Eyal Lubetzky

Anatomy of a young giant component in the random graph (2009)

Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical regime, $p=c/n$ with fixed $c>1$, was shown to...

Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval

We provide a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3...

Diameters in supercritical random graphs via first passage percolation (2009)

Ding, Jian, Kim, Jeong Han, Lubetzky, Eyal, Peres, Yuval

We study the diameter of $C_1$, the largest component of the Erd\H{o}s-R\'enyi random graph $\cG(n,p)$ emerging from the critical window, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to...

Sums and products along sparse graphs (2009)

Alon, Noga, Angel, Omer, Benjamini, Itai, Lubetzky, Eyal

In their seminal paper from 1983, Erd\H{o}s and Szemer\'edi showed that any $n$ distinct integers induce either $n^{1+\epsilon}$ distinct sums of pairs or that many distinct products, and conjectured...

Hamiltonicity thresholds in Achlioptas processes (2009)

Michael Krivelevich, Eyal Lubetzky, Benny Sudakov

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)...

Choice-memory tradeoff in allocations (2009)

Alon, Noga, Gurel-Gurevich, Ori, Lubetzky, Eyal

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 has order n and the maximum...

Mixing time of critical Ising model on trees is polynomial in the height (2009)

Codes and Xor graph products (2008)

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...

Censored Glauber Dynamics for the mean field Ising Model (2008)

What is the maximum possible number, f3(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, g3(n), of vectors in...

Cutoff phenomena for random walks on random regular graphs (2008)

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...

Lubetzky, Eyal, Sly, Allan

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...

Broadcasting with side information (2008)

Alon, Noga, Hasidim, Avinatan, Lubetzky, Eyal, Stav, Uri, Weinstein, Amit

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...

The mixing time evolution of Glauber dynamics for the mean-field Ising model (2008)

Non-linear index coding outperforming the linear optimum (2008)

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 <...

Lubetzky, Eyal, Stav, Uri

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,...,R_n$. The receiver $R_i$ is...

Hamiltonicity thresholds in Achlioptas processes (2008)

Krivelevich, Michael, Lubetzky, Eyal, Sudakov, Benny

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)...

Independent sets in tensor graph powers (2008)

Codes and Xor graph products (2008)

The tensor product of two graphs, G and H, has a vertex set V (G) × V (H) and an edge between (u, v) and (u ′ , v ′ ) iff both uu ′ ∈ E(G) and vv ′ ∈ E(H). Let A(G) denote the limit of...

The isoperimetric constant of the random graph process, preprint (2008)

What is the maximum possible number, f3(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, g3(n), of vectors in...

Itai Benjamini, Simi Haber, Michael Krivelevich, Eyal Lubetzky

2\Delta graphs, where eG(0) is the edgeless graph on n vertices, and eG(t) is the result of addingan edge to e G(t- 1), uniformly distributed over all the missing edges. We show that in almost every...

Total-variation cutoff in birth-and-death chains (2008)

Uniformly cross intersecting families (2008)

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...

The Multicast Bandwidth Advantage in Serving (2007)

Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...

Web Site Yossi, Yossi Azar, Meir Feder, Eyal Lubetzky, Doron Rajwan

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...

Poisson approximation for non-backtracking random walks (2007)

Privileged users in zero-error transmission over a noisy channel (2007)

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...

Coarse to over-fine optical flow estimation (2007)

The k-th power of a graph G is the graph whose vertex set is V (G) k, where two distinct ktuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G),...

Tomer Amiaz, Eyal Lubetzky, Nahum Kiryati

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...

Non-backtracking random walks mix faster (2006)

Alon, Noga, Benjamini, Itai, Lubetzky, Eyal, Sodin, Sasha

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...

Uniformly cross intersecting families (2006)

The Shannon capacity of a graph and the independence numbers of its powers (2006)

Let $\mathcal{A}$ and $\matchcal{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...

Privileged users in zero-error transmission over a noisy channel (2006)

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...

Independent sets in tensor graph powers (2006)

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...

On two biased graph processes (2006)

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...

Amir, Gideon, Lubetzky, Eyal

In [Amir et al.], the authors consider the generalization $\Gor$ of the Erd\H{o}s-R\'enyi random graph process $G$, where instead of adding new edges uniformly, $\Gor$ gives a weight of size 1 to...

Graph powers, Delsarte, Hoffman, Ramsey and Shannon (2006)

Uniformly cross intersecting families (2006)

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...

Uniformly cross intersecting families (2006)

Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...

Non-backtracking random walks mix faster (2006)

Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...

Noga Alon, Itai Benjamini, Eyal Lubetzky, Sasha Sodin

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...

Giant Components in Biased Graph Processes (2005)

Amir, Gideon, Gurel-Gurevich, Ori, Lubetzky, Eyal, Singer, Amit

A random graph process, $\Gorg[1](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...

The isoperimetric constant of the random graph process (2005)

Benjamini, Itai, Haber, Simi, Krivelevich, Michael, Lubetzky, Eyal

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...

The Shannon capacity of a graph and the independence numbers of its powers (2005)