How to avoid using the Regularity Lemma: Pósa’s conjecture revisited

In this paper we investigate how the use of the Regularity Lemma and the Blow-up Lemma can be avoided in certain extremal problems of dense graphs. We present the ideas for the following well-known Pósa conjecture on the square of a Hamiltonian cycle. In 1962 Pósa conjectured that any graph G of order n and minimum degree at least 2 3 n contains the square of a Hamiltonian cycle. In an earlier paper we proved this conjecture with the use of the Regularity Lemma–Blow-up Lemma method for n ≥ n 0 where n 0 is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n 0 is much smaller.