Yahav Alon

activity

20182020

collaborators

3 papers

math.CO2020

Cycle lengths in sparse random graphs

Yahav Alon, Michael Krivelevich, Eyal Lubetzky

We study the set $L (G)$ of lengths of all cycles that appear in a random $d$ -regular $G$ on $n$ vertices for a fixed $d \geq 3$ , as well as in Erdős--Rényi random graphs on $…

math.CO2019

Finding a Hamilton cycle fast on average using rotations and extensions

Yahav Alon, Michael Krivelevich

We present an algorithm CRE, which either finds a Hamilton cycle in a graph $G$ or determines that there is no such cycle in the graph. The algorithm's expected running time over i…

math.CO2018

Random graph's Hamiltonicity is strongly tied to its minimum degree

Yahav Alon, Michael Krivelevich

We show that the probability that a random graph $G \sim G (n, p)$ contains no Hamilton cycle is $(1 + o (1)) P r (δ (G) < 2)$ for all values of $p = p (n)$ . We also prove an analogous result…