2022/04/19 by Martinsson, Anders, Steiner, Raphael
#05C35 #05C38 #05C48 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2204.09107
Given a constant α>0, an n-vertex graph is called an α-expander if every set X of at most n/2 vertices in G has an external neighborhood of size at least α|X|. Addressing a question posed by Friedman and Krivelevich in [Combinatorica, 41(1), (2021), pp. 53--74], we prove the following result: Let k>1 be an integer with smallest prime divisor p. Then for α>(1)/(p-1) every sufficiently large α-expanding graph contains cycles of length congruent to any given residue modulo k. This result is almost best possible, in the following sense: There exists an absolute constant c>0 such that for every integer k with smallest prime divisor p and for every positive α