We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseu-dorandomness notion. A graph G is (ε,p,k,ℓ)-pseudorandom if for all disjoint X, Y (is contained in) V(G) with |X| ≥ εp~kn and |Y| ≥ εp~ℓn we have e(X, Y) = (1 ± ε)p|X||Y|. We prove that for all β ＞ 0 there is an ε ＞ 0 such that an (ε, p, 1, 2)-pseudorandom graph on n vertices with minimum degree at least βpn contains the square of a Hamilton cycle. In particular, this implies that (n, d, λ)-graphs with λ (＜＜) d~(5/2)n~(-3/2) contain the square of a Hamilton cycle, and thus a triangle factor if n is a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403-426]. We also obtain results for higher powers of Hamilton cycles and establish corresponding counting versions. Our proofs are constructive, and yield deterministic polynomial time algorithms.
展开▼
机译：我们使用以下相对较弱的pseu-dorandomness概念研究伪随机图中Hamilton循环的幂的出现。如果对于所有不相交的X，|（包含在）V（G）中，且| X |为|，则图G为（ε，p，k，ℓ）-伪随机。 ≥εp〜kn和| Y | ≥εp〜ℓn我们有e（X，Y）=（1±ε）p | X || Y |。我们证明，对于所有β＞ 0，都有一个ε＞ 0，使得n个顶点上具有最小度至少为βpn的（ε，p，1，2）-伪随机图包含汉密尔顿循环的平方。特别是，这意味着，具有λ（＜＜）d〜（5/2）n〜（-3/2）的（n，d，λ）图包含汉密尔顿循环的平方，因此，如果存在n是3的倍数。这在Krivelevich，Sudakov和Szabo的结果上得到了改进[稀疏伪随机图中的三角因子，Combinatorica 24（2004），否。 3，403-426]。我们还获得了汉密尔顿周期的更高幂的结果，并建立了相应的计数版本。我们的证明是建设性的，并产生确定性的多项式时间算法。
展开▼
