Extremal results for odd cycles in sparse pseudorandom graphs
Extremal results for odd cycles in sparse pseudorandom graphs
复制标题
稀疏伪随机图中奇数循环的极值结果
DOI：
10.1007/s00493-014-2912-y
复制
发表时间：
2014
期刊：
影响因子：
1.1
通讯作者：
Mathias Schacht
中科院分区：
文献类型：
--
作者：
Elad Aigner-Horev;Hiêp Hàn;Mathias Schacht
我们考虑伪随机图子图的极值问题。对于图形F和Г，广义图兰密度πF(Г)表示不包含复制的Г的极大子图的相对密度。推广了经典的Turán型关于奇圈的结果，证明了πF(Г)=1/2是一个奇圈，Г是一个充分伪随机图.特别地，对于(n，d，λ)-图Г，即所有非平凡特征值都在区间[−λ，λ]内的n-点，d-正则图，我们的结果对长度为ℓ的奇圈成立，这证明了Krivelevich，Lee和sudakov的一个猜想.对于三角形，这个条件是最有可能的，之前曾由Sudakov、Szabó和Vu证明过，他们解决了当F是完全图时的情况。ALON和KAHALE的构造(基于早期关于无三角形(n，d；λ)图的ALON的构造)表明，我们关于Г的假设对于每一个奇数ℓ≥5都是最好可能的。
We consider extremal problems for subgraphs of pseudorandom graphs. For graphsFandГthe generalized Turán densityπF(Г) denotes the relative density of a maximum subgraph ofГ, which contains no copy ofF. Extending classical Turán type results for odd cycles, we show thatπF(Г)=1/2 providedFis an odd cycle andГis a sufficiently pseudorandom graph.In particular, for (n,d,λ)-graphsГ, i.e.,n-vertex,d-regular graphs with all non-trivial eigenvalues in the interval [−λ,λ], our result holds for odd cycles of lengthℓ, providedUp to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case whenFis a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free (n,d;λ)-graphs) shows that our assumption onГis best possible up to the polylog-factor for every oddℓ≥5.
登录
查看更多内容
随机图的极值子图
DOI：
--
发表时间：
2007
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
G. Brightwell;K. Panagiotou;A. Steger
通讯作者：
A. Steger
影响因子：
3.9
作者：
J. Balogh;R. Morris;Wojciech Samotij
通讯作者：
J. Balogh;R. Morris;Wojciech Samotij
随机离散结构的稳定性结果
DOI：
--
发表时间：
2011
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
Wojciech Samotij
通讯作者：
Wojciech Samotij
关于随机图中的 KÅR 猜想
影响因子：
1
作者：
D. Conlon;W. T. Gowers;W. Samotij;M. Schacht
通讯作者：
M. Schacht
稀疏随机集中的组合定理
DOI：
--
发表时间：
2010
期刊：
影响因子：
--
作者：
D. Conlon;W. Gowers
通讯作者：
W. Gowers