List of publications - Eyal Lubetzky

• E. Lubetzky and Yufei Zhao,
  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).

  
  Submitted.
  
  
• P. Caputo, E. Lubetzky, F. Martinelli, A. Sly and F.L. Toninelli,
  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.
  
  
• P. Caputo, E. Lubetzky, F. Martinelli, A. Sly and F.L. Toninelli,
  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, to appear.
  
  
• P. Cuff, J. Ding, O. Louidor, E. Lubetzky, Y. Peres, A. Sly,
  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.
  
  
• T. Bohman, A. Frieze and E. Lubetzky,
  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}$, 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.

  
  Submitted.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  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 $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 $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.

  
  Submitted.
  
  
• E. Lubetzky and A. Sly,
  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, to appear.
  
  
• A. Blasiak, R. Kleinberg and E. Lubetzky,
  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.
  
  
• M. Krivelevich, E. Lubetzky and B. Sudakov,
  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, to appear.
  
  
• P.-S. Loh and E. Lubetzky,
  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.
  
  
• E. Lubetzky, F. Martinelli, A. Sly and F.L. Toninelli,
  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 15 (2013), no. 2, 339–386.
  
  
• A. Azar, O. Gurel-Gurevich, E. Lubetzky and T. Moscibroda,
  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.
  
  
• T. Bohman, A. Frieze and E. Lubetzky,
  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.
  
  
• A. Blasiak, R. Kleinberg and E. Lubetzky,
  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.

  
  Submitted.
  
  
• E. Lubetzky and A. Sly,
  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.
  
  
• E. Lubetzky and A. Sly,
  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.
  
  
• E. Lubetzky, B. Sudakov and V. Vu,
  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.
  
  
• E. Lubetzky and A. Sly,
  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.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  Mixing time of near-critical random graphs. Abstract

  Let $\mathcal{C}_1$ be the largest component of the Erdős-Rényi random graph $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.
  
  
• N. Alon, O. Angel, I. Benjamini and E. Lubetzky,
  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 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.

  
  Israel Journal of Mathematics 188 (2012), no. 1, 353–384.
  
  
• J. Ding, J.H. Kim, E. Lubetzky and Y. Peres,
  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 $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.
  
  
• J. Ding, J.H. Kim, E. Lubetzky and Y. Peres,
  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 $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.
  
  
• N. Alon, O. Gurel-Gurevich and E. Lubetzky,
  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.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  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.
  
  
• E. Lubetzky and A. Sly,
  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 \emph{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 \emph{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.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  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 \emph{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.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  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.
  
  
• N. Alon, A. Hasidim, E. Lubetzky, U. Stav and A. Weinstein,
  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.
  
  
• M. Krivelevich, E. Lubetzky and B. Sudakov,
  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.
  
  
• J. Ding, E. Lubetzky and Y. Peres,
  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.
  
  
• E. Lubetzky and U. Stav,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• N. Alon, I. Benjamini, E. Lubetzky and S. Sodin,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• G. Amir and E. Lubetzky,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• T. Amiaz, E. Lubetzky and N. Kiryati,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• G. Amir, O. Gurel-Gurevich, E. Lubetzky and A. Singer,
  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.
  
  
• I. Benjamini, S. Haber, M. Krivelevich and E. Lubetzky,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• N. Alon and E. Lubetzky,
  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.
  
  
• Y. Azar, M. Feder, E. Lubetzky, D. Rajwan and N. Shulman,
  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.