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

AbstractIn 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 23n 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≥n0 where n0 is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n0 is much smaller