2019/12/23 by Friedman, Limor, Krivelevich, Michael · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1912.11011
For a positive constant α a graph G on n vertices is called an α-expander if every vertex set U of size at most n/2 has an external neighborhood whose size is at least α|U|. We study cycle lengths in expanding graphs. We first prove that cycle lengths in α-expanders are well distributed. Specifically, we show that for every 00 a graph G on n vertices is called a β-graph if every pair of disjoint sets of size at least βn are connected by an edge. We prove that for every β<1/20 there exist positive constants b1=O((1)/(log(1/β))) and b2=O(β) such that every β-graph G on n vertices contains a cycle of length ℓ for every integer ℓ∈[b1log n,(1-b2)n]; the order of dependence of b1 and b2 on β is optimal.