Cycle lengths in expanding graphs

DOI10.1007/S00493-020-4434-0zbMATH Open1474.05220arXiv1912.11011OpenAlexW3109168039MaRDI QIDQ2036619FDOQ2036619

Limor Friedman, Michael Krivelevich

Publication date: 29 June 2021

Published in: Combinatorica (Search for Journal in Brave)

Abstract: 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 $alphaleft|Uight|$. 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<alphaleq1$ there exist positive constants $n_0$, $C$ and $A=O(1/alpha)$ such that for every $alpha$-expander $G$ on $ngeq{n}_0$ vertices and every integer $ellinleft[Clogn,fracnCight]$, $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, we show that every $alpha$-expander on $n$ vertices contains $Omegaleft(fracalph{a}^{3}logleft(1/alphaight)ight)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 $ell$ for every integer $ellinleft[b_{1}logn,(1-b_2)night]$; the order of dependence of $b_1$ and $b_2$ on $$ is optimal.

Full work available at URL: https://arxiv.org/abs/1912.11011

Recommendations

• Cycle lengths modulo \(k\) in expanders
• Expanders -- how to find them, and what to find in them
• Cycle lengths in graphs with large minimum degree
• On cycle lengths in graphs of moderate degree
• Distribution of cycle lengths in graphs

zbMATH Keywords

cycle lengths\(\alpha\)-expanderexternal neighborhood

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Expander graphs (05C48)

Cites Work

• Eigenvalues and expanders
• Tree embeddings
• Expanding graphs contain all small trees
• Large bounded degree trees in expanding graphs
• Pancyclic graphs. I
• Expander graphs and their applications
• Ramanujan graphs
• The probabilistic method
• On arithmetic progressions of cycle lengths in graphs
• Cycles of length 0 modulo 4 in graphs
• Graphs with a cycle of length divisible by three
• Graph decomposition with applications to subdivisions and path systems modulo k
• Cycle lengths and minimum degree of graphs
• Cycle lengths and chromatic number of graphs
• Hamilton cycles in highly connected and expanding graphs
• Cycle lengths in sparse graphs
• The number of cycle lengths in graphs of given minimum degree and girth
• Cycles in triangle-free graphs of large chromatic number
• Distribution of cycle lengths in graphs
• Cycles Modulo k
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Title not available (Why is that?)
• On the distribution of cycle lengths in graphs
• Cycles of length 0 modulo k in directed graphs
• Long paths and Hamiltonicity in random graphs
• Finding and Using Expanders in Locally Sparse Graphs
• Expanders – how to find them, and what to find in them

Cited In (14)

• Perfect matching in random graphs is as hard as Tseitin
• Cycle lengths modulo \(k\) in expanders
• Distribution of cycle lengths in graphs
• Extending cycles in directed graphs
• Oriented discrepancy of Hamilton cycles
• Chvátal-Erdős condition for pancyclicity
• Turán‐type problems for long cycles in random and pseudo‐random graphs
• Title not available (Why is that?)
• Many Hamiltonian subsets in large graphs with given density
• Crux and Long Cycles in Graphs
• Discrepancies of spanning trees and Hamilton cycles
• The multicolor size-Ramsey numbers of cycles
• Divisible subdivisions
• Cycle lengths in sparse random graphs

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)