Cycle lengths in expanding graphs (Q2036619)

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.