Cycle Lengths in Expanding Graphs

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|U|. We study cycle lengths in expanding graphs. We first prove that cycle lengths in alpha-expanders are well distributed. Specifically, we show that for every 0 < alpha <= 1 there exist positive constants n(0), C and A = O(1/alpha) such that for every alpha-expander G on n >= n(0) vertices and every integer , l is an element of[C log n,n/c] G contains a cycle whose length is between l and l+A; the order of dependence of the additive error term A on alpha is optimal. Secondly, we show that every alpha-expander on n vertices contains Omega(alpha(3)/log(1/alpha)) 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 beta > 0 a graph G on n vertices is called a beta-graph if every pair of disjoint sets of size at least beta n are connected by an edge. We prove that for every there exist positive constants b(1)-O(1/log(1/beta))and b(2) = O(beta) such that every beta-graph G on n vertices contains a cycle of length l for every integer l is an element of[b(1) logn,(1-b(2))n]; the order of dependence of b(1) and b(2) on beta is optimal.

Automated summary

The paper investigates the distribution and properties of cycle lengths in expanding graphs, proving structural characteristics of alpha-expanders and beta-graphs, and analyzing the properties of their cycle lengths in detail.