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

Abstract: Consider the random subgraph process on a base graph

G

on

n

vertices: a sequence

l b r a c e G_{t} b r a c e_{t = 0}^{| E (G) |}

of random subgraphs of

G

obtained by choosing an ordering of the edges of

G

uniformly at random, and by sequentially adding edges to

G_{0}

, the empty graph on the vertex set of

G

, according to the chosen ordering. We show that if

G

has one of the following properties: 1. There is a positive constant

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

such that

d e l t a (G) g e q l e f t (f r a c 12 + v a r e p s i l o n i g h t) n

; 2. There are some constants

such that every two disjoint subsets

U, W

of size at least

a l p h a n

have at least

edges between them, and the minimum degree of

G

is at least

; or: 3.

G

is an

(n, d, l a m b d a)

--graph, with

d g e q f r a c C c d o t n c d o t l o g l o g n l o g n

and

l a m b d a l e q f r a c c c d o t d^{2} n

for some absolute constants

c, C > 0

. then for a positive integer constant

k

with high probability the hitting time of the property of containing

k

edge disjoint Hamilton cycles is equal to the hitting time of having minimum degree at least

2 k

. These results extend prior results by by Johansson and by Frieze and Krivelevich, and answer a question posed by Frieze.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Hitting time of edge disjoint Hamilton cycles in random subgraph processes on dense base graphs