126 citations · 988 across the 68 of their papers we have counts for
7 papers · 1 filter
Non-backtracking random walks mix faster
Noga Alon, Itai Benjamini, Eyal Lubetzky +1
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…
Uniformly cross intersecting families
Noga Alon, Eyal Lubetzky
Let and $\matchcal{B}$ denote two families of subsets of an -element set. The pair is said to be -cross-intersecting iff $|A\cap…
On two biased graph processes
Gideon Amir, Eyal Lubetzky
In [Amir et al.], the authors consider the generalization $\Gor$ of the Erdős-Rényi random graph process , where instead of adding new edges uniformly, $\Gor$ gives a weight of…
Independent sets in tensor graph powers
Noga Alon, Eyal Lubetzky
The tensor product of two graphs, and , has a vertex set and an edge between and iff both and . Let …
Privileged users in zero-error transmission over a noisy channel
Noga Alon, Eyal Lubetzky
The -th power of a graph is the graph whose vertex set is , where two distinct -tuples are adjacent iff they are equal or adjacent in in each coordinate. The…
The Shannon capacity of a graph and the independence numbers of its powers
Noga Alon, Eyal Lubetzky
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 th…