Yahav Alon

activity

20182023

most citedThe completion numbers of Hamiltonicity and pancyclicity in random graphs

1 citations · 1 across the 6 of their papers we have counts for

collaborators

Showing math.COShow all

10 papers · 1 filter

math.CO2023

Sparse pancyclic subgraphs of random graphs

Yahav Alon, Michael Krivelevich

It is known that the complete graph $K_{n}$ contains a pancyclic subgraph with $n + (1 + o (1)) \cdot lo g_{2} n$ edges, and that there is no pancyclic graph on $n$ vertices with fewer than…

math.CO2023

Two-round Ramsey games on random graphs

Yahav Alon, Patrick Morris, Wojciech Samotij

Motivated by the investigation of sharpness of thresholds for Ramsey properties in random graphs, Friedgut, Kohayakawa, Rödl, Ruciński and Tetali introduced two variants of a singl…

math.CO2023★ 1 cited

The completion numbers of Hamiltonicity and pancyclicity in random graphs

Yahav Alon, Michael Anastos

Let $μ (G)$ denote the minimum number of edges whose addition to $G$ results in a Hamiltonian graph, and let $μ^(G)$ denote the minimum number of edges whose addition to $G$ resu…

math.CO2022

Hamilton completion and the path cover number of sparse random graphs

Yahav Alon, Michael Krivelevich

We prove that for every $ε > 0$ there is $c_{0}$ such that if $G \sim G (n, c / n)$ , $c \geq c_{0}$ , then with high probability $G$ can be covered by at most $(1+\varepsilon)\cdot \…

math.CO2022

The global resilience of Hamiltonicity in $G (n, p)$

Yahav Alon

Denote by $r_{g} (G, H)$ the global resilience of a graph $G$ with respect to Hamiltonicity. That is, $r_{g} (G, H)$ is the minimal $r$ for which there exists a subgrap…

math.CO2020

Spanning trees at the connectivity threshold

Yahav Alon, Michael Krivelevich, Peleg Michaeli

We present an explicit connected spanning structure that appears in a random graph just above the connectivity threshold with high probability.

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

Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs

Yahav Alon, Michael Krivelevich

Consider the random subgraph process on a base graph $G$ on $n$ vertices: a sequence ${G_{t}}_{t = 0}^{∣ E (G) ∣}$ of random subgraphs of $G$ obtained by choosing an order…

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…

Sparse pancyclic subgraphs of random graphs

Two-round Ramsey games on random graphs

The completion numbers of Hamiltonicity and pancyclicity in random graphs

Hamilton completion and the path cover number of sparse random graphs

The global resilience of Hamiltonicity in G(n,p)

Spanning trees at the connectivity threshold

Cycle lengths in sparse random graphs

Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs

Finding a Hamilton cycle fast on average using rotations and extensions

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

The global resilience of Hamiltonicity in $G (n, p)$