The extremal function for cycles of length mod k

Abstract: Burr and ErdH{o}s conjectured that for each

k, e l l i n m a t h b b Z^{+}

such that

k m a t h b b Z + e l l

contains even integers, there exists

c_{k} (e l l)

such that any graph of average degree at least

c_{k} (e l l)

contains a cycle of length

e l l

mod

k

. This conjecture was proved by Bollob'{a}s, and many successive improvements of upper bounds on

c_{k} (e l l)

appear in the literature. In this short note, for

1 l e q e l l l e q k

, we show that

c_{k} (e l l)

is proportional to the largest average degree of a

C_{e l l}

-free graph on

k

vertices, which determines

c_{k} (e l l)

up to an absolute constant. In particular, using known results on Tur'{a}n numbers for even cycles, we obtain

c_{k} (e l l) = O (e l l k^{2 / e l l})

for all even

e l l

, which is tight for

e l l i n 4, 6, 10

. Since the complete bipartite graph

K_{e l l - 1, n - e l l + 1}

has no cycle of length

2 e l l

mod

k

, it also shows

c_{k} (e l l) = T h e t a (e l l)

for

e l l = O m e g a (l o g k)

.

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

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 (10)

This page was built for publication: The extremal function for cycles of length \(\ell\) mod \(k\)