Cycle lengths modulo k in expanders

DOI10.1016/J.EJC.2022.103642MaRDI QIDQ2111188zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 28 December 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cycle lengths\(\alpha\)-expanderexternal neighborhood

Mathematics Subject Classification ID

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

Abstract: Given a constant $alpha>0$, an $n$-vertex graph is called an $alpha$-expander if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $alpha|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 $alpha>frac1p-1$ every sufficiently large $alpha$-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 $alpha<fraccp-1$, there exist arbitrarily large $alpha$-expanding graphs with no cycles of length $r$ modulo $k$, for some $rin0,ldots,k-1$.

Recommendations

• Cycle lengths in expanding graphs
• scientific article; zbMATH DE number 617590
• The extremal function for cycles of length \(\ell\) mod \(k\)
• Cycles of even lengths modulo \(k\)
• Cycle lengths modulo \(k\) in large 3-connected cubic 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 expanding graphs
• Cycle lengths in sparse graphs
• Cycle lengths modulo \(k\) in large 3-connected cubic 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
• Divisible subdivisions
• Eigenvalues and expanders
• Expander graphs and their applications
• Expanders -- how to find them, and what to find in them
• Explicit expanders of every degree and size
• Finding and using expanders in locally sparse graphs
• Girth in graphs
• Graph decomposition with applications to subdivisions and path systems modulo k
• Graphs with a cycle of length divisible by three
• On arithmetic progressions of cycle lengths in graphs
• On the distribution of cycle lengths in graphs
• Pancyclic graphs. I
• The isoperimetric number of random regular graphs
• The number of cycle lengths in graphs of given minimum degree and girth
• Zero sum cycles in complete digraphs

Cited in

(2)

• Cycle Lengths in $A^k b$
• Cycle lengths in expanding graphs

This page was built for publication: Cycle lengths modulo \(k\) in expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2111188)