On Hamilton cycles in Erdős-Rényi subgraphs of large graphs

Publication date 16 September 2020

Abstract: Given a graph

G a m m a = (V, E)

on

n

vertices and

m

edges, we define the ErdH{o}s-R'{e}nyi graph process with host

G a m m a

as follows. A permutation

e_{1}, d o t s, e_{m}

of

E

is chosen uniformly at random, and for

t l e q m

we let

G a m m a_{t} = (V, e_{1}, d o t s, e_{t})

. Suppose the minimum degree of

G a m m a

is

d e l t a (G a m m a) g e q (1 / 2 + v a r e p s i l o n) n

for some constant

v a r e p s i l o n > 0

. Then with high probability,

G a m m a_{t}

becomes Hamiltonian at the same moment that its minimum degree becomes at least two. Given

0 l e q p l e q 1

we let

G a m m a_{p}

be the ErdH{o}s-R'{e}nyi subgraph of

G a m m a

, obtained by retaining each edge independently with probability

p

. When

d e l t a (G a m m a) g e q (1 / 2 + v a r e p s i l o n) n

, we provide a threshold function

p_{0}

for Hamiltonicity, such that if

(p - p_{0}) n o - i n f t y

then

G a m m a_{p}

is not Hamiltonian whp, and if

(p - p_{0}) n o i n f t y

then

G a m m a_{p}

is Hamiltonian whp.

Recommendations

Cites work

Cited in

(5)

This page was built for publication: On Hamilton cycles in Erdős-Rényi subgraphs of large graphs