Cycle lengths in expanding graphs

DOI10.1007/S00493-020-4434-0MaRDI QIDQ2036619zbMATH OpenOpenAlexFDO

Authors Limor Friedman, Michael Krivelevich

Publication date 29 June 2021

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

cycle lengths\(\alpha\)-expanderexternal neighborhood

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(14)

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

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)