Long paths and cycles in random subgraphs of H-free graphs

Abstract: Let

m a t h c a l H

be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let

G

be an arbitrary finite

m a t h c a l H

-free graph with minimum degree at least

k

. For

p i n [0, 1]

, we form a

p

-random subgraph

G_{p}

of

G

by independently keeping each edge of

G

with probability

p

. Extending a classical result of Ajtai, Koml'os, and Szemer'edi, we prove that for every positive

v a r e p s i l o n

, there exists a positive

d e l t a

(depending only on

v a r e p s i l o n

) such that the following holds: If

p g e f r a c 1 + v a r e p s i l o n k

, then with probability tending to

1

as

k o i n f t y

, the random graph

G_{p}

contains a cycle of length at least

n_{m a t h c a l H} (d e l t a k)

, where

n_{m a t h c a l H} (k) > k

is the minimum number of vertices in an

m a t h c a l H

-free graph of average degree at least

k

. Thus in particular

G_{p}

as above typically contains a cycle of length at least linear in

k

.

Full work available at URL: https://arxiv.org/abs/1303.1066

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (11)

This page was built for publication: Long paths and cycles in random subgraphs of \(\mathcal{H}\)-free graphs