On degree sequences forcing the square of a Hamilton cycle - Staden, K; Treglown, A (Society for Industrial and Applied Mathematics, 2017)
A famous conjecture of Posa from 1962 asserts that every graph on n vertices and with minimum degree at least 2n/3 contains the square of a Hamilton cycle. The conjecture was proven for large graphs in 1996 by Komlos, Sarkozy, and Szemeredi [Random Structures Algorithms, 9 (1996) pp. 193-211]. In this paper we prove a degree sequence version of Posa's conjecture: Given any η > 0, every graph G of sufficiently large order n contains the square of a Hamilton cycle if its degree sequence d1<... < dnsatisfies di≥ (1/3 + η)n + i for all i ≤ n/3. The degree sequence condition here is asymptotically best possible. Our approach uses a hybrid of the regularity-blowup method and the connecting-absorbing method.