On level line fluctuations of SOS surfaces above a wall. Abstract
We study the low temperature $(2+1)$D Solid-On-Solid model on $[ 1, L ]^2$ with zero boundary conditions and non-negative heights (a floor at height $0$). Caputo et al.\ (2016) established that this random surface typically admits either $\mathfrak h $ or $\mathfrak h+1$ many nested macroscopic level line loops $\{\mathcal L_i\}_{i\geq 0}$ for an explicit $\mathfrak h\asymp \log L$, and its top loop $\mathcal L_0$ has cube-root fluctuations: e.g., if $\rho(x)$ is the vertical displacement of $\mathcal L_0$ from the bottom boundary point $(x,0)$, then $\max \rho(x) = L^{1/3+o(1)}$ over $x\in I_0:=L/2+[-L^{2/3},L^{2/3}]$. It is believed that rescaling $\rho$ by $L^{1/3}$ and $I_0$ by $L^{2/3}$ would yield a limit law of a diffusion on $[-1,1]$. However, no nontrivial lower bound was known on $\rho(x)$ for a fixed $x\in I_0$ (e.g., $x=\frac L2$), let alone on $\min\rho(x)$ in $I_0$, to complement the bound on $\max\rho(x)$. Here we show a lower bound of the predicted order $L^{1/3}$: for every $\epsilon>0$ there exists $\delta>0$ such that $\min_{x\in I_0} \rho(x) \geq \delta L^{1/3}$ with probability at least $1-\epsilon$. The proof relies on the Ornstein–Zernike machinery due to Campanino–Ioffe–Velenik, and a result of Ioffe, Shlosman and Toninelli (2015) that rules out pinning in Ising polymers with modified interactions along the boundary. En route, we refine the latter result into a Brownian excursion limit law, which may be of independent interest. We further show that in a $ K L^{2/3}\times K L^{2/3}$ box with boundary conditions $\mathfrak h-1,\mathfrak h,\mathfrak h,\mathfrak h$ (i.e., $\mathfrak h-1$ on the bottom side and $\mathfrak h$ elsewhere), the limit of $\rho(x)$ as $K,L\to\infty$ is a Ferrari–Spohn diffusion.
Submitted.
Metastability cascades and prewetting in the SOS model. Abstract
We study Glauber dynamics for the low temperature $(2+1)$D Solid-On-Solid model on a box of side-length $n$ with a floor at height $0$ (inducing entropic repulsion) and a competing bulk external field $\lambda$ pointing down (the prewetting problem). In 1996, Cesi and Martinelli showed that if the inverse-temperature $\beta$ is large enough, then along a decreasing sequence of critical points $(\lambda_c^{(k)})_{ k=0}^{K_\beta}$ the dynamics is torpid: its inverse spectral gap is $O(1)$ when $\lambda \in (\lambda_c^{(k+1)},\lambda_c^{(k)})$ whereas it is $\exp[\Theta(n)]$ at each $\lambda_c^{(k)}$ for each $k\leq K_\beta$, due to a coexistence of rigid phases at heights $k+1$ and $k$. Our focus is understanding (a) the onset of metastability as $\lambda_n\uparrow\lambda_c^{(k)}$; and (b) the effect of an unbounded number of layers, as we remove the restriction $k\le K_\beta$, and even allow for $\lambda_n\to 0$ towards the $\lambda = 0$ case which has $O(\log n)$ layers and was studied by Caputo et al. (2014). We show that for any $k$, possibly growing with $n$, the inverse gap is $\exp[\tilde\Theta(1/|\lambda_n-\lambda_c^{(k)}|)]$ as $\lambda\uparrow \lambda_c^{(k)}$ up to distance $n^{-1+o(1)}$ from this critical point, due to a metastable layer at height $k$ on the way to forming the desired layer at height $k+1$. By taking $\lambda_n = n^{-\alpha}$ (corresponding to $k_n\asymp \log n$), this also interpolates down to the behavior of the dynamics when $\lambda =0$. We compliment this by extending the fast mixing to all $\lambda$ uniformly bounded away from $(\lambda_c^{(k)})_{k=0}^\infty$. Together, these results provide a sharp understanding of the predicted infinite sequence of dynamical phase transitions governed by the layering phenomenon. Due to the above obstacles, our methods are initially only applicable to 1 of these 4 interface extrema, and additional ideas are needed to recover the other 3 rates given the behavior of the first one.
Submitted.
Extrema of 3D Potts interfaces. Abstract
The interface between the plus and minus phases in the low temperature 3D Ising model has been intensely studied since Dobrushin's pioneering works in the early 1970's established its rigidity. Advances in the last decade yielded the tightness of the maximum of the interface of this Ising model on the cylinder of side length $n$, around a mean that is asymptotically $c\log n$ for an explicit $c$ (temperature dependent). In this work, we establish analogous results for the 3D Potts and random cluster (FK) models. Compared to 3D Ising, the Potts model and its lack of monotonicity form obstacles for existing methods, calling for new proof ideas, while its interfaces (and associated extrema) exhibit richer behavior. We show that the maxima and minima of the interface bounding the blue component in the 3D Potts interface, and those of the interface bounding the bottom component in the 3D FK model, are governed by 4 different large deviation rates, whence the corresponding global extrema feature 4 distinct constants $c$ as above. Due to the above obstacles, our methods are initially only applicable to 1 of these 4 interface extrema, and additional ideas are needed to recover the other 3 rates given the behavior of the first one.
Communications in Mathematical Physics, to appear.
The extremal point process of branching Brownian motion in ℝd. Abstract
We consider a branching Brownian motion in $\mathbb{R}^d$ with $d \geq 1$ in which the position $X_t^{(u)}\in \mathbb{R}^d$ of a particle $u$ at time $t$ can be encoded by its direction $\theta^{(u)}_t \in \mathbb S^{d-1}$ and its distance $R^{(u)}_t$ to 0. We prove that the extremal point process $\sum \delta_{\theta^{(u)}_t, R^{(u)}_t - m_t^{(d)}}$ (where the sum is over all particles alive at time $t$ and $m^{(d)}_t$ is an explicit centring term) converges in distribution to a randomly shifted decorated Poisson point process on $\mathbb{S}^{d-1} \times \mathbb{R}$. More precisely, the so-called clan-leaders form a Cox process with intensity proportional to $D_\infty(\theta) e^{-\sqrt{2}r} d r d \theta $, where $D_\infty(\theta)$ is the limit of the derivative martingale in direction $\theta$ and the decorations are i.i.d. copies of the decoration process of the standard one-dimensional branching Brownian motion. This proves a conjecture of Stasiński, Berestycki and Mallein (Ann. Inst. H. Poincaré 57:1786–1810, 2021), and builds on that paper and on Kim, Lubetzky and Zeitouni (Ann. Appl. Probab., to appear).
Annals of Probability, to appear.
On the limiting law of line ensembles of Brownian polymers with geometric area tilts. Abstract
We study the line ensembles of non-crossing Brownian bridges above a hard wall, each tilted by the area of the region below it with geometrically growing pre-factors. Thiss model, which mimics the level lines of the $(2+1)$D SOS model above a hard wall, was studied in two works from 2019 by Caputo, Ioffe and Wachtel. In those works, the tighh tness of the law of the top $k$ paths, for any fixed $k$, was established under either zero or free boundary conditions, which in the former setting implied the existence of a limit via a monotonicity argument. Here we address the open problem of a limit under free boundary conditions: we prove that as the interval length, followed by the nn umber of paths, go to $\infty$, the top $k$ paths converge to the same limit as in the free boundary case, as conjectured by Caputo, Ioffe and Wachtel.
Annales de l'Institut Henri Poincaré (B) Probab. Statist., to appear.
The threshold for stacked triangulations. Abstract
A stacked triangulation of a $d$-simplex $\mathbf{o}=\{1,\ldots,d+1\}$ ($d\geq 2$) is a triangulation obtained by repeatedly subdividing a $d$-simplex into $d+1$ nee w ones via a new vertex (the case $d=2$ is known as an Appolonian network). We study the occurrence of such a triangulation in the Linial–Meshulam model, i.e., for which $p$ does the random simplicial complex $Y\sim \mathcal{Y}_d(n,p)$ contain the faces of a stacked triangulation of the $d$-simplex $\mathbf{o}$, with its internal verr tices labeled in $[n]$. In the language of bootstrap percolation in hypergraphs, it pertains to the threshold for $K_{d+2}^{d+1}$, the $(d+1)$-uniform clique on $d+2$ vee rtices.
Our main result identifies this threshold for every $d\geq 2$, showing it is asymptotically $(\alpha_d n)^{-1/d}$, where $\alpha_d$ is the growth rate of the Fuss–Caa talan numbers of order $d$. The proof hinges on a second moment argument in the supercritical regime, and on Kalai's algebraic shifting in the subcritical regime.
International Mathematics Research Notices (IMRN) (2023), Issue 19, 16296–16335.
Entropic repulsion of 3D Ising interfaces conditioned to stay above a floor. Abstract
We study the interface of the Ising model in a cylinder of side-length $n$ in $\mathbb Z^3$ under Dobrushin's boundary conditions at low temperature $1/\beta$, conditioned to stay in a half-space above height $-\sfh$ (a floor). Without this conditioning, Dobrushin showed in 1972 that typically most of the interface is flat at height $0$. With the floor, for small $\sfh$, the model is expected to exhibit \emph{entropic repulsion}, where the typical height of the interface lifts off of $0$. Detailed understanding of the SOS model---a more tractable height function approximation of 3D Ising---due to Caputo et al., suggests that there is a single integer value $-h_n^* \sim -c\log n$ of the floor height, delineating the transition between rigidity at height $0$ and entropic repulsion.
We identify an explicit $h_n^*=( c_\star+o(1))\log n$ such that, for the typical Ising interface above a hard floor at $-\sfh$, all but an $\epsilon(\beta)$-fraction of the sites are propelled to be above height $0$ if $\sfh < h_n^*-1$, whereas all but an $\epsilon(\beta)$-fraction of the sites remain at height $0$ if $\sfh\geq h_n^*$. Further, $c_\star$ is such that the typical height of the unconditional maximum is $(2c_\star + o(1))\log n$; this confirms scaling predictions from the SOS approximation.
Electronic Journal of Probability 28 (2023), 1–44.
Approximate domain Markov property for rigid Ising interfaces. Abstract
Consider the Ising model on a centered box of side length $n$ in $\mathbb Z^d$ with $\mp$-boundary conditions that are minus in the upper half-space and plus in the lower half-space. Dobrushin famously showed that in dimensions $d\ge 3$, at low-temperatures the Ising interface (dual-surface separating the plus/minus phases) is rigid, i.e., it has $O(1)$ height fluctuations. Recently, the authors decomposed these oscillations into pillars and identified their typical shape, leading to a law of large numbers and tightness of their maximum.
Suppose we condition on a height-$h$ level curve of the interface, bounding a set $S \subset \mathbb Z^{d-1}$, along with the entire interface outside the cylinder $S\times \mathbb Z$: what does the interface in $S\times \mathbb Z$ look like? Many models of random surfaces (e.g., SOS and DGFF) fundamentally satisfy the domain Markov property, whereby their heights on $S$ only depend on the heights on $S^c$ through the heights on $\partial S$. The Ising interface importantly does not satisfy this property; the law of the interface depends on the full spin configuration outside $S\times \mathbb Z$.
Here we establish an approximate domain Markov property inside the level curves of the Ising interface. We first extend Dobrushin's result to this setting, showing the interface in $S\times \mathbb Z$ is rigid about height $h$, with exponential tails on its height oscillations. Then we show that the typical tall pillars in $S\times \mathbb Z$ are uniformly absolutely continuous with respect to tall pillars of the unconditional Ising interface. Using this we identify the law of large numbers, tightness, and Gumbel tail bounds on the maximum oscillations in $S\times \mathbb Z$ about height $h$, showing that these only depend on the conditioning through the cardinality of $S$.
Journal of Statistical Physics 190 (2023), no. 5, 99.
The maximum of branching Brownian motion in ℝd. Abstract
We show that in branching Brownian motion (BBM) in $\mathbb{R}^d$, $d\geq 2$, the law of $R_t^*$, the maximum distance of a particle from the origin at time $t$, converges as $t\to\infty$ to the law of a randomly shifted Gumbel random variable.
Annals of Applied Probability 33 (2023), no. 2, 1515–1568.
Noise sensitivity of critical random graphs. Abstract
We study noise sensitivity of properties of the largest components $(\mathcal{C}_j)_{j\geq 1}$ of the random graph $\mathcal{G}(n,p)$ in its critical window $p=(1+\lambda n^{-1/3})/n$. For instance, is the property ``$|\mathcal{C}_1|$ exceeds its median size'' noise sensitive? Roberts and \c{S}eng\"{u}l (2018) proved that the answer to this is yes if the noise $\epsilon$ is such that $\epsilon \gg n^{-1/6}$, and conjectured the correct threshold is $\epsilon \gg n^{-1/3}$. That is, the threshold for sensitivity should coincide with the critical window—as shown for the existence of long cycles by the first author and Steif (2015).
We prove that for $\epsilon\gg n^{-1/3}$ the pair of vectors $ n^{-2/3}(|\mathcal{C}_j|)_{j\geq 1}$ before and after the noise converges in distribution to a pair of i.i.d. random variables, whereas for $\epsilon\ll n^{-1/3}$ the $\ell^2$-distance between the two goes to 0 in probability. This confirms the above conjecture: any Boolean function of the vector of rescaled component sizes is sensitive in the former case and stable in the latter.
We also look at the effect of the noise on the metric space $n^{-1/3}(\mathcal{C}_j)_{j\geq 1}$. E.g., for $\epsilon\geq n^{-1/3+o(1)}$, we show that the joint law of the spaces before and after the noise converges to a product measure, implying noise sensitivity of any property seen in the limit, e.g., ``the diameter of $\mathcal{C}_1$ exceeds its median.''
Israel Journal of Mathematics 252 (2022), 187–214.
Cycle lengths in sparse random graphs. Abstract
We study the set $\mathcal{L}(G)$ of lengths of all cycles that appear in a random $d$-regular $G$ on $n$ vertices for a fixed $d\geq 3$, as well as in Erdős–Rényi random graphs on $n$ vertices with a fixed average degree $c>1$. Fundamental results on the distribution of cycle counts in these models were established in the 1980's and early 1990's, with a focus on the extreme lengths: cycles of fixed length, and cycles of length linear in $n$. Here we derive, for a random $d$-regular graph, the limiting probability that $\mathcal{L}(G)$ simultaneously contains the entire range $\{\ell,\ldots,n\}$ for $\ell\geq 3$, as an explicit expression $\theta_\ell=\theta_\ell(d)\in(0,1)$ which goes to $1$ as $\ell\to\infty$. For the random graph $\mathcal{G}(n,p)$ with $p=c/n$, where $c\geq C_0$ for some absolute constant $C_0$, we show the analogous result for the range $\{\ell,\ldots,(1-o(1))L_{\rm max}(G)\}$, where $L_{\rm max}$ is the length of a longest cycle in $G$. The limiting probability for $\mathcal{G}(n,p)$ coincides with $\theta_\ell$ from the $d$-regular case when $c$ is the integer $d-1$. In addition, for the directed random graph $\mathcal{D}(n,p)$ we show results analogous to those on $\mathcal{G}(n,p)$, and for both models we find an interval of $c \epsilon^2 n$ consecutive cycle lengths in the slightly supercritical regime $p=\frac{1+\epsilon}n$.
Random Structures and Algorithms 61 (2022), no. 3, 444–461.
Maximum of Branching Brownian motion in a periodic environment. Abstract
We study the maximum of Branching Brownian motion (BBM) with branching rates that vary in space, via a periodic function of a particle's location. This corresponds to a variant of the F-KPP equation in a periodic medium, extensively studied in the last 15 years, admitting pulsating fronts as solutions. Recent progress on this PDE due to Hamel, Nolen, Roquejoffre and Ryzhik ('16) implies tightness for the centered maximum of BBM in a periodic environment. Here we establish the convergence in distribution of specific subsequences of this centered maximum, and identify the limiting distribution. Consequently, we find the asymptotic shift between the solution to the corresponding F-KPP equation with Heavyside initial data and the pulsating wave, thereby answering a question of Hamel et al. Analogous results are given for the cases where the Brownian motion is replaced by an Ito diffusion with periodic coefficients, as well as for nearest-neighbor branching random walks.
Annales de l'Institut Henri Poincaré (B) Probab. Statist. 58 (2022), no. 4, 2065–2093.
Maximum and shape of interfaces in 3D Ising crystals. Abstract
Dobrushin (1972) showed that the interface of a 3D Ising model with minus boundary conditions above the $xy$-plane and plus below is rigid (has $O(1)$-fluctuations) at every sufficiently low temperature. Since then, basic features of this interface—such as the asymptotics of its maximum—were only identified in more tractable random surface models that approximate the Ising interface at low temperatures, e.g., for the (2+1)D Solid-On-Solid model. Here we study the large deviations of the interface of the 3D Ising model in a cube of side-length $n$ with Dobrushin's boundary conditions, and in particular obtain a law of large numbers for $M_n$, its maximum: if the inverse-temperature $\beta$ is large enough, then $M_n / \log n \to 2/\alpha_\beta$ as $n\to\infty$, in probability, where $\alpha_\beta$ is given by a large deviation rate in infinite volume.
We further show that, on the large deviation event that the interface connects the origin to height $h$, it consists of a 1D spine that behaves like a random walk, in that it decomposes into a linear (in $h$) number of asymptotically-stationary weakly-dependent increments that have exponential tails. As the number $T$ of increments diverges, properties of the interface such as its surface area, volume, and the location of its tip, all obey CLTs with variances linear in $T$. These results generalize to every dimension $d\geq 3$.
Communications in Pure and Applied Mathematics 75 (2022), no. 12, 2575–2684.
Universality for Langevin-like spin glass dynamics. Abstract
We study dynamics for asymmetric spin glass models, proposed by Hertz et al. and Sompolinsky et al. in the 1980's in the context of neural networks: particles evolve via a modified Langevin dynamics for the Sherrington–Kirkpatrick model with soft spins, whereby the disorder is i.i.d. standard Gaussian rather than symmetric. Ben Arous and Guionnet (1995), followed by Guionnet (1997), proved for Gaussian interactions that as the number of particles grows, the short-term empirical law of this dynamics converges a.s. to a non-random law $\mu_\star$ of a ``self-consistent single spin dynamics,'' as predicted by physicists. Here we obtain universality of this fact: For asymmetric disorder given by i.i.d. variables of zero mean, unit variance and exponential or better tail decay, at every temperature, the empirical law of sample paths of the Langevin-like dynamics in a fixed time interval has the same a.s. limit $\mu_\star$.
Annals of Applied Probability 31 (2021), no. 6, 2864–2880.
Fast initial conditions for Glauber dynamics. Abstract
In the study of Markov chain mixing times, analysis has centered on the performance from a worst-case starting state. Here, in the context of Glauber dynamics for the one-dimensional Ising model, we show how new ideas from information percolation can be used to establish mixing times from other starting states. At high temperatures we show that the alternating initial condition is asymptotically the fastest one, and, surprisingly, its mixing time is faster than at infinite temperature, accelerating as the inverse-temperature $\beta$ ranges from 0 to $\beta_0=\frac12 \mathrm{arctanh}(\frac13)$. Moreover, the dominant test function depends on the temperature: at $\beta<\beta_0$ it is autocorrelation, whereas at $\beta>\beta_0$ it is the Hamiltonian.
Probability Theory and Related Fields 181 (2021), no. 1–3, 647–667.
Tightness and tails of the maximum in 3D Ising interfaces. Abstract
Consider the 3D Ising model on a box of side length $n$ with minus boundary conditions above the $xy$-plane and plus boundary conditions below it. At low temperatures, Dobrushin (1972) showed that the interface separating the predominantly plus and predominantly minus regions is localized: its height above a fixed point has exponential tails. Recently, the authors proved a law of large numbers for the maximum height $M_n$ of this interface: for every $\beta$ large, $M_n/ \log n\to c_\beta$ in probability as $n\to\infty$.
Here we show that the laws of the centered maxima $(M_n - \mathbb{E}[M_n])_{n\geq 1}$ are uniformly tight. Moreover, even though this sequence does not converge, we prove that it has uniform upper and lower Gumbel tails (exponential right tails and doubly exponential left tails). Key to the proof is a sharp (up to $O(1)$ precision) understanding of the surface large deviations. This includes, in particular, the shape of a pillar that reaches near-maximum height, even at its base, where the interactions with neighboring pillars are dominant.
Annals of Probability 49 (2021), no. 2, 732–792.
Minimum weight disk triangulations and fillings. Abstract
We study the minimum total weight of a disk triangulation using vertices out of $\{1,\ldots,n\}$, where the boundary is the triangle $(123)$ and the $\binom{n}3$ triangles have independent weights, e.g. $\mathrm{Exp}(1)$ or $\mathrm{U}(0,1)$. We show that for explicit constants $c_1,c_2>0$, this minimum is $c_1 \frac{\log n}{\sqrt n} + c_2 \frac{\log\log n}{\sqrt n} + \frac{Y_n}{\sqrt n}$ where the random variable $Y_n$ is tight, and it is attained by a triangulation that consists of $\frac14\log n + O_{P}(\sqrt{\log n}) $ vertices. Moreover, for disk triangulations that are canonical, in that no inner triangle contains all but $O(1)$ of the vertices, the minimum weight has the above form with the law of $Y_n$ converging weakly to a shifted Gumbel. In addition, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle $(123)$ are both attained by the minimum weight disk triangulation.
Transactions of the American Mathematical Society 374 (2021), no. 5, 3265–3287.
Empirical spectral distributions of sparse random graphs. Abstract
We study the spectrum of a random multigraph with a degree sequence $\mathbf{D}_n=(D_i)_{i=1}^n$ and average degree $1 \ll \omega_n \ll n$, generated by the configuration model. We show that, when the empirical spectral distribution (ESD) of $\omega_n^{-1} \mathbf{D}_n $ converges weakly to a limit $\nu$, under mild moment assumptions (e.g., $D_i/\omega_n$ are i.i.d. with a finite second moment), the ESD of the normalized adjacency matrix converges in probability to $\nu\boxtimes \sigma_{\mathrm{sc}}$, the free multiplicative convolution of $\nu$ with the semicircle law. Relating this limit with a variant of the Marchenko–Pastur law yields the continuity of its density (away from zero), and an effective procedure for determining its support.
Our proof of convergence is based on a coupling of the graph to an inhomogeneous Erdős–Rényi graph with the target ESD, using three intermediate random graphs, with a negligible number of edges modified in each step.
In and Out of Equilibrium 3, Celebrating Vladas Sidoravicius (Progr. Probab. 77) (2021), 319–345.
Random walks on Ramanujan complexes and digraphs. Abstract
The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres (2016). In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat–Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time logkn. This is established by systematically studying the mixing of random walks on Ramanujan digraphs with certain properties. We then show that the digraph arising from such an operator $T$ on a Ramanujan complex has these properties. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $\widetilde{A}_n$ and $\widetilde{C}_2$.
Journal of the European Mathematical Society (JEMS) 22 (2020), no. 11, pp. 3441–3466.
Asymptotics in bond percolation on expanders. Abstract
We consider supercritical bond percolation on a family of high-girth d-regular expanders. Alon, Benjamini and Stacey (2004) established that its critical probability for the appearance of a linear-sized ("giant") component is $p_c=1/(d−1)$. Our main result recovers the sharp asymptotics of the size and degree distribution of the vertices in the giant at any $p>p_c$, as well as that of its 2-core. It was further shown in [ABS04] that the second largest component, at any $0 < p < 1$, has size at most $n^{\omega}$ for some $\omega<1$. We show that, unlike the situation in the classical Erdős–Rényi random graph, the second largest component in bond percolation on a regular expander, even with an arbitrarily large girth, can have size $n^{\omega'}$ for $\omega'$ arbitrarily close to $1$. Moreover, as a by-product of that construction, we answer negatively a question of Benjamini (2013) on the relation between the diameter of a component in percolation on expanders and the existence of a giant component. Finally, we establish other typical features of the giant component, e.g., the existence of a linear path.
Random Structures and Algorithms 56 (2020), no. 4, 927–947.
Quasi-polynomial mixing of critical 2D random cluster models. Abstract
We study the Glauber dynamics for the random cluster (FK) model on the torus $(\mathbb{Z}/n\mathbb{Z})^2$ with parameters $(p,q)$, for $q \in (1,4]$ and $p$ the critical point $p_c$. The dynamics is believed to undergo a critical slowdown, with its continuous-time mixing time transitioning from $O(\log n)$ for $p\neq p_c$ to a power-law in $n$ at $p=p_c$. This was verified at $p\neq p_c$ by Blanca and Sinclair, whereas at the critical $p=p_c$, with the exception of the special integer points $q=2,3,4$ (where the model corresponds to Ising/Potts models) the best-known upper bound on mixing was exponential in $n$. Here we prove an upper bound of $n^{O(\log n)}$ at $p=p_c$ for all $q\in (1,4]$, where the key ingredient is controlling the number of disjoint long-range crossings at criticality.
Random Structures and Algorithms 56 (2020), no. 2, 517–556.
Exponentially slow mixing in the mean-field Swendsen–Wang dynamics. Abstract
Swendsen–Wang dynamics for the Potts model was proposed in the late 1980's as an alternative to single-site heat-bath dynamics, in which global updates allow this MCMC sampler to switch between metastable states and ideally mix faster. Gore and Jerrum (1999) found that this dynamics may in fact exhibit slow mixing: they showed that, for the Potts model with $q\geq 3$ colors on the complete graph on $n$ vertices at the critical point $\beta_c(q)$, Swendsen–Wang dynamics has $t_{\mathrm{mix}}\geq \exp(c\sqrt n)$. The same lower bound was extended to the critical window $(\beta_s,\beta_S)$ around $\beta_c$ by Galanis et al. (2015), as well as to the corresponding mean-field FK model by Blanca and Sinclair (2015). In both cases, an upper bound of $t_{\mathrm{mix}} \leq \exp(c' n)$ was known. Here we show that the mixing time is truly exponential in $n$: namely, $t_{\mathrm{mix}} \geq \exp (cn)$ for Swendsen–Wang dynamics when $q\geq 3$ and $\beta\in(\beta_s,\beta_S)$, and the same bound holds for the related MCMC samplers for the mean-field FK model when $q>2$.
Annales de l'Institut Henri Poincaré (B) Probab. Statist. 56 (2020), no. 1, 68–86.
Preliminary version appeared in the Proc. of the 29rd annual ACM-SIAM SODA (2018), 1981–1988.
Comparing mixing times on sparse random graphs. Abstract
It is natural to expect that nonbacktracking random walk will mix faster than simple random walks, but so far this has only been proved in regular graphs. To analyze typical irregular graphs, let $G$ be a random graph on $n$ vertices with minimum degree 3 and a degree distribution that has exponential tails. We determine the precise worst-case mixing time for simple random walk on $G$, and show that, with high probability, it exhibits cutoff at time $\textbf{h}^{-1} \log n$, where $\textbf{h}$ is the asymptotic entropy for simple random walk on a Galton–Watson tree that approximates $G$ locally. (Previously this was only known for typical starting points.) Furthermore, we show this asymptotic mixing time is strictly larger than the mixing time of nonbacktracking walk, via a delicate comparison of entropies on the Galton–Watson tree.
Annales de l'Institut Henri Poincaré (B) Probab. Statist. 55 (2019), no. 2, 1116–1130.
Preliminary version appeared in the Proc. of the 29rd annual ACM-SIAM SODA (2018), 1734–1740.
A large deviation principle for the Erdős–Rényi uniform random graph,. Abstract
Starting with the large deviation principle (LDP) for the Erdős–Rényi binomial random graph $\mathcal{G}(n,p)$ (edge indicators are i.i.d.), due to Chatterjee and Varadhan (2011), we derive the LDP for the uniform random graph $\mathcal{G}(n,m)$ (the uniform distribution over graphs with $n$ vertices and $m$ edges), at suitable $m=m_n$.Applying the latter LDP we find that tail decays for subgraph counts in $\mathcal{G}(n,m_n)$ are controlled by variational problems, which up to a constant shift, coincide with those studied by Kenyon et al. and Radin et al. in the context of constrained random graphs, e.g., the edge/triangle model.
Electronic Communications in Probability 23 (2018), paper no. 79, 13 pp.
Concentration inequalities for polynomials of contracting Ising models. Abstract
We study the concentration of a degree-$d$ polynomial of the $N$ spins of a general Ising model, in the regime where single-site Glauber dynamics is contracting. For $d=1$, Gaussian concentration was shown by Marton (1996) and Samson (2000) as a special case of concentration for convex Lipschitz functions, and extended to a variety of related settings by e.g., Chazottes et al. (2007) and Kontorovich and Ramanan (2008). For $d=2$, exponential concentration was shown by Marton (2003) on lattices. We treat a general fixed degree $d$ with $O(1)$ coefficients, and show that the polynomial has variance $O(N^d)$ and, after rescaling it by $N^{-d/2}$, its tail probabilities decay as $\exp(- c\, r^{2/d})$ for deviations of $r \geq C \log N$.
Electronic Communications in Probability 23 (2018), paper no. 76, 12 pp.
The effect of boundary conditions on mixing of 2D Potts models at discontinuous phase transitions. Abstract
We study the critical stochastic $q$-state Potts model on the square lattice. Unlike the expected behavior when the phase transition is continuous ($q=2,3,4$)—a universal power-law for the mixing time independently of the boundary conditions—the mixing time at a discontinuous phase transition, $t_{\mathrm{mix}}$, is highly sensitive to those. It was recently shown by the authors that $t_{\mathrm{mix}} \gtrsim \exp(cn)$ on an $n\times n$ box with periodic boundary, yet under free or monochromatic boundary conditions $t_{\mathrm{mix}} \lesssim \exp(n^{1/2+o(1)})$. In this work we classify this effect under boundary conditions interpolating between these two (torus vs. free/monochromatic) for Swendsen–Wang dynamics at large $q$. Specifically, we show that alternating boundary conditions, such as red-free-red-free, also induce $t_{\mathrm{mix}} \gtrsim \exp(cn)$, whereas red-periodic-red-periodic, as well as Dobrushin boundary conditions, such as red-red-free-free, induce sub-exponential mixing.
Electronic Journal of Probability 23 (2018), 1–30.
Mixing times of critical two-dimensional Potts models. Abstract
We study dynamical aspects of the $q$-state Potts model on an $n\times n$ box at its critical $\beta_c(q)$. Heat-bath Glauber dynamics and cluster dynamics such as Swendsen–Wang (that circumvent low-temperature bottlenecks) are all expected to undergo ``critical slowdowns'' in the presence of periodic boundary conditions: the inverse spectral gap, which in the subcritical regime is $O(1)$, should at criticality be polynomial in $n$ for $1< q \leq 4$, and exponential in $n$ for $q>4$ in accordance with the predicted discontinuous phase transition. This was confirmed for $q=2$ (the Ising model) by the second author and Sly, and for sufficiently large $q$ by Borgs et al.
Here we show that the following holds for the critical Potts model on the torus: for $q=3$, the inverse gap of Glauber dynamics is $n^{O(1)}$; for $q=4$, it is at most $n^{O(\log n)}$; and for every $q>4$ in the phase-coexistence regime, the inverse gaps of both Glauber dynamics and Swendsen–Wang dynamics are exponential in $n$.
For free boundary conditions and large $q$, we show that the dynamics at criticality is faster than on the torus (unlike the Ising model where free/periodic boundary conditions induce similar dynamical behaviors at all temperatures): the inverse gap of Glauber dynamics is at most $\exp(n^{1/2+o(1)})$, and for Swendsen–Wang it is $\exp(n^{o(1)})$.
Communications in Pure and Applied Mathematics 71 (2018), no. 5, 994–1046.
Random walks on the random graph. Abstract
We study random walks on the giant component of the Erdős–Rényi random graph $\mathcal{G}(n, p)$ where $p = \lambda/n$ for $\lambda > 1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order $\log^2 n$. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to $O(\log n)$ and concentrates it (the cutoff phenomenon occurs): the typical mixing is at $(\nu \mathbf{d})^{-1} \log n \pm (\log n)^{1/2+o(1)}$, where $\nu$ and $\mathbf{d}$ are the speed of random walk and dimension of harmonic measure on a Poisson($\lambda$)-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
Annals of Probability 46 (2018), no. 1, 456–490.
Universality of cutoff for the Ising model. Abstract
On any locally-finite geometry, the stochastic Ising model is known to be contractive when the inverse-temperature $\beta$ is small enough, via classical results of Dobrushin and of Holley in the 1970's. By a general principle proposed by Peres, the dynamics is then expected to exhibit cutoff. However, so far cutoff for the Ising model has been confirmed mainly for lattices, heavily relying on amenability and log Sobolev inequalities. Without these, cutoff was unknown at any fixed $\beta>0$, no matter how small, even in basic examples such as the Ising model on a binary tree or a random regular graph.
We use the new framework of information percolation to show that, in any geometry, there is cutoff for the Ising model at high enough temperatures. Precisely, on any sequence of graphs with maximum degree $d$, the Ising model has cutoff provided that $\beta<\kappa/d$ for some absolute constant $\kappa$ (a result which, up to the value of $\kappa$, is best possible). Moreover, the cutoff location is established as the time at which the sum of squared magnetizations drops to 1, and the cutoff window is $O(1)$, just as when $\beta=0$.
Finally, the mixing time from almost every initial state is not more than a factor of $1+\epsilon_\beta$ faster then the worst one (with $\epsilon_\beta\to0$ as $\beta\to 0$), whereas the uniform starting state is at least $2-\epsilon_\beta$ times faster.
Annals of Probability 45 (2017), no. 6A, 3664–3696.
Upper tails and independence polynomials in random graphs. Abstract
The upper tail problem in the Erdős–Rényi random graph $G\sim\mathcal{G}_{n,p}$ asks to estimate the probability that the number of copies of a graph $H$ in $G$ exceeds its expectation by a factor $1+\delta$. Chatterjee and Dembo (2014) showed that in the sparse regime of $p\to 0$ as $n\to\infty$ with $p \geq n^{-\alpha}$ for an explicit $\alpha=\alpha_H>0$, this problem reduces to a natural variational problem on weighted graphs, which was thereafter asymptotically solved by two of the authors in the case where $H$ is a clique.
Here we extend the latter work to any fixed graph $H$ and determine a function $c_H(\delta)$ such that, for $p$ as above and any fixed $\delta>0$, the upper tail probability is $\exp[-(c_H(\delta)+o(1))n^2 p^\Delta \log(1/p)]$, where $\Delta$ is the maximum degree of $H$. As it turns out, the leading order constant in the large deviation rate function, $c_H(\delta)$, is governed by the independence polynomial of $H$, defined as $P_H(x)=\sum i_H(k) x^k $ where $i_H(k)$ is the number of independent sets of size $k$ in $H$. For instance, if $H$ is a regular graph on $m$ vertices, then $c_H(\delta)$ is the minimum between $\frac12 \delta^{2/m}$ and the unique positive solution of $P_H(x) = 1+\delta$.
Advances in Mathematics 319 (2017), 313–347.
On the variational problem for upper tails in sparse random graphs. Abstract
What is the probability that the number of triangles in $\mathcal{G}_{n,p}$, the Erdős–Rényi random graph with edge density $p$, is at least twice its mean? Writing it as $\exp[- r(n,p)]$, already the order of the rate function $r(n,p)$ was a longstanding open problem when $p=o(1)$, finally settled in 2012 by Chatterjee and by DeMarco and Kahn, who independently showed that $r(n,p)\asymp n^2p^2 \log (1/p)$ for $p \gtrsim \frac{\log n}n$; the exact asymptotics of $r(n,p)$ remained unknown.
The following variational problem can be related to this large deviation question at $p\gtrsim \frac{\log n}n$: for $\delta>0$ fixed, what is the minimum asymptotic $p$-relative entropy of a weighted graph on $n$ vertices with triangle density at least $(1+\delta)p^3$? A beautiful large deviation framework of Chatterjee and Varadhan (2011) reduces upper tails for triangles to a limiting version of this problem for fixed $p$. A very recent breakthrough of Chatterjee and Dembo extended its validity to $n^{-\alpha}\ll p \ll 1$ for an explicit $\alpha>0$, and plausibly it holds in all of the above sparse regime.
In this note we show that the solution to the variational problem is $\min\{\frac12 \delta^{2/3}\,,\, \frac13 \delta\}$ when $n^{-1/2}\ll p \ll 1$ vs. $\frac12 \delta^{2/3}$ when $n^{-1} \ll p\ll n^{-1/2}$ (the transition between these regimes is expressed in the count of triangles minus an edge in the minimizer). From the results of Chatterjee and Dembo, this shows for instance that the probability that $\mathcal{G}_{n,p}$ for $ n^{-\alpha} \leq p \ll 1$ has twice as many triangles as its expectation is $\exp[-r(n,p)]$ where $r(n,p)\sim \frac13 n^2 p^2\log(1/p)$. Our results further extend to $k$-cliques for any fixed $k$, as well as give the order of the upper tail rate function for an arbitrary fixed subgraph when $p\geq n^{-\alpha}$.
Random Structures and Algorithms 50 (2017), no. 3, 420–436.
Cycle factors and renewal theory. Abstract
For which values of $k$ does a uniformly chosen $3$-regular graph $G$ on $n$ vertices typically contain $ n/k$ vertex-disjoint $k$-cycles (a $k$-cycle factor)? To date, this has been answered for $k=n$ and for $k \ll \log n$; the former, the Hamiltonicity problem, was finally answered in the affirmative by Robinson and Wormald in 1992, while the answer in the latter case is negative since with high probability (w.h.p.) most vertices do not lie on $k$-cycles.
A major role in our study of this problem is played by renewal processes without replacement, where one wishes to estimate the probability that in a uniform permutation of a given a set of positive integers, the partial sums hit a designated target integer. Using sharp tail estimates for these renewal processes, which may be of independent interest, we settle the cycle factor problem completely: the ``threshold" for a $k$-cycle factor in $G$ as above is $\kappa_0 \log_2 n$ with $\kappa_0=[1-\frac12\log_2 3]^{-1}\approx 4.82$.
Precisely, $G$ contains a $k$-cycle factor w.h.p. if $k\geq K_0(n):= \lceil \kappa_0 \log_2(2n/e)\rceil$ and w.h.p. does not contain one if $k< K_0(n)-\log^2 n/n$. Thus, for most values of $n$ the threshold concentrates on the single integer $K_0(n)$. As a byproduct, we confirm the ``Comb Conjecture,'' an old problem concerning the embedding of certain spanning trees in the random graph $\mathcal{G}(n,p)$.
Communications in Pure and Applied Mathematics 70 (2017), no. 2, 289–339.
Cutoff on all Ramanujan graphs. Abstract
We show that on every Ramanujan graph $G$, the simple random walk exhibits cutoff: when $G$ has $n$ vertices and degree $d$, the total-variation distance of the walk from the uniform distribution at time $t=\frac{d}{d-2}\log_{d-1} n + s\sqrt{\log n}$ is asymptotically $\mathbb{P}(Z > c\, s)$ where $Z$ is a standard normal variable and $c=c(d)$ is an explicit constant. Furthermore, for all $1 \leq p \leq \infty$, $d$-regular Ramanujan graphs minimize the asymptotic $L^p$-mixing time for SRW among all $d$-regular graphs. Our proof also shows that, for every vertex $x$ in $G$ as above, its distance from $n-o(n)$ of the vertices is asymptotically $\log_{d-1} n$.
Geometric and Functional Analysis 26 (2016), no. 4, 1190–1216.
Harmonic pinnacles in the Discrete Gaussian model. Abstract
The 2D Discrete Gaussian model gives each height function $\eta : \mathbb{Z}^2\to\mathbb{Z}$ a probability proportional to $\exp(-\beta \mathcal{H}(\eta))$, where $\beta$ is the inverse-temperature and $\mathcal{H}(\eta) = \sum_{x\sim y}(\eta_x-\eta_y)^2$ sums over nearest-neighbor bonds. We consider the model at large fixed $\beta$, where it is flat unlike its continuous analog (the Gaussian Free Field).
We first establish that the maximum height in an $L\times L$ box with 0 boundary conditions concentrates on two integers $M,M+1$ with $M\sim \sqrt{(1/2\pi\beta)\log L\log\log L}$. The key is a large deviation estimate for the height at the origin in $\mathbb{Z}^2$, dominated by ``harmonic pinnacles'', integer approximations of a harmonic variational problem. Second, in this model conditioned on $\eta\geq 0$ (a floor), the average height rises, and in fact the height of almost all sites concentrates on levels $H,H+1$ where $H\sim M/\sqrt{2}$.
This in particular pins down the asymptotics, and corrects the order, in results of Bricmont, El-Mellouki and Fröhlich (1986), where it was argued that the maximum and the height of the surface above a floor are both of order $\sqrt{\log L}$.
Finally, our methods extend to other classical surface models (e.g., restricted SOS), featuring connections to $p$-harmonic analysis and alternating sign matrices.
Communications in Mathematical Physics 344 (2016), no. 3, 673–717.
The threshold for combs in random graphs. Abstract
For $k\mid n$ let $Comb_{n,k}$ denote the tree consisting of an $(n/k)$-vertex path with disjoint $k$-vertex paths beginning at each of its vertices. An old conjecture says that for any $k=k(n)$ the threshold for the random graph $\mathcal{G}(n,p)$ to contain $Comb_{n,k}$ is at $p\asymp \frac{\log n}n$. Here we verify this for $k \leq C\log n$ with any fixed $C>0$. In a companion paper, using very different methods, we treat the complementary range, proving the conjecture for $k\geq \kappa_0 \log n$ (with $\kappa_0\approx 4.82$).
Random Structures and Algorithms 48 (2016), no. 4, 794–802.
Information percolation and cutoff for the stochastic Ising model. Abstract
We introduce a new framework for analyzing Glauber dynamics for the Ising model. The traditional approach for obtaining sharp mixing results has been to appeal to estimates on spatial properties of the stationary measure from within a multi-scale analysis of the dynamics. Here we propose to study these simultaneously by examining ``information percolation'' clusters in the space-time slab.
Using this framework, we obtain new results for the Ising model on $(\mathbb{Z}/n\mathbb{Z})^d$ throughout the high temperature regime: total-variation mixing exhibits cutoff with an $O(1)$-window around the time at which the magnetization is the square-root of the volume. (Previously, cutoff in the full high temperature regime was only known for $d\leq 2$, and only with an $O(\log\log n)$-window.)
Furthermore, the new framework opens the door to understanding the effect of the initial state on the mixing time. We demonstrate this on the 1D Ising model, showing that starting from the uniform (``disordered'') initial distribution asymptotically halves the mixing time, whereas almost every deterministic starting state is asymptotically as bad as starting from the (``ordered'') all-plus state.
Journal of the American Mathematical Society (JAMS) 29 (2016), 729–774.
Scaling limit and cube-root fluctuations in SOS surfaces above a wall. Abstract
Consider the classical (2+1)-dimensional Solid-On-Solid model above a hard wall on an $L\times L$ box of $\mathbb{Z}^2$. The model describes a crystal surface by assigning a non-negative integer height $\eta_x$ to each site $x$ in the box and 0 heights to its boundary. The probability of a surface configuration $\eta$ is proportional to $\exp(-\beta \mathcal{H}(\eta))$, where $\beta$ is the inverse-temperature and $\mathcal{H}(\eta)$ sums the absolute values of height differences between neighboring sites.
We give a full description of the shape of the SOS surface for low enough temperatures. First we show that with high probability the height of almost all sites is concentrated on two levels, $H(L)=\lfloor (1/4\beta)\log L\rfloor$ and $H(L)-1$. Moreover, for most values of $L$ the height is concentrated on the single value $H(L)$. Next, we study the ensemble of level lines corresponding to the heights $(H(L),H(L)-1,...)$. We prove that w.h.p. there is a unique macroscopic level line for each height. Furthermore, when taking a diverging sequence of system sizes $L_k$, the rescaled macroscopic level line at height $H(L_k)-n$ has a limiting shape if the fractional parts of $(1/4\beta)\log L_k$ converge to a noncritical value. The scaling limit is an explicit convex subset of the unit square $Q$ and its boundary has a flat component on the boundary of $Q$. Finally, the highest macroscopic level line has $L_k^{1/3+o(1)}$ fluctuations along the flat part of the boundary of its limiting shape.
Journal of the European Mathematical Society (JEMS) 18 (2016), no. 5, 931–995.
Strong noise sensitivity and random graphs. Abstract
The noise sensitivity of a Boolean function describes its likelihood to flip under small perturbations of its input. Introduced in the seminal work of Benjamini, Kalai and Schramm (1999), it was there shown to be governed by the first level of Fourier coefficients in the central case of monotone functions at a constant critical probability $p_c$.
Here we study noise sensitivity and a natural stronger version of it, addressing the effect of noise given a specific witness in the original input. Our main context is the Erdős–Rényi random graph, where already the property of containing a given graph is sufficiently rich to separate these notions. In particular, our analysis implies (strong) noise sensitivity in settings where the BKS criterion involving the first Fourier level does not apply, e.g., when $p_c \to 0$ polynomially fast in the number of variables.
Annals of Probability 43 (2015), no. 6, 3239–3278.
Random triangle removal. Abstract
Starting from a complete graph on $n$ vertices, repeatedly delete the edges of a uniformly chosen triangle. This stochastic process terminates once it arrives at a triangle-free graph, and the fundamental question is to estimate the final number of edges (equivalently, the time it takes the process to finish, or how many edge-disjoint triangles are packed via the random greedy algorithm). Bollobás and Erdős (1990) conjectured that the expected final number of edges has order $n^{3/2}$. An upper bound of $o(n^2)$ was shown by Spencer (1995) and independently by Rödl and Thoma (1996). Several bounds were given for variants and generalizations (e.g., Alon, Kim and Spencer (1997) and Wormald (1999)), while the best known upper bound for the original question of Bollobás and Erdős was $n^{7/4+o(1)}$ due to Grable (1997). No nontrivial lower bound was available.
Here we prove that with high probability the final number of edges in random triangle removal is equal to $n^{3/2+o(1)}$, thus confirming the $3/2$ exponent conjectured by Bollobás and Erdős and matching the predictions of Gordon, Kuperberg, Patashnik, and Spencer (1996). For the upper bound, for any fixed $\epsilon>0$ we construct a family of $\exp(O(1/\epsilon))$ graphs by gluing $O(1/\epsilon)$ triangles sequentially in a prescribed manner, and dynamically track the number of all homomorphisms from them, rooted at any two vertices, up to the point where $n^{3/2+\epsilon}$ edges remain. A system of martingales establishes concentration for these random variables around their analogous means in a random graph with corresponding edge density, and a key role is played by the self-correcting nature of the process. The lower bound builds on the estimates at that very point to show that the process will typically terminate with at least $n^{3/2-o(1)}$ edges left.
Advances in Mathematics 280 (2015), 379–438.
An exposition to information percolation for the Ising model. Abstract
Information percolation is a new method for analyzing stochastic spin systems through classifying and controlling the clusters of information-flow in the space-time slab. It yielded sharp mixing estimates (cutoff with an $O(1)$-window) for the Ising model on $\mathbb{Z}^d$ up to the critical temperature, as well as results on the effect of initial conditions on mixing. In this expository note we demonstrate the method on lattices (more generally, on any locally-finite transitive graph) at very high temperatures.
Annales de la Faculté des Sciences de Toulouse 29 (2015), no. 4, 745–761.
On replica symmetry of large deviations in random graphs. Abstract
The following question is due to Chatterjee and Varadhan (2011). Fix $0 < p < r <1$ and take $G\sim \mathcal{G}(n,p)$, the Erdős–Rényi random graph with edge density $p$, conditioned to have at least as many triangles as the typical $\mathcal{G}(n,r)$. Is $G$ close in cut-distance to a typical $\mathcal{G}(n,r)$? Via a beautiful new framework for large deviation principles in $\mathcal{G}(n,p)$, Chatterjee and Varadhan gave bounds on the replica symmetric phase, the region of $(p,r)$ where the answer is positive. They further showed that for any small enough $p$ there are at least two phase transitions as $r$ varies.
We settle this question by identifying the replica symmetric phase for triangles and more generally for any fixed $d$-regular graph. By analyzing the variational problem arising from the framework of Chatterjee and Varadhan we show that the replica symmetry phase consists of all $(p,r)$ such that $(r^d,h_p(r))$ lies on the convex minorant of $x\mapsto h_p(x^{1/d})$ where $h_p$ is the rate function of a binomial with parameter $p$. In particular, the answer for triangles involves $h_p(\sqrt{x})$ rather than the natural guess of $h_p(x^{1/3})$ where symmetry was previously known. Analogous results are obtained for linear hypergraphs as well as the setting where the largest eigenvalue of $G\sim\mathcal{G}(n,p)$ is conditioned to exceed the typical value of the largest eigenvalue of $\mathcal{G}(n,r)$. Building on the work of Chatterjee and Diaconis (2012) we obtain additional results on a class of exponential random graphs including a new range of parameters where symmetry breaking occurs. En route we give a short alternative proof of a graph homomorphism inequality due to Kahn (2001) and Galvin and Tetali (2004).
Random Structures and Algorithms 47 (2015), no. 1, 109–146.
Cutoff for the East process. Abstract
The East process is a 1D kinetically constrained interacting particle system, introduced in the physics literature in the early 90's to model liquid-glass transitions. Spectral gap estimates of Aldous and Diaconis in 2002 imply that its mixing time on $L$ sites has order $L$. We complement that result and show cutoff with an $O(\sqrt{L})$-window.
The main ingredient is an analysis of the front of the process (its rightmost zero in the setup where zeros facilitate updates to their right). One expects the front to advance as a biased random walk, whose normal fluctuations would imply cutoff with an $O(\sqrt{L})$-window. The law of the process behind the front plays a crucial role: Blondel showed that it converges to an invariant measure $\nu$, on which very little is known. Here we obtain quantitative bounds on the speed of convergence to $\nu$, finding that it is exponentially fast. We then derive that the increments of the front behave as a stationary mixing sequence of random variables, and a Stein-method based argument of Bolthausen (`82) implies a CLT for the location of the front, yielding the cutoff result.
Finally, we supplement these results by a study of analogous kinetically constrained models on trees, again establishing cutoff, yet this time with an $O(1)$-window.
Communications in Mathematical Physics 335 (2015), no. 3, 1287–1322.
Cover time of a random graph with a degree sequence II: Allowing vertices of degree two. Abstract
We study the cover time of a random graph chosen uniformly at random from the set of graphs with vertex set $[n]$ and degree sequence $\textbf{d}=(d_i)_{i=1}^n$. In a previous work, the asymptotic cover time was obtained under a number of assumptions on $\textbf{d}$, the most significant being that $d_i\geq 3$ for all $i$. Here we replace this assumption by $d_i\geq 2$. As a corollary, we establish the asymptotic cover time for the 2-core of the emerging giant component of $\mathcal{G}(n,p)$.
Random Structures and Algorithms 45 (2014), no. 4, 627–674.
Cores of random graphs are born Hamiltonian. Abstract
Let $(G_t)_{t \geq 0}$ be the random graph process ($G_0$ is edgeless and $G_t$ is obtained by adding a uniformly distributed new edge to $G_{t-1}$), and let $\tau_k$ denote the minimum time $t$ such that the $k$-core of $G_t$ (its unique maximal subgraph with minimum degree at least $k$) is nonempty. For any fixed $k\geq 3$ the $k$-core is known to emerge via a discontinuous phase transition, where at time $t=\tau_k$ its size jumps from 0 to linear in the number of vertices with high probability. It is believed that for any $k\geq 3$ the core is Hamiltonian upon creation w.h.p., and Bollobás, Cooper, Fenner and Frieze further conjectured that it in fact admits $\lfloor(k-1)/2\rfloor$ edge-disjoint Hamilton cycles. However, even the asymptotic threshold for Hamiltonicity of the $k$-core in $\mathcal{G}(n,p)$ was unknown for any $k$. We show here that for any fixed $k\ge 15$ the $k$-core of $G_t$ is w.h.p. Hamiltonian for all $t \geq \tau_k$, i.e., immediately as the $k$-core appears and indefinitely afterwards. Moreover, we prove that for large enough fixed $k$ the $k$-core contains $\lfloor (k-3)/2\rfloor$ edge-disjoint Hamilton cycles w.h.p. for all $t\geq \tau_k$.
Proceedings of the London Mathematical Society 109 (2014), no. 1, 161–188.
Cutoff for general spin systems with arbitrary boundary conditions. Abstract
The cutoff phenomenon describes a sharp transition in the convergence of a Markov chain to equilibrium. In recent work, the authors established cutoff and its location for the stochastic Ising model on the $d$-dimensional torus $(\mathbb{Z}/n\mathbb{Z})^d$ for any $d\geq 1$. The proof used the symmetric structure of the torus and monotonicity in an essential way.
Here we enhance the framework and extend it to general geometries, boundary conditions and external fields to derive a cutoff criterion that involves the growth rate of balls and the log-Sobolev constant of the Glauber dynamics. In particular, we show there is cutoff for stochastic Ising on any sequence of bounded-degree graphs with sub-exponential growth under arbitrary external fields provided the inverse log-Sobolev constant is bounded. For lattices with homogenous boundary, such as all-plus, we identify the cutoff location explicitly in terms of spectral gaps of infinite-volume dynamics on half-plane intersections. Analogous results establishing cutoff are obtained for non-monotone spin-systems at high temperatures, including the gas hard-core model, the Potts model, the anti-ferromagnetic Potts model and the coloring model.
Communications in Pure and Applied Mathematics 67 (2014), no. 6, 982–1027.
Dynamics of 2+1 dimensional SOS surfaces above a wall: slow mixing induced by entropic repulsion. Abstract
We study the Glauber dynamics for the (2+1)D Solid-On-Solid model above a hard wall and below a far away ceiling, on an $L \times L$ box of $\Bbb Z^2$ with zero boundary conditions, at large inverse-temperature $\beta$. It was shown by Bricmont, El-Mellouki and Fröhlich (1986) that the floor constraint induces an entropic repulsion effect which lifts the surface to an average height $H \asymp (1/\beta)\log L$. As an essential step in understanding the effect of entropic repulsion on the Glauber dynamics we determine the equilibrium height $H$ to within an additive constant: $H=(1/4\beta)\log L+O(1)$. We then show that starting from zero initial conditions the surface rises to its final height $H$ through a sequence of metastable transitions between consecutive levels. The time for a transition from height $h=aH $, $a\in (0,1)$, to height $h+1$ is roughly $\exp(c L^a)$ for some constant $c>0$. In particular, the mixing time of the dynamics is exponentially large in $L$, i.e., $T_{\mathrm{mix}} \geq e^{c L}$. We also provide the matching upper bound $T_{\mathrm{mix}} \leq e^{c' L}$, requiring a challenging analysis of the statistics of height contours at low temperature and new coupling ideas and techniques. Finally, to emphasize the role of entropic repulsion we show that without a floor constraint at height zero the mixing time is no longer exponentially large in $L$.
Annals of Probability 42 (2014), no. 4, 1516–1589.
Anatomy of the giant component: The strictly supercritical regime. Abstract
In a recent work of the authors and Kim, we derived a complete description of the largest component of the Erdős–Rényi random graph $\mathcal{G}(n,p)$ as it emerges from the critical window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to\infty$ and $\epsilon=o(1)$, in terms of a tractable contiguous model. Here we provide the analogous description for the supercritical giant component, i.e., the largest component of $\mathcal{G}(n,p)$ for $p = \lambda/n$ where $\lambda>1$ is fixed. The contiguous model is roughly as follows: Take a random degree sequence and sample a random multigraph with these degrees to arrive at the kernel; Replace the edges by paths whose lengths are i.i.d. geometric variables to arrive at the 2-core; Attach i.i.d. Poisson Galton-Watson trees to the vertices for the final giant component. As in the case of the emerging giant, we obtain this result via a sequence of contiguity arguments at the heart of which are Kim's Poisson-cloning method and the Pittel-Wormald local limit theorems.
European Journal of Combinatorics 35 (2014), 155–168.
Cutoff for the Ising model on the lattice. Abstract
Introduced in 1963, Glauber dynamics is one of the most practiced and extensively studied methods for sampling the Ising model on lattices. It is well known that at high temperatures, the time it takes this chain to mix in $L^1$ on a system of size $n$ is $O(\log n)$. Whether in this regime there is cutoff, i.e. a sharp transition in the $L^1$-convergence to equilibrium, is a fundamental open problem: If so, as conjectured by Peres, it would imply that mixing occurs abruptly at $(c+o(1))\log n$ for some fixed $c > 0$, thus providing a rigorous stopping rule for this MCMC sampler. However, obtaining the precise asymptotics of the mixing and proving cutoff can be extremely challenging even for fairly simple Markov chains. Already for the one-dimensional Ising model, showing cutoff is a longstanding open problem.
We settle the above by establishing cutoff and its location at the high temperature regime of the Ising model on the lattice with periodic boundary conditions. Our results hold for any dimension and at any temperature where there is strong spatial mixing: For $\mathbb{Z}^2$ this carries all the way to the critical temperature. Specifically, for fixed $d \geq 1$, the continuous-time Glauber dynamics for the Ising model on $(\mathbb{Z}/n\mathbb{Z})^d$ with periodic boundary conditions has cutoff at $(d/2\lambda_\infty)\log n$ where $\lambda_\infty$ is the spectral gap of the dynamics on the infinite-volume lattice. To our knowledge, this is the first time where cutoff is shown for a Markov chain where even understanding its stationary distribution is limited.
The proof hinges on a new technique for translating $L^1$-mixing to $L^2$-mixing of projections of the chain, which enables the application of logarithmic-Sobolev inequalities. The technique is general and carries to other monotone and anti-monotone spin-systems, e.g. gas hard-core, Potts, anti-ferromagentic Ising, arbitrary boundary conditions, etc.
Inventiones Mathematicae 191 (2013), no. 3, 719–755.
Longest cycles in sparse random digraphs. Abstract
Long paths and cycles in sparse random graphs and digraphs were studied intensively in the 1980's. It was finally shown by Frieze in 1986 that the random graph $\mathcal{G}(n,p)$ with $p=c/n$ has a cycle on at all but at most $(1+\epsilon)ce^{-c}n$ vertices with high probability, where $\epsilon=\epsilon(c)\to 0$ as $c\to\infty$. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph $\mathcal{D}(n,p)$ no tight result was known and the best estimate was a factor of $c/2$ away from the corresponding lower bound. In this work we close this gap and show that the random digraph $\mathcal{D}(n,p)$ with $p=c/n$ has a cycle containing all but $(2+\epsilon)e^{-c}n$ vertices w.h.p., where $\epsilon=\epsilon(c)\to 0$ as $c\to\infty$. This is essentially tight since w.h.p. such a random digraph contains $(2e^{-c}-o(1))n$ vertices with zero in-degree or out-degree.
Random Structures and Algorithms 43 (2013), no. 1, 1–15.
Quasi-polynomial mixing of the 2D stochastic Ising model with "plus" boundary up to criticality. Abstract
We considerably improve upon the recent result of Martinelli and Toninelli on the mixing time of Glauber dynamics for the \twod Ising model in a box of side $L$ at low temperature and with random boundary conditions whose distribution $\mathbf{P}$ stochastically dominates the extremal plus phase. An important special case is when $\mathbf{P}$ is concentrated on the homogeneous all-plus configuration, where the mixing time $T_{\mathrm{mix}}$ is conjectured to be polynomial in $L$. In [MT] it was shown that for a large enough inverse-temperature $\beta$ and any $\epsilon >0$ there exists $c=c(\beta,\epsilon)$ such that $\lim_{L\to\infty}\mathbf{P}(T_{\mathrm{mix}} \geq \exp({cL^\epsilon})) =0$. In particular, for the all-plus boundary conditions and $\beta$ large enough $T_{\mathrm{mix}} \leq \exp({cL^\epsilon})$.
Here we show that the same conclusions hold for all $\beta$ larger than the critical value $\beta_c$ and with $\exp({cL^\epsilon})$ replaced by $L^{c \log L }$ (i.e. quasi-polynomial mixing). The key point is a modification of the inductive scheme of [MT] together with refined equilibrium estimates that hold up to criticality, obtained via duality and random-line representation tools for the Ising model. In particular, we establish new precise bounds on the law of Peierls contours which quantitatively sharpen the Brownian bridge picture established e.g. in [Greenberg-Ioffe (2005)], [Higuchi (1979)], [Hryniv (1998)].
Journal of the European Mathematical Society (JEMS) 15 (2013), no. 2, 339–386.
Stochastic coalescence in logarithmic time. Abstract
The following distributed coalescence protocol was introduced by Dahlia Malkhi in 2006 motivated by applications in social networking. Initially there are $n$ agents wishing to coalesce into one cluster via a decentralized stochastic process, where each round is as follows: Every cluster flips a fair coin to dictate whether it is to issue or accept requests in this round. Issuing a request amounts to contacting a cluster randomly chosen proportionally to its size. A cluster accepting requests is to select an incoming one uniformly (if there are such) and merge with that cluster. Empirical results by Fernandess and Malkhi suggested the protocol concludes in $O(\log n)$ rounds with high probability, whereas numerical estimates by Oded Schramm, based on an ingenious analytic approximation, suggested that the coalescence time should be super-logarithmic.
Our contribution is a rigorous study of the stochastic coalescence process with two consequences. First, we confirm that the above process indeed requires super-logarithmic time w.h.p., where the inefficient rounds are due to oversized clusters that occasionally develop. Second, we remedy this by showing that a simple modification produces an essentially optimal distributed protocol: If clusters favor their smallest incoming merge request then the process does terminate in $O(\log n)$ rounds w.h.p., and simulations show that the new protocol readily outperforms the original one. Our upper bound hinges on a potential function involving the logarithm of the number of clusters and the cluster-susceptibility, carefully chosen to form a supermartingale. The analysis of the lower bound builds upon the novel approach of Schramm which may find additional applications: Rather than seeking a single parameter that controls the system behavior, instead one approximates the system by the Laplace transform of the entire cluster-size distribution.
Annals of Applied Probability 23 (2013), no. 2, 492–528.
Preliminary version appeared in the Proc. of the 23rd annual ACM-SIAM SODA (2012), 541–551.
Index coding via linear programming. Abstract
Index Coding has received considerable attention recently motivated in part by applications such as fast video-on-demand and efficient communication in wireless networks and in part by its connection to Network Coding. Optimal encoding schemes and efficient heuristics were studied in various settings, while also leading to new results for Network Coding such as improved gaps between linear and non-linear capacity as well as hardness of approximation. The basic setting of Index Coding encodes the side-information relation, the problem input, as an undirected graph and the fundamental parameter is the broadcast rate $\beta$, the average communication cost per bit for sufficiently long messages (i.e. the non-linear vector capacity). Recent nontrivial bounds on $\beta$ were derived from the study of other Index Coding capacities (e.g. the scalar capacity $\beta_1$) by Bar-Yossef et al (2006), Lubetzky and Stav (2007) and Alon et al (2008). However, these indirect bounds shed little light on the behavior of $\beta$: there was no known polynomial-time algorithm for approximating $\beta$ in a general network to within a nontrivial (i.e. $o(n)$) factor, and the exact value of $\beta$ remained unknown for any graph where Index Coding is nontrivial.
Our main contribution is a direct information-theoretic analysis of the broadcast rate $\beta$ using linear programs, in contrast to previous approaches that compared $\beta$ with graph-theoretic parameters. This allows us to resolve the aforementioned two open questions. We provide a polynomial-time algorithm with a nontrivial approximation ratio for computing $\beta$ in a general network along with a polynomial-time decision procedure for recognizing instances with $\beta=2$. In addition, we pinpoint $\beta$ precisely for various classes of graphs (e.g. for various Cayley graphs of cyclic groups) thereby simultaneously improving the previously known upper and lower bounds for these graphs. Via this approach we construct graphs where the difference between $\beta$ and its trivial lower bound is linear in the number of vertices and ones where $\beta$ is uniformly bounded while its upper bound derived from the naive encoding scheme is polynomially worse.
IEEE Transactions on Information Theory 59 (2013), no. 9, 5811–5823.
The shape of the (2+1)D SOS surface above a wall. Abstract
We give a full description for the shape of the classical (2+1)D Solid-On-Solid model above a wall, introduced by Temperley (1952). On an $L\times L$ box at a large inverse-temperature $\beta$ the height of most sites concentrates on a single level $h = \lfloor (1/4\beta)\log L\rfloor$ for most values of $L$. For a sequence of diverging boxes the ensemble of level lines of heights $(h,h-1,...)$ has a scaling limit in Hausdorff distance iff the fractional parts of $(1/4\beta)\log L$ converge to a noncritical value. The scaling limit is explicitly given by nested distinct loops formed via translates of Wulff shapes. Finally, the $h$-level lines feature $L^{1/3+o(1)}$ fluctuations from the side boundaries.
Comptes Rendus Mathematique 350 (2012), no. 13–14, 703–706.
Critical Ising on the square lattice mixes in polynomial time. Abstract
The Ising model is widely regarded as the most studied model of spin-systems in statistical physics. The focus of this paper is its dynamic (stochastic) version, the Glauber dynamics, introduced in 1963 and by now the most popular means of sampling the Ising measure. Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the dynamics on $\mathbb{Z}^2$ everywhere except at criticality. While the critical behavior of the Ising model has long been the focus for physicists, mathematicians have only recently developed an understanding of its critical geometry with the advent of SLE, CLE and new tools to study conformally invariant systems.
A rich interplay exists between the static and dynamic models. At the static phase-transition for Ising, the dynamics is conjectured to undergo a critical slowdown: At high temperature the inverse-gap is $O(1)$, at the critical $\beta_c$ it is polynomial in the side-length and at low temperature it is exponential in it. A seminal series of papers verified this on $\mathbb{Z}^2$ except at $\beta=\beta_c$ where the behavior remained a challenging open problem.
Here we establish the first rigorous polynomial upper bound for the critical mixing, thus confirming the critical slowdown for the Ising model in $\mathbb{Z}^2$. Namely, we show that on a finite box with arbitrary (e.g. fixed, free, periodic) boundary conditions, the inverse-gap at $\beta=\beta_c$ is polynomial in the side-length. The proof harnesses recent understanding of the scaling limit of critical Fortuin-Kasteleyn representation of the Ising model together with classical tools from the analysis of Markov chains.
Communications in Mathematical Physics 313 (2012), no. 3, 815–836.
Mixing time of near-critical random graphs. Abstract
Let $\mathcal{C}_1$ be the largest component of the Erdős–Rényi random graph $\mathcal{G}(n,p)$. The mixing time of random walk on $\mathcal{C}_1$ in the strictly supercritical regime, $p=c/n$ with fixed $c > 1$, was shown to have order $\log^2 n$ by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In the critical window, $p=\frac{1+\epsilon}n$ where $\lambda = \epsilon^3 n$ is bounded, Nachmias and Peres proved that the mixing time on $\mathcal{C}_1$ is of order $n$. However, it was unclear how to interpolate between these results, and estimate the mixing time as the giant component emerges from the critical window. Indeed, even the asymptotics of the diameter of $\mathcal{C}_1$ in this regime were only recently obtained by Riordan and Wormald, as well as the present authors and Kim.
In this paper we show that for $p=\frac{1+\epsilon}n$ with $\lambda = \epsilon^3 n \to \infty$ and $\lambda=o(n)$, the mixing time on $\mathcal{C}_1$ is with high probability of order $(n/\lambda)\log^2 \lambda$. In addition, we show that this is the order of the largest mixing time over all components, both in the slightly supercritical and in the slightly subcritical regime (i.e., $p=\frac{1-\epsilon}n$ with $\lambda$ as above).
Annals of Probability 40 (2012), no. 3, 979–1008.
Glauber Dynamics for the mean-field Potts Model. Abstract
We study Glauber dynamics for the mean-field (Curie-Weiss) Potts model with $q\geq 3$ states and show that it undergoes a critical slowdown at an inverse-temperature $\beta_s(q)$ strictly lower than the critical $\beta_c(q)$ for uniqueness of the thermodynamic limit. The dynamical critical $\beta_s(q)$ is the spinodal point marking the onset of metastability.
We prove that when $\beta<\beta_s(q)$ the mixing time is asymptotically $C(\beta, q) n \log n$ and the dynamics exhibits the cutoff phenomena, a sharp transition in mixing, with a window of order $n$. At $\beta=\beta_s(q)$ the dynamics no longer exhibits cutoff and its mixing obeys a power-law of order $n^{4/3}$. For $\beta>\beta_s(q)$ the mixing time is exponentially large in $n$. Furthermore, as $\beta \uparrow \beta_s$ with $n$, the mixing time interpolates smoothly from subcritical to critical behavior, with the latter reached at a scaling window of $O(n^{-2/3})$ around $\beta_s$. These results form the first complete analysis of mixing around the critical dynamical temperature — including the critical power law — for a model with a first order phase transition.
Journal of Statistical Physics 149 (2012), no. 3, 432–477.
Sums and products along sparse graphs. Abstract
In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n1+e distinct sums of pairs or that many distinct products, and conjectured a lower bound of n2-o(1). They further proposed a generalization of this problem, in which the sums and products are taken along the edges of a given graph G on n labeled vertices. They conjectured a version of the sum-product theorem for general graphs that have at least n1+e edges.
In this work, we consider sum-product theorems for sparse graphs, and show that this problem has important consequences already when $G$ is a matching (i.e., $n/2$ disjoint edges): Any lower bound of the form $n^{1/2+\delta}$ for its sum-product over the integers implies a lower bound of $n^{1+\delta}$ for the original Erdős–Szemerédi problem.
In contrast, over the reals the minimal sum-product for the matching is $\Theta(\sqrt{n})$, hence this approach has the potential of achieving lower bounds specialized to the integers. We proceed to give lower and upper bounds for this problem in different settings. In addition, we provide tight bounds for sums along expanders.
A key element in our proofs is a reduction from the sum-product of a matching to the maximum number of translates of a set of integers into the perfect squares. This problem was originally studied by Euler, and we obtain a stronger form of Euler's result using elliptic curve analysis.
Israel Journal of Mathematics 188 (2012), no. 1, 353–384.
Spectra of lifted Ramanujan graphs. Abstract
A random $n$-lift of a base graph $G$ is its cover graph $H$ on the vertices $[n]\times V(G)$, where for each edge $u v$ in $G$ there is an independent uniform bijection $\pi$, and $H$ has all edges of the form $(i,u),(\pi(i),v)$. A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.
Let $G$ be a graph with largest eigenvalue $\lambda_1$ and let $\rho$ be the spectral radius of its universal cover. Friedman (2003) proved that every ``new'' eigenvalue of a random lift of $G$ is $O(\rho^{1/2}\lambda_1^{1/2} )$ with high probability, and conjectured a bound of $\rho+o(1)$, which would be tight by results of Lubotzky and Greenberg (1995). Linial and Puder (2008) improved Friedman's bound to $O(\rho^{2/3}\lambda_1^{1/3})$. For $d$-regular graphs, where $\lambda_1=d$ and $\rho=2\sqrt{d-1}$, this translates to a bound of $O(d^{2/3})$, compared to the conjectured $2\sqrt{d-1}$.
Here we analyze the spectrum of a random $n$-lift of a $d$-regular graph whose nontrivial eigenvalues are all at most $\lambda$ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is $O((\lambda \vee \rho) \log \rho)$. This result is tight up to a logarithmic factor, and for $\lambda \leq d^{2/3-\epsilon}$ it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical $n$-lift of a Ramanujan graph is nearly Ramanujan.
Advances in Mathematics 227 (2011), no. 4, 1612–1645.
Anatomy of a young giant component in the random graph. Abstract
We provide a complete description of the giant component of the Erdős–Rényi random graph $\mathcal{G}(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.
Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component $\mathcal{C}_1$ is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for $\mathcal{C}_1$). Let $Z$ be normal with mean $\frac23 \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random $3$-regular graph on $2\lfloor Z\rfloor$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d. geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex.
A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.
This description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of $\epsilon$, as well as the mixing time of the random walk on $\mathcal{C}_1$.
Random Structures and Algorithms 39 (2011), no. 2, 139–178.
Lexicographic products and the power of non-linear network coding. Abstract
We introduce a technique for establishing and amplifying gaps between parameters of network coding and index coding. The technique uses linear programs to establish separations between combinatorial and coding-theoretic parameters and applies hypergraph lexicographic products to amplify these separations. This entails combining the dual solutions of the lexicographic multiplicands and proving that they are a valid dual of the product. Our result is general enough to apply to a large family of linear programs. This blend of linear programs and lexicographic products gives a recipe for constructing hard instances in which the gap between combinatorial or coding-theoretic parameters is polynomially large. We find polynomial gaps in cases in which the largest previously known gaps were only small constant factors or entirely unknown. Most notably, we show a polynomial separation between linear and non-linear network coding rates. This involves exploiting a connection between matroids and index coding to establish a previously unknown separation between linear and non-linear index coding rates. We also construct index coding problems with a polynomial gap between the broadcast rate and the trivial lower bound for which no gap was previously known.
Proc. of the 52nd IEEE FOCS (2011), 609–619.
Optimal whitespace synchronization strategies. Abstract
The whitespace-discovery problem describes two parties, Alice and Bob, trying to establish a communication channel over one of a given large segment of whitespace channels. Subsets of the channels are occupied in each of the local environments surrounding Alice and Bob, as well as in the global environment between them (Eve). In the absence of a common clock for the two parties, the goal is to devise time-invariant (stationary) strategies minimizing the synchronization time. This emerged from recent applications in discovery of wireless devices.
We model the problem as follows. There are $N$ channels, each of which is open (unoccupied) with probability $p_1,p_2,q$ independently for Alice, Bob and Eve respectively. Further assume that $N \gg 1 / (p_1 p_2 q)$ to allow for sufficiently many open channels. Both Alice and Bob can detect which channels are locally open and every time-slot each of them chooses one such channel for an attempted sync. One aims for strategies that, with high probability over the environments, guarantee a shortest possible expected sync time depending only on the $p_i$'s and $q$.
Here we provide a stationary strategy for Alice and Bob with a guaranteed expected sync time of $O(1/(p_1 p_2 q^2))$ given that each party also has knowledge of $p_1,p_2,q$. When the parties are oblivious of these probabilities, analogous strategies incur a cost of a poly-log factor, i.e. $\tilde{O}(1/(p_1 p_2 q^2))$. Furthermore, this performance guarantee is essentially optimal as we show that any stationary strategies of Alice and Bob have an expected sync time of at least $\Omega(1/(p_1 p_2 q)^2)$.
Proc. of the 19th European Symposium on Algorithms (ESA) (2011), 713–722.
Explicit expanders with cutoff phenomena. Abstract
The cutoff phenomenon describes a sharp transition in the convergence of an ergodic finite Markov chain to equilibrium. Of particular interest is understanding this convergence for the simple random walk on a bounded-degree expander graph. The first example of a family of bounded-degree graphs where the random walk exhibits cutoff in total-variation was provided only very recently, when the authors showed this for a typical random regular graph. However, no example was known for an explicit (deterministic) family of expanders with this phenomenon. Here we construct a family of cubic expanders where the random walk from a worst case initial position exhibits total-variation cutoff. Variants of this construction give cubic expanders without cutoff, as well as cubic graphs with cutoff at any prescribed time-point.
Electronic Journal of Probability 16 (2011), 419–435.
Giant components in biased graph processes. Abstract
A random graph process, $\mathcal{G}(n)$, is a sequence of graphs on $n$ vertices which begins with the edgeless graph, and where at each step a single edge is added according to a uniform distribution on the missing edges. It is well known that in such a process a giant component (of linear size) typically emerges after $(1+o(1))\frac{n}{2}$ edges (a phenomenon known as ``the double jump''), i.e., at time $t=1$ when using a timescale of $n/2$ edges in each step.
We consider a generalization of this process, $\mathcal{G}_K(n)$, proposed by Itai Benjamini in order to model the spreading of an epidemic. This generalized process gives a weight of size $1$ to missing edges between pairs of isolated vertices, and a weight of size $K \in [0,\infty)$ otherwise. This corresponds to a case where links are added between $n$ initially isolated settlements, where the probability of a new link in each step is biased according to whether or not its two endpoint settlements are still isolated.
Combining methods of Spencer and Wormald (2007) with analytical techniques, we describe the typical emerging time of a giant component in this process, $t_c(K)$, as the singularity point of a solution to a set of differential equations. We proceed to analyze these differential equations and obtain properties of $\mathcal{G}_K$, and in particular, we show that $t_c(K)$ strictly decreases from $\frac{3}{2}$ to $0$ as $K$ increases from $0$ to $\infty$, and that $t_c(K) = \frac{4}{\sqrt{3K}}\left(1 + o(1)\right)$, where the $o(1)$-term tends to $0$ as $K\to\infty$. Numerical approximations of the differential equations agree both with computer simulations of the process $\mathcal{G}_K(n)$ and with the analytical results.
Indiana University Mathematical Journal 59 (2011), no. 6, 1893–1930.
Mixing time of critical Ising model on trees is polynomial in the height. Abstract
In the heat-bath Glauber dynamics for the Ising model on the lattice, physicists believe that the spectral gap of the continuous-time chain exhibits the following behavior. For some critical inverse-temperature $\beta_c$, the inverse-gap is $O(1)$ for $\beta < \beta_c$, polynomial in the surface area for $\beta = \beta_c$ and exponential in it for $\beta > \beta_c$. This has been proved for $\mathbb{Z}^2$ except at criticality. So far, the only underlying geometry where the critical behavior has been confirmed is the complete graph. Recently, the dynamics for the Ising model on a regular tree, also known as the Bethe lattice, has been intensively studied. The facts that the inverse-gap is bounded for $\beta < \beta_c$ and exponential for $\beta > \beta_c$ were established, where $\beta_c$ is the critical spin-glass parameter, and the tree-height $h$ plays the role of the surface area.
In this work, we complete the picture for the inverse-gap of the Ising model on the $b$-ary tree, by showing that it is indeed polynomial in $h$ at criticality. The degree of our polynomial bound does not depend on $b$, and furthermore, this result holds under any boundary condition. We also obtain analogous bounds for the mixing-time of the chain. In addition, we study the near critical behavior, and show that for $\beta > \beta_c$, the inverse-gap and mixing-time are both $\exp[\Theta((\beta-\beta_c) h)]$.
Communications in Mathematical Physics 295 (2010), no. 1, 161–207.
Cutoff phenomena for random walks on random regular graphs. Abstract
The cutoff phenomenon describes a sharp transition in the convergence of a family of ergodic finite Markov chains to equilibrium. Many natural families of chains are believed to exhibit cutoff, and yet establishing this fact is often extremely challenging. An important such family of chains is the random walk on $G(n,d)$, a random $d$-regular graph on $n$ vertices. It is well known that almost every such graph for $d\geq 3$ is an expander, and even essentially Ramanujan, implying a mixing-time of $O(\log n)$. According to a conjecture of Peres, the simple random walk on $G(n,d)$ for such $d$ should then exhibit cutoff w.h.p. As a special case of this, Durrett conjectured that the mixing time of the lazy random walk on a random $3$-regular graph is w.h.p. $(6+o(1))\log_2 n$.
In this work we confirm the above conjectures, and establish cutoff in total-variation, its location and its optimal window, both for simple and for non-backtracking random walks on $G(n,d)$. Namely, for any fixed $d\geq 3$, the simple random walk on $G(n,d)$ w.h.p. has cutoff at $\frac{d}{d-2}\log_{d-1} n$ with window order $\sqrt{\log n}$. Surprisingly, the non-backtracking random walk on $G(n,d)$ w.h.p. has cutoff already at $\log_{d-1} n$ with constant window order. We further extend these results to $\mathcal{G}(n,d)$ for any $d=n^{o(1)}$ that grows with $n$ (beyond which the mixing time is $O(1)$), where we establish concentration of the mixing time on one of two consecutive integers.
Duke Mathematical Journal 153 (2010), no. 3, 475–510.
Hamiltonicity thresholds in Achlioptas processes. Abstract
In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on $n$ labeled vertices. At each round we are presented with $K = K(n)$ edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible.
We show that this problem has three regimes, depending on the value of $K$. For $K = o(\log n)$, the threshold for Hamiltonicity is $(1+o(1))n/(2K)\log n$, i.e., typically we can construct a Hamilton cycle $K$ times faster that in the usual random graph process. When $K = \omega(\log n)$ we can essentially waste almost no edges, and create a Hamilton cycle within $n + o(n)$ rounds with high probability. Finally, in the intermediate regime where $K$ has order $\log n$, the threshold has order $n$ and we obtain upper and lower bounds that differ by a multiplicative factor of 3.
Random Structures and Algorithms 37 (2010), no. 1, 1–24.
Diameters in supercritical random graphs via first passage percolation. Abstract
We study the diameter of $\mathcal{C}_1$, the largest component of the Erdős–Rényi random graph $\mathcal{G}(n,p)$ in the emerging supercritical phase, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$. This parameter was extensively studied for fixed $\epsilon > 0$, yet results for $\epsilon=o(1)$ outside the critical window were only obtained very recently. Prior to this work, Riordan and Wormald gave precise estimates on the diameter, however these did not cover the entire supercritical regime (namely, when $\epsilon^3 n\to\infty$ arbitrarily slowly). Łuczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differed by a factor of $\frac{1000}7$.
We show that throughout the emerging supercritical phase, i.e. for any $\epsilon=o(1)$ with $\epsilon^3n\to\infty$, the diameter of $\mathcal{C}_1$ is with high probability asymptotic to $D(\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. This constitutes the first proof of the asymptotics of the diameter valid throughout this phase. The proof relies on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation. The main advantage of our method is its flexibility. It also implies that in the emerging supercritical phase the diameter of the 2-core of $\mathcal{C}_1$ is w.h.p. asymptotic to $\frac23 D(\epsilon,n)$, and the maximal distance in $\mathcal{C}_1$ between any pair of kernel vertices is w.h.p. asymptotic to $\frac59 D(\epsilon,n)$.
Combinatorics, Probability and Computing 19 (2010), no. 5–6, 729–751.
Total variation cutoff in birth-and-death chains. Abstract
The cutoff phenomenon describes a case where a Markov chain exhibits a sharp transition in its convergence to stationarity. In 1996, Diaconis surveyed this phenomenon, and asked how one could recognize its occurrence in families of finite ergodic Markov chains. In 2004, the third author noted that a necessary condition for cutoff in a family of reversible chains is that the product of the mixing-time and spectral-gap tends to infinity, and conjectured that in many settings, this condition should also be sufficient. Diaconis and Saloff-Coste (2006) verified this conjecture for continuous-time birth-and-death chains, started at an endpoint, with convergence measured in separation. It is natural to ask whether the conjecture holds for these chains in the more widely used total-variation distance.
In this work, we confirm the above conjecture for all continuous-time or lazy discrete-time birth-and-death chains, with convergence measured via total-variation distance. Namely, if the product of the mixing-time and spectral-gap tends to infinity, the chains exhibit cutoff at the maximal hitting time of the stationary distribution median, with a window of at most the geometric mean between the relaxation-time and mixing-time.
In addition, we show that for any lazy (or continuous-time) birth-and-death chain with stationary distribution $\pi$, the separation $1 - p^t(x,y)/\pi(y)$ is maximized when $x,y$ are the endpoints. Together with the above results, this implies that total-variation cutoff is equivalent to separation cutoff in any family of such chains.
Probability Theory and Related Fields 146 (2010), no. 1, 61–85.
Choice-memory tradeoff in allocations. Abstract
In the classical balls-and-bins paradigm, where $n$ balls are placed independently and uniformly in $n$ bins, typically the number of bins with at least two balls in them is $\Theta(n)$ and the maximum number of balls in a bin is $\Theta(\frac{\log n}{\log\log n})$. It is well known that when each round offers $k$ independent uniform options for bins, it is possible to typically achieve a constant maximal load if and only if $k= \Omega(\log n)$. Moreover, it is possible w.h.p. to avoid any collisions between $n/2$ balls if $k>\log_2 n$.
In this work, we extend this into the setting where only $m$ bits of memory are available. We establish a tradeoff between the number of choices $k$ and the memory $m$, dictated by the quantity $km/n$. Roughly put, we show that for $k m \gg n$ one can achieve a constant maximal load, while for $k m \ll n$ no substantial improvement can be gained over the case $k=1$ (i.e., a random allocation).
For any $k = \Omega(\log n)$ and $m=\Omega(\log^2 n)$, one can achieve a constant load w.h.p. if $k m = \Omega(n)$, yet the load is unbounded if $km=o(n)$. Similarly, if $k m > C n$ then $n/2$ balls can be allocated without any collisions w.h.p., whereas for $k m < \epsilon n$ there are typically $\Omega(n)$ collisions. Furthermore, we show that the load is w.h.p. at least $\frac{\log(n/m)}{\log k + \log\log(n/m)}$. In particular, for $k\leq\mathrm{polylog}(n)$, if $m = n^{1-\delta}$ the optimal maximal load is $\Theta(\frac{\log n}{\log\log n})$ (the same as in the case $k=1$), while $m=2n$ suffices to ensure a constant load. Finally, we analyze non-adaptive allocation algorithms and give tight upper and lower bounds for their performance.
Annals of Applied Probability 20 (2010), no. 4, 1470–1511.
Preliminary version appeared in the Proc. of the 50th IEEE FOCS (2009), 230–238.
A note on the random greedy triangle-packing algorithm. Abstract
The random greedy algorithm for constructing a large partial Steiner-Triple-System is defined as follows. We begin with a complete graph on $n$ vertices and proceed to remove the edges of triangles one at a time, where each triangle removed is chosen uniformly at random from the collection of all remaining triangles. This stochastic process terminates once it arrives at a triangle-free graph. In this note we show that with high probability the number of edges in the final graph is at most $ n^{7/4 +o(1)}$.
Journal of Combinatorics 1 (2010), no. 3–4, 477–488.
The mixing time evolution of Glauber dynamics for the mean-field Ising model. Abstract
We consider Glauber dynamics for the Ising model on the complete graph on $n$ vertices, known as the Curie-Weiss model. It is well-known that the mixing-time in the high temperature regime ($\beta < 1$) has order $n\log n$, whereas the mixing-time in the case $\beta > 1$ is exponential in $n$. Recently, Levin, Luczak and Peres proved that for any fixed $\beta < 1$ there is cutoff at time $\frac{1}{2(1-\beta)}n\log n$ with a window of order $n$, whereas the mixing-time at the critical temperature $\beta=1$ is $\Theta(n^{3/2})$. It is natural to ask how the mixing-time transitions from $\Theta(n\log n)$ to $\Theta(n^{3/2})$ and finally to $\exp\left(\Theta(n)\right)$. That is, how does the mixing-time behave when $\beta=\beta(n)$ is allowed to tend to $1$ as $n\to\infty$.
In this work, we obtain a complete characterization of the mixing-time of the dynamics as a function of the temperature, as it approaches its critical point $\beta_c=1$. In particular, we find a scaling window of order $1/\sqrt{n}$ around the critical temperature. In the high temperature regime, $\beta = 1 - \delta$ for some $0 < \delta < 1$ so that $\delta^2 n \to\infty$ with $n$, the mixing-time has order $(n/\delta)\log(\delta^2 n)$, and exhibits cutoff with constant $\frac{1}{2}$ and window size $n/\delta $. In the critical window, $\beta = 1\pm \delta$ where $\delta^2 n$ is $O(1)$, there is no cutoff, and the mixing-time has order $n^{3/2}$. At low temperature, $\beta = 1 + \delta$ for $\delta > 0$ with $\delta^2 n \to\infty$ and $\delta=o(1)$, there is no cutoff, and the mixing time has order mixing time has order $\frac{n}{\delta}\exp\left((\frac{3}{4}+o(1))\delta^2 n\right)$.
Communications in Mathematical Physics 289 (2009), no. 2, 725–764.
Poisson approximation for non-backtracking random walks. Abstract
Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. Alon, Benjamini, Lubetzky and Sodin studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length $n$ on a high-girth $n$-vertex regular expander, is typically $(1+o(1))\frac{\log n}{\log\log n}$, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes.
In this work, we answer the above question by combining a generalized form of Brun's sieve with some extensions of the ideas in Alon et al. Let $N_t$ denote the number of vertices visited precisely $t$ times by a non-backtracking random walk of length $n$ on a regular $n$-vertex expander of fixed degree and girth $g$. We prove that if $g\to\infty$ then for any fixed $t$, $N_t/n$ is typically $1/(e t!)+o(1)$. Furthermore, if $g = \Omega(\log\log n)$ then $N_t / n$ is typically $(1+o(1))/(e t!)$ uniformly over all $t \leq (1-o(1))\frac{\log n}{\log\log n}$ and 0 for all $t \geq (1+o(1))\frac{\log n}{\log\log n}$. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.
Israel Journal of Mathematics 174 (2009), 227–252.
Uniformly cross intersecting families. Abstract
Let $\mathcal{A}$ and $\mathcal{B}$ denote two families of subsets of an $n$-element set. The pair $(\mathcal{A},\mathcal{B})$ is said to be $\ell$-cross-intersecting iff $|A\cap B| = \ell$ for all $A\in\mathcal{A}$ and $B\in\mathcal{B}$. Denote by $P_\ell(n)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ over all such pairs. The best known upper bound on $P_\ell(n)$ is $\Theta(2^n)$, by Frankl and Rödl. For a lower bound, Ahlswede, Cai and Zhang showed, for all $n \geq 2\ell$, a simple construction of an $\ell$-cross-intersecting pair $(\mathcal{A},\mathcal{B})$ with $|\mathcal{A}||\mathcal{B}| = \binom{2\ell}{\ell}2^{n-2\ell}=\Theta(2^n/\sqrt{\ell})$, and conjectured that this is best possible. Consequently, Sgall asked whether or not $P_\ell(n)$ decreases with $\ell$.
In this paper, we confirm the above conjecture of Ahlswede et al. for any sufficiently large $\ell$, implying a positive answer to the above question of Sgall as well. By analyzing the linear spaces of the characteristic vectors of $\mathcal{A},\mathcal{B}$ over $\mathbb{R}$, we show that there exists some $\ell_0>0$, such that $P_\ell(n) \leq \binom{2\ell}{\ell}2^{n-2\ell}$ for all $\ell \geq \ell_0$. Furthermore, we determine the precise structure of all the pairs of families which attain this maximum.
Combinatorica 29 (2009), no. 4, 389–431.
Censored Glauber Dynamics for the mean field Ising Model. Abstract
We study Glauber dynamics for the Ising model on the complete graph on $n$ vertices, known as the Curie-Weiss Model. It is well known that at high temperature ($\beta < 1$) the mixing time is $\Theta(n\log n)$, whereas at low temperature ($\beta > 1$) it is $\exp(\Theta(n))$. Recently, Levin, Luczak and Peres considered a censored version of this dynamics, which is restricted to non-negative magnetization. They proved that for fixed $\beta > 1$, the mixing-time of this model is $\Theta(n\log n)$, analogous to the high-temperature regime of the original dynamics. Furthermore, they showed cutoff for the original dynamics for fixed $\beta<1$. The question whether the censored dynamics also exhibits cutoff remained unsettled.
In a companion paper, we extended the results of Levin et al. into a complete characterization of the mixing-time for the Curie-Weiss model. Namely, we found a scaling window of order $1/\sqrt{n}$ around the critical temperature $\beta_c=1$, beyond which there is cutoff at high temperature. However, determining the behavior of the censored dynamics outside this critical window seemed significantly more challenging.
In this work we answer the above question in the affirmative, and establish the cutoff point and its window for the censored dynamics beyond the critical window, thus completing its analogy to the original dynamics at high temperature. Namely, if $\beta = 1 + \delta$ for some $\delta > 0$ with $\delta^2 n \to \infty$, then the mixing-time has order $(n/\delta)\log(\delta^2 n)$. The cutoff constant is $\left(1/2+[2(\zeta^2 \beta/\delta - 1)]^{-1}\right)$, where $\zeta$ is the unique positive root of $g(x)=\tanh(\beta x)-x$, and the cutoff window has order $n/\delta$.
Journal of Statistical Physics 137 (2009), no. 3, 407–458.
Non-linear index coding outperforming the linear optimum. Abstract
The following source coding problem was introduced by Birk and Kol: a sender holds a word $x\in{0,1}^n$, and wishes to broadcast a codeword to $n$ receivers, $R_1,\ldots,R_n$. The receiver $R_i$ is interested in $x_i$, and has prior side information comprising some subset of the $n$ bits. This corresponds to a directed graph $G$ on $n$ vertices, where $i j$ is an edge iff $R_i$ knows the bit $x_j$. An index code for $G$ is an encoding scheme which enables each $R_i$ to always reconstruct $x_i$, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol (FOCS 2006). They introduced a graph parameter, $\mathrm{minrk}_2(G)$, which completely characterizes the length of an optimal linear index code for $G$. The authors of BBJK showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal.
In this work, we disprove the main conjecture of BBJK in the following strong sense: for any $\epsilon > 0$ and sufficiently large $n$, there is an $n$-vertex graph $G$ so that every linear index code for $G$ requires codewords of length at least $n^{1-\epsilon}$, and yet a non-linear index code for $G$ has a word length of $n^{\epsilon}$. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson.
IEEE Transactions on Information Theory 55 (2009), 3544–3551.
Preliminary version appeared in the Proc. of the 48th IEEE FOCS (2007), 161–167.
Broadcasting with side information. Abstract
A sender holds a word $x$ consisting of $n$ blocks $x_i$, each of $t$ bits, and wishes to broadcast a codeword to $m$ receivers, $R_1,...,R_m$. Each receiver $R_i$ is interested in one block, and has prior side information consisting of some subset of the other blocks. Let $\beta_t$ be the minimum number of bits that has to be transmitted when each block is of length $t$, and let $\beta$ be the limit $\beta = \lim_{t \rightarrow \infty} \beta_t/t$. In words, $\beta$ is the average communication cost per bit in each block (for long blocks). Finding the coding rate $\beta$, for such an informed broadcast setting, generalizes several coding theoretic parameters related to Informed Source Coding on Demand, Index Coding and Network Coding.
In this work we show that usage of large data blocks may strictly improve upon the trivial encoding which treats each bit in the block independently. To this end, we provide general bounds on $\beta_t$, and prove that for any constant $C$ there is an explicit broadcast setting in which $\beta = 2$ but $\beta_1 > C$. One of these examples answers a question of Lubetzky and Stav.
In addition, we provide examples with the following counterintuitive direct-sum phenomena. Consider a union of several mutually independent broadcast settings. The optimal code for the combined setting may yield a significant saving in communication over concatenating optimal encodings for the individual settings. This result also provides new non-linear coding schemes which improve upon the largest known gap between linear and non-linear Network Coding, thus improving the results of Dougherty, Freiling, and Zeger.
The proofs are based on a relation between this problem and results in the study of Witsenhausen's rate, OR graph products, colorings of Cayley graphs, and the chromatic numbers of Kneser graphs.
Proc. of the 49th IEEE FOCS (2008), 823–832.
The isoperimetric constant of the random graph process. Abstract
The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial S$ denotes the set of edges with precisely one end in $S$. A random graph process on $n$ vertices, $\mathcal{G}(t)$, is a sequence of $\binom{n}{2}$ graphs, where $\mathcal{G}(0)$ is the edgeless graph on $n$ vertices, and $\mathcal{G}(t)$ is the result of adding an edge to $\mathcal{G}(t-1)$, uniformly distributed over all the missing edges. We show that in almost every graph process $i(\mathcal{G}(t))$ equals the minimal degree of $\mathcal{G}(t)$ as long as the minimal degree is $o(\log n)$. Furthermore, we show that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically $\Theta(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.
Random Structures and Algorithms 32 (2008), 101–114.
Non-backtracking random walks mix faster. Abstract
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as fast as the mixing rate of the simple random walk. The closer the expander is to a Ramanujan graph, the higher the ratio between the above two mixing rates is.
As an application, we show that if $G$ is a high-girth regular expander on $n$ vertices, then a typical non-backtracking random walk of length $n$ on $G$ does not visit a vertex more than $(1+o(1))\frac{\log n}{\log \log n}$ times, and this result is tight. In this sense, the multi-set of visited vertices is analogous to the result of throwing $n$ balls to $n$ bins uniformly, in contrast to the simple random walk on $G$, which almost surely visits some vertex $\Omega(\log n)$ times.
Communications in Contemporary Mathematics 9 (2007), 585–603.
Privileged users in zero-error transmission over a noisy channel. Abstract
The $k$-th power of a graph $G$ is the graph whose vertex set is $V(G)^k$, where two distinct $k$-tuples are adjacent iff they are equal or adjacent in $G$ in each coordinate. The Shannon capacity of $G$, $c(G)$, is $\lim_{k\to\infty}\alpha(G^k)^{1/k}$, where $\alpha(G)$ denotes the independence number of $G$. When $G$ is the characteristic graph of a channel $\mathcal{C}$, $c(G)$ measures the effective alphabet size of $\mathcal{C}$ in a zero-error protocol. A sum of channels, $\mathcal{C}=\sum_i \mathcal{C}_i$, describes a setting when there are $t\geq 2$ senders, each with his own channel $\mathcal{C}_i$, and each letter in a word can be selected from either of the channels. This corresponds to a disjoint union of the characteristic graphs, $G=\sum_i G_i$.
We show that for any fixed $t$ and any family $F$ of subsets of $T={1,2,...,t}$, there are $t$ graphs $G_1,G_2, ...,G_t$, so that for every subset $I$ of $T$, the Shannon capacity of the disjoint union $\sum_{i \in I} G_i$ is "large" if $I$ contains a member of $F$, and is "small" otherwise.
Combinatorica 27 (2007), 737–743.
Graph powers, Delsarte, Hoffman, Ramsey and Shannon. Abstract
The $k$-th $p$-power of a graph $G$ is the graph on the vertex set $V(G)^k$, where two $k$-tuples are adjacent iff the number of their coordinates which are adjacent in $G$ is not congruent to $0$ modulo $p$. The clique number of powers of $G$ is poly-logarithmic in the number of vertices, thus graphs with small independence numbers in their $p$-powers do not contain large homogenous subsets. We provide algebraic upper bounds for the asymptotic behavior of independence numbers of such powers, settling a previous conjecture of Alon and Lubetzky (2007) up to a factor of $2$. For precise bounds on some graphs, we apply Delsarte's linear programming bound and Hoffman's eigenvalue bound. Finally, we show that for any nontrivial graph $G$, one can point out specific induced subgraphs of large $p$-powers of $G$ with neither a large clique nor a large independent set. We prove that the larger the Shannon capacity of $G^c$ is, the larger these subgraphs are, and if $G$ is the complete graph, then some $p$-power of $G$ matches the bounds of the Frankl-Wilson Ramsey construction, and is in fact a subgraph of a variant of that construction.
SIAM J. Discrete Math 21 (2007), 329–348.
Codes and Xor graph products. Abstract
What is the maximum possible number, $f_3(n)$, of vectors of length $n$ over $\{0,1,2\}$ such that the Hamming distance between every two is even? What is the maximum possible number, $g_3(n)$, of vectors in $\{0,1,2\}^n$ such that the Hamming distance between every two is odd? We investigate these questions, and more general ones, by studying Xor powers of graphs, focusing on their independence number and clique number, and by introducing two new parameters of a graph $G$. Both parameters denote limits of series of either clique numbers or independence numbers of the Xor powers of $G$ (normalized appropriately), and while both limits exist, one of the series grows exponentially as the power tends to infinity, while the other grows linearly. As a special case, it follows that $f_3(n)=\Theta(2^n)$ whereas $g_3(n)=\Theta(n)$.
Combinatorica 27 (2007), 13–33.
Independent sets in tensor graph powers. Abstract
The tensor product of two graphs, $G$ and $H$, has a vertex set $V(G)\times V(H)$ and an edge between $(u,v)$ and $(u',v')$ iff both $u u' \in E(G)$ and $v v' \in E(H)$. Let $A(G)$ denote the limit of the independence ratios of tensor powers of $G$, $\lim \alpha(G^n)/|V(G^n)|$. This parameter was introduced by Brown, Nowakowski and Rall, who showed that $A(G)$ is lower bounded by the vertex expansion ratio of independent sets of $G$. In this note we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products.
J. Graph Theory 54 (2007), 73–87.
Coarse to Over-Fine Optical Flow Estimation. Abstract
We present a readily applicable way to go beyond the accuracy limits of current optical flow estimators. Modern optical flow algorithms employ the coarse to fine approach. We suggest to upgrade this class of algorithms, by adding over-fine interpolated levels to the pyramid. Theoretical analysis of the coarse to over-fine approach explains its advantages in handling flow-field discontinuities and simulations show its benefit for sub-pixel motion. By applying the suggested technique to various multiscale optical flow algorithms, we reduced the estimation error by 10%-30% on the common test sequences. Using the coarse to over-fine technique, we obtain optical flow estimation results that are currently the best for benchmark sequences.
Pattern Recognition 40 (2007), 2496–2503.
The Shannon capacity of a graph and the independence numbers of its powers. Abstract
The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of independence numbers in strong powers of a fixed graph can exhibit a complex structure, implying that the Shannon Capacity of a graph cannot be approximated (up to a sub-polynomial factor of the number of vertices) by any arbitrarily large, yet fixed, prefix of the series. This is true even if this prefix shows a significant increase of the independence number at a given power, after which it stabilizes for a while.
IEEE Transactions on Information Theory 52 (2006), 2172–2176.
The Multicast Bandwidth Advantage in Serving a Web Site. Abstract
Delivering popular web pages to the clients results in high bandwidth and high load on the web servers. A method to overcome this problem is to send these pages, requested by many users, via multicast. In this paper, we provide an analytic criterion to determine which pages to multicast, and analyze the overall saving factor as compared with a unicast delivery. The analysis is based on the well known observation that page popularity follows a Zipf-like distribution. Interestingly, we can obtain closed-form analytical expressions for the saving factor, that show the multicast advantage as a function of the site hit-rate, the allowed latency and the Zipf parameter.
Proc. of 3rd NGC (2001), 88–99.
On two biased graph processes. Abstract
In recent paper the authors considered the generalization $\mathcal{G}^{\vee}_K$ of the Erdős–Rényi random graph process $\mathcal{G}_1$, where instead of adding new edges uniformly, $\mathcal{G}^{\vee}_K$ gives a weight of size $1$ to missing edges between pairs of isolated vertices, and a weight of size $K\in[0,\infty)$ otherwise. This can correspond to the linking of settlements or the spreading of an epidemic. The authors investigate $t^{\vee}_g(K)$, the critical time for the appearance of a giant component as a function of $K$, and prove that $t_g^\vee=\left(1 + o(1)\right)\frac{4}{\sqrt{3K}}$, using a proper timescale.
In this work, we show that a natural variation of the model $\mathcal{G}^{\vee}_K$ has interesting properties. Define the process $\mathcal{G}^{\wedge}_K$, where a weight of size $K$ is assigned to edges between pairs of non-isolated vertices, and a weight of size $1$ otherwise. We prove that the asymptotical behavior of the giant component threshold is essentially the same for $\mathcal{G}^{\wedge}_K$, and namely $t^{\wedge}_g / t^{\vee}_g$ tends to $\frac{64\sqrt{6}}{\pi(24+\pi^2)}\approx 1.47$ as $K\to\infty$. However, the corresponding thresholds for connectivity satisfy $t_c^{\wedge} / t^{\vee}_c =\max\{\frac{1}{2},K\}$ for every $K>0$. Following the methods of Amir et al., $t^{\wedge}_g$ is characterized as the singularity point to a system of differential equations, and computer simulations of both models agree with the analytical results as well as with the asymptotic analysis. In the process, we answer the following question: when does a giant component emerge in a graph process where edges are chosen uniformly out of all edges incident to isolated vertices, while such exist, and otherwise uniformly? This corresponds to the value of $t^{\wedge}_g(0)$, which we show to be $\frac{3}{2}+\frac{4}{3\mathrm{e}^2-1}$.
Manuscript.