Phase transitions in the 1-2 model

Speaker: 

Zhongyang Li

Institution: 

University of Connecticut

Time: 

Monday, November 21, 2016 - 12:00pm to 12:50pm

Host: 

Location: 

340P

 

 

A configuration in the 1-2 model is a subgraph of the hexagonal lattice, in which each vertex is incident to 1 or 2 edges. By assigning weights to configurations at each vertex, we can define a family of probability measures on the space of these configurations, such that the probability of a configuration is proportional to the product of weights of configurations at vertices.

 

We study the phase transition of the model by investigating the probability measures with varying weights. We explicitly identify the critical weights, in the sense that the edge-edge correlation decays to 0 exponentially in the subcritical case, and converges to a non-zero constant in the supercritical case, under the limit measure obtained from torus approximation. These results are obtained by a novel measure-preserving correspondence between configurations in the 1-2 model and perfect matchings on a decorated graph, which appears to be a more efficient way to solve the model, compared to the holographic algorithm used by computer scientists to study the model. 

 

When the weights are uniform, we prove a weak mixing property for the finite-volume measures - this implies the uniqueness of the infinite-volume measure and the fast mixing of a Markov chain Monte Carlo sampling. The major difficulty here is the absence of stochastic monotonicity.

Poisson approximation of combinatorial assemblies with low rank

Speaker: 

Stephen DeSalvo

Institution: 

UCLA

Time: 

Tuesday, November 15, 2016 - 11:00pm to 11:50pm

Host: 

Location: 

RH 306

We present a general framework for approximating combinatorial assemblies when both the size $n$ and the number of components $k$ is specified.  The approach is an extension of the usual saddle point approximation, and we demonstrate near-universal behavior when the rank $r := n-k$ is small relative to $n$ (hence the name `low rank’).  

 

In particular, for $\ell = 1, 2, \ldots$, when $r \asymp n^\alpha$, for $\alpha \in \left(\frac{\ell}{\ell+1}, \frac{\ell+1}{\ell+2}\right)$, the size~$L_1$ of the largest component converges in probability to $\ell+2$.  When $r \sim t\, n^{\ell/(\ell+1)}$ for any $t>0$ and any positive integer $\ell$, $\P(L_1 \in \{\ell+1, \ell+2\}) \to 1$.  We also obtain as a corollary bounds on the number of such combinatorial assemblies, which in the special case of set partitions fills in a countable number of gaps in the asymptotic analysis of Louchard for Stirling numbers of the second kind. 

 

This is joint work with Richard Arratia.

Random perturbations of non-normal matrices

Speaker: 

Elliot Paquette

Institution: 

Ohio State University

Time: 

Tuesday, January 24, 2017 - 11:00am

Location: 

RH 306

Suppose one wants to calculate the eigenvalues of a large, non-normal matrix.  For example, consider the matrix which is 0 in most places except above the diagonal, where it is 1.  The eigenvalues of this matrix are all 0.  Similarly, if one conjugates this matrix, in exact arithmetic one would get all eigenvalues equal to 0.  However, when one makes floating point errors, the eigenvalues of this matrix are dramatically different.  One can model these errors as performing a small, random perturbation to the matrix.  And, far from being random, the eigenvalues of this perturbed matrix nearly exactly equidistribute on the unit circle.  This talk will give a probabilistic explanation of why this happens and discuss the general question: how does one predict the eigenvalues of a large, non-normal, randomly perturbed matrix?

Noncommutative Majorization Principles and Grothendieck's Inequality

Speaker: 

Steven Heilman

Institution: 

UCLA

Time: 

Tuesday, November 29, 2016 - 11:00pm to 11:50pm

Host: 

Location: 

RH 306

The seminal invariance principle of Mossel-O'Donnell-Oleszkiewicz implies the following. Suppose we have a multilinear polynomial Q, all of whose partial derivatives are small. Then the distribution of Q on i.i.d. uniform {-1,1} inputs is close to the distribution of Q on i.i.d. standard Gaussian inputs. The case that Q is a linear function recovers the Berry-Esseen Central Limit Theorem. In this way, the invariance principle is a nonlinear version of the Central Limit Theorem. We prove the following version of one of the two inequalities of the invariance principle, which we call a majorization principle. Suppose we have a multilinear polynomial Q with matrix coefficients, all of whose partial derivatives are small. Then, for any even K>1, the Kth moment of Q on i.i.d. uniform {-1,1} inputs is larger than the Kth moment of Q on (carefully chosen) random matrix inputs, minus a small number. The exact statement must be phrased carefully in order to avoid being false. Time permitting, we discuss applications of this result to anti-concentration, and to computational hardness for the noncommutative Grothendieck inequality. (joint with Thomas Vidick) (

Loop erased random walk, uniform spanning tree and bi-Laplacian Gaussian field in the critical dimension.

Speaker: 

Wei Wu

Institution: 

CIMS

Time: 

Monday, October 24, 2016 - 11:00am to 11:50am

Host: 

Location: 

NS2 1201

Critical lattice models are believed to converge to a free field in the scaling limit, at or above their critical dimension.  This has been (partially) established for Ising and Phi^4 models for d \geq 4. We describe a simple spin model from uniform spanning forests in $\Z^d$ whose critical dimension is 4 and prove that the scaling limit is the bi-Laplacian Gaussian field for $d\ge 4$. At dimension 4, there is a logarithmic correction for the spin-spin correlation and the bi-Laplacian Gaussian field is a log correlated field. The proof also improves the known mean field picture of LERW in d=4, by showing that the renormalized escape probability (and arm events) of 4D LERW converge to some "continuum escaping probability". Based on joint works with Greg Lawler and Xin Sun.

Compactness and Large Deviations

Speaker: 

Chiranjib Mukherjee

Institution: 

CIMS

Time: 

Tuesday, October 25, 2016 - 11:00am to 11:50am

Host: 

Location: 

RH 306

COMPACTNESS AND LARGE DEVIATIONS

In a reasonable topological space, large deviation estimates essentially deal
with probabilities of events that are asymptotically (exponentially) small,
and in a certain sense, quantify the rate of these decaying probabilities.
In such estimates, upper bounds for such small probabilities often require 
compactness of the ambient space, which is often absent in problems arising in
statistical mechanics (for example, distributions of local times of
Brownian motion in the full space R^d). Motivated by such a problem, we
present a robust theory of “translation-invariant compactification”
of probability measures in R^d. Thanks to an inherent shift-invariance of
the underlying problem, we are able to apply this abstract theory painlessly
and solve a long standing problem in statistical mechanics, the mean-field
polaron problem.

This talk is based on joint works with S. R. S. Varadhan (New York), as
well as with Erwin Bolthausen(Zurich)and Wolfgang Koenig (Berlin).

Universality for the Toda algorithm to compute the eigenvalues of a random matrix.

Speaker: 

Tom Trogdon

Institution: 

UCI

Time: 

Tuesday, October 11, 2016 - 11:00am to 11:50am

Host: 

Location: 

RH 3066

 

 

The Toda lattice, beyond being a completely integrable dynamical system, has many important properties.  Classically, the Toda flow is seen as acting on a specific class of bi-infinite Jacobi matrices.  Depending on the boundary conditions imposed for finite matrices, it is well known that the flow can be used as an eigenvalue algorithm. It was noticed by P. Deift, G. Menon and C. Pfrang that the fluctuations in the time it takes to compute eigenvalues of a random symmetric matrix with the Toda, QR and matrix sign algorithms are universal. In this talk, I will present a proof of such universality for the Toda algorithm.  I will also discuss empirical and rigorous results for other algorithms from numerical analysis.  This is joint work with P. Deift.

A two scale proof of the Eyring-Kramers formula (joint work with Andre Schlichting)

Speaker: 

Georg Menz

Institution: 

UCLA

Time: 

Tuesday, October 4, 2016 - 11:00pm to 11:50pm

Host: 

Location: 

RH 306

We consider a drift-diffusion process on a smooth potential landscape

with small noise. We give a new proof of the Eyring-Kramers formula

which asymptotically characterizes the spectral gap of the generator of

the diffusion. The proof is based on a refinement of the two-scale

approach introduced by Grunewald, Otto, Villani, and Westdickenberg and

of the mean-difference estimate introduced by Chafai and Malrieu. The

new proof exploits the idea that the process has two natural

time-scales: a fast time-scale resulting from the fast convergence to a

metastable state, and a slow time-scale resulting from exponentially

long waiting times of jumps between metastable states. A nice feature

of the argument is that it can be used to deduce an asymptotic formula

for the log-Sobolev constant, which was previously unknown.

Obliquely reflected Brownian motion

Speaker: 

Zhen-qing Chen

Institution: 

University of Washington

Time: 

Tuesday, May 17, 2016 - 1:00pm to 1:50pm

Host: 

Location: 

RH 306

Boundary theory for one-dimensional diffusions is now well understood. Boundary theory for multi-dimensional diffusions is much richer and remains to be better understood. In this talk, we will be concerned with the construction and characterization of obliquely reflected Brownian motions in all bounded simply connected planar domains, including non-smooth domains,
with general reflection vector field on the boundary.  
We show that the family of all obliquely reflected Brownian motions in a given domain can be characterized in two different ways, either by the field of angles of oblique reflection on the boundary or by the stationary distribution and the rate of rotation of the process about a reference point in the domain. We further show that Brownian motion with darning and excursion reflected Brownian motion can be obtained as a limit of obliquely reflected Brownian motions.

Based on joint work with K. Burdzy, D. Marshall and K. Ramanan.

Pages

Subscribe to RSS - Combinatorics and Probability