Cycle lengths modulo k in expanders

DOI10.1016/J.EJC.2022.103642zbMATH Open1505.05080arXiv2204.09107OpenAlexW4310017061MaRDI QIDQ2111188FDOQ2111188

Authors: Yanyan Li 

Publication date: 28 December 2022

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

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$.

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

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

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)

Cites Work

• Eigenvalues and expanders
• Pancyclic graphs. I
• Expander graphs and their applications
• 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
• The isoperimetric number of random regular graphs
• 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
• Cycle lengths in sparse graphs
• Girth in 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
• Cycle lengths in expanding graphs
• Explicit expanders of every degree and size
• Cycle lengths modulo \(k\) in large 3-connected cubic graphs
• Title not available (Why is that?)
• On the distribution of cycle lengths in graphs
• Cycles of length 0 modulo k in directed graphs
• Zero sum cycles in complete digraphs
• Finding and using expanders in locally sparse graphs
• Expanders -- how to find them, and what to find in them
• Divisible subdivisions

Cited In (2)

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

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)