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)$.
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.
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 most vertices do not lie on $k$-cycles.
Here we settle the 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, we prove a 2-point concentration result: if $k \geq \kappa_0 \log_2(2n/e)$ divides $n$ then $G$ contains a $k$-cycle factor w.h.p., whereas if $k<\kappa_0\log_2(2n/e)-\frac{\log^2 n}n$ then w.h.p. it does not. 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)$.
The proof follows the small subgraph conditioning framework, but the associated second moment analysis here is far more delicate than in any earlier use of this method and involves several novel features, among them a sharp estimate for tail probabilities in renewal processes without replacement which may be of independent interest.
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$).
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.
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.
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$.
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.
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.
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).
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$.
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.
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}$, motivated by the study of the Ramsey number $R(3,t)$. 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 Spencer et al. 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 all homomorphisms from them, rooted at any two vertices, up to 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.
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.
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.
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.
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.
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.
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)].
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)$.
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)}$.
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.
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.
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.
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.
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.
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).
In their seminal paper from 1983, Erdős and Szemerédi showed that any n distinct integers induce either n^{1+e} distinct sums of pairs or that many distinct products, and conjectured a lower bound of n^{2-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 n^{1+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.
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)$.
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$.
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.
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)]$.
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.
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$.
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)$.
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.
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.
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.
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.
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.
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.
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.
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}$.
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.
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.
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.
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.
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.
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.
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)$.
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.
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.