Cycle lengths in expanding graphs

Abstract: For a positive constant

a l p h a

a graph

G

on

n

vertices is called an

a l p h a

-expander if every vertex set

U

of size at most

n / 2

has an external neighborhood whose size is at least

a l p h a l e f t | U i g h t |

. We study cycle lengths in expanding graphs. We first prove that cycle lengths in

a l p h a

-expanders are well distributed. Specifically, we show that for every

0 < a l p h a l e q 1

there exist positive constants

n_{0}

,

C

and

A = O (1 / a l p h a)

such that for every

a l p h a

-expander

G

on

n g e q n_{0}

vertices and every integer

e l l i n l e f t [C l o g n, f r a c n C i g h t]

,

G

contains a cycle whose length is between

e l l

and

e l l + A

; the order of dependence of the additive error term

A

on

a l p h a

is optimal. Secondly, we show that every

a l p h a

-expander on

n

vertices contains

O m e g a l e f t (f r a c a l p h a^{3} l o g l e f t (1 / a l p h a i g h t) i g h t) n

different cycle lengths. Finally, we introduce another expansion-type property, guaranteeing the existence of a linearly long interval in the set of cycle lengths. For

a graph

G

on

n

vertices is called a

-graph if every pair of disjoint sets of size at least

are connected by an edge. We prove that for every

there exist positive constants

and

such that every

-graph

G

on

n

vertices contains a cycle of length

e l l

for every integer

e l l i n l e f t [b_{1} l o g n, (1 - b_{2}) n i g h t]

; the order of dependence of

b_{1}

and

b_{2}

on

is optimal.

Review text

For a positive constant \(\alpha\) a graph \(G\) on \(n\) vertices is called an \(\alpha\)-expander if every vertex set \(U\) of size at most \(n/2\) has an external neighborhood whose size is at least \(\alpha\vert U\vert \). It is proved that cycle lengths in \(\alpha\)-expanders are well distributed. In particular, it is shown that for every \(0 < \alpha\le 1\) there exist positive constants \(n_0\), \(C\) and \(A = O(1/\alpha)\) such that for every \(\alpha\)-expander \(G\) on \(n\ge n_0\) vertices and every integer \(\ell\in \big[C\log n, \frac{n}{C}\big]\), \(G\) contains a cycle whose length is between \(\ell\) and \(\ell + A\); the order of dependence of the additive error term \(A\) on \(\alpha\) is optimal. Secondly, it is shown that every \(\alpha\)-expander on \(n\) vertices contains \(\Omega\Big(\frac{\alpha^3} {\log(1/\alpha)}\Big)n\) different cycle lengths. Finally, it is introduced another expansion-type property, guaranteeing the existence of a linearly long interval in the set of cycle lengths. Namely, for \(\beta > 0\) a graph \(G\) on \(n\) vertices is called \(\beta\)-graph if every pair of disjoint sets of size at least \(\beta n\) are connected by an edge. It is proved that for every \(\beta < 1/20\) there exist positive constants \(b_1 = O\Big(\frac{1} {\log(1/\beta)}\Big)\) and \(b_2 = O(\beta)\) such that every \(\beta\)-graph \(G\) on \(n\) vertices contains a cycle of length \(\ell\) for every integer \(\ell\in[b_1\log n,(1-b_2)n]\); the order of dependence of \(b_1\) and \(b_2\) on \(\beta\) is optimal.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: Cycle lengths in expanding graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2036619)