论文标题
循环长度Modulo $ k $在扩展器中
Cycle lengths modulo $k$ in expanders
论文作者
论文摘要
给定常量的$α> 0 $，如果每套$ x $的$ x $最多$ n/2 $ g $中的$ n $ vertex图称为$α$ - expander，则具有至少$α| x | $的外部邻域。解决弗里德曼（Friedman）和克里维尔维奇（Krivelevich）在[Combinatorica，41（1），（2021），第53---74页中提出的一个问题，我们证明了以下结果：让$ k> 1 $是一个具有最小prime Divisor $ $ p $的整数。然后，对于$α> \ frac {1} {p-1} $，每个足够大的$α$ - 扩展图都包含与任何给定残基Modulo $ k $一致的长度周期。从下面的意义上讲，这个结果几乎是最好的：存在绝对常数$ c> 0 $，使得对于每个具有最小的Prime Divisor $ p $的整数$ k $，并且对于每个正面$α<\ frac {c} {p-1} $ \ {0，\ ldots，k-1 \} $。
Given a constant $α>0$, an $n$-vertex graph is called an $α$-expander if every set $X$ of at most $n/2$ vertices in $G$ has an external neighborhood of size at least $α|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 $α>\frac{1}{p-1}$ every sufficiently large $α$-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 $α<\frac{c}{p-1}$, there exist arbitrarily large $α$-expanding graphs with no cycles of length $r$ modulo $k$, for some $r \in \{0,\ldots,k-1\}$.
