.png){kind=icon}
返回
COUNTING ODD CYCLES IN SPARSE PSEUDORANDOM GRAPHS
.png){kind=icon}
PRE
AI
DOI：10.1090/proc/17216.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们回答了关于奇圈的两个极端问题，这些问题在稀疏伪随机图的研究中自然产生。设F为(n, d, λ)图，即具有n个顶点、d-正则且所有非平凡特征值位于区间[-λ, λ]内的图。Krivelevich、Lee和Sudakov [SIAM J. Discrete Math. 24 (2010), pp. 1-16] 猜想，每当2k-1 << d^{2k}/n时，F的每一个具有(1/2 + o(1))e(F)条边的子图G都包含一个奇圈C_{2k+1}。Aigner-Horev、Ha'n和第三作者 [Combinatorica 34 (2014), pp. 379-406] 通过在假设2k-1 << d^{2k}/n中允许一个额外的polylogarithmic因子证明了较弱的命题，但我们完全消除了该因子，从而解决了该猜想。这也推广了Sudakov、Szabo和Vu关于三角形的Turán型定理。其次，我们得到了关于奇圈的Ramsey多重性结果。具体而言，在相同的参数范围内，我们证明F的每一个2边着色都包含至少(1-o(1))2^{-2k}d^{2k} +1个单色C_{2k+1}副本。Alon和Kahale构造的C_{2k+1}-free伪随机图表明，这两个结果在渐近意义下是最佳可能的。
Keyword:
MULTIPLICITIES
期刊
P
IF:
0.8
论文数:
304
被引数:
0
机构
引用论文
.png){kind=icon}
分享收藏分享收藏分享收藏
分享收藏分享收藏
查看更多内容