Powers of Hamilton cycles in pseudorandom graphs
Powers of Hamilton cycles in pseudorandom graphs
复制标题
DOI：
10.1007/s00493-015-3228-2
复制
发表时间：
2014-02
期刊：
影响因子：
1.1
通讯作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
中科院分区：
文献类型：
--
作者：
Peter Allen;Julia Böttcher;Hiêp Hàn;Y. Kohayakawa;Y. Person
利用以下相对弱的伪随机概念，研究了伪随机图中哈密顿环幂的表现。一个图gis (ε,p,k, r)-伪随机if对于所有断连txandy∧V(G)，其中|X|≥εpknand |Y|≥εp r，我们有（X，Y）=(1±ε)p|X||Y|。我们证明了对于所有β>，存在一个ε>，使得一个(ε,p,1,2)-伪随机图的最小度至少为βp，它包含一个Hamilton环的平方。特别是，这意味着λ≪d5/2n-3/2的（n,d,λ）图包含汉密尔顿圈的平方，因此三角形因子是3的倍数。这比Krivelevich， Sudakov和Szabó[27]的结果有所改进。我们还将结果推广到Hamilton环的更高次，并建立了相应的计数版本。
We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graphGis (ε,p,k,ℓ)-pseudorandom if for all disjointXandY⊂V(G) with |X|≥εpknand |Y|≥εpℓnwe havee(X,Y)=(1±ε)p|X||Y|. We prove that for allβ>0 there is anε>0 such that an (ε,p,1,2)-pseudorandom graph onnvertices with minimum degree at leastβpncontains the square of a Hamilton cycle. In particular, this implies that (n,d,λ)-graphs with λ≪d5/2n-3/2contain the square of a Hamilton cycle, and thus a triangle factor ifnis a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabó [27].We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.