How to avoid using the regularity Lemma: Pósa's conjecture revisited (Q960978)

It is well known that many extremal problems, perhaps especially ones related to dense graphs, can be approached via the Szemerédi regularity lemma, which (summarising very crudely) says that for large \(n\) every graph on \(n\) vertices can have its vertices partitioned into sets of roughly equal size, such that the edge between two sets in this partition are `random-like'. However, though a terribly powerful tool, the Regularity Lemma often requires \(n\) to be extremely large, and thus there is interest in `Regularity-Lemma-free\'\, proofs of the results, which will often at least work for more general values of \(n\). In particular, the problem studied in the paper under review is a conjecture of Pósa, that if \(G\) is a graph on \(n\) vertices with minimum degree \(\delta(G)\geq 2n/3\) then \(G\) contains the square of a Hamilton cycle. (The square of any graph is the graph with the same vertex set and two vertices being adjacent in the square if they are at distance \(\leq 2\) in the original graph). Pósa's conjecture was proved for \(n\geq n_{0}\) in [\textit{J. Komlós, G. N. Sárközy} and \textit{E. Szemerédi}, Random Struct. Algorithms 9, No.1-2, 193--211 (1996; Zbl 0864.05063)] but the \(n_{0}\) depended on the Regularity Lemma and was thus astronomically large. In the paper under review an alternative proof, avoiding the Regularity Lemma, is given, which still needs a (very) large \(n\) but less large than previously. Here is some idea of the proof. Fix \(\alpha\) small (1/10 will do). There are two cases. In the first, \(G\) has two (not necessarily disjoint) subsets \(A,B\subseteq V(G)\) such that \((1/3-\alpha)n\leq | A|, | B| \leq n/3\) and (with \(e(A,B)\) the number of edges with one endpoint in \(A\) and the other in \(B\)) the density \[ d(A,B)=\frac{e(A,B)}{| A| | B|} \] is less than \(\alpha\). Then in this case the argument from the above paper (which did not use the Regularity Lemma) can be recycled. Otherwise, if there are no such \(A\) and \(B\), the argument first establishes existence of short squares of paths between any two disjoint ordered pairs of vertices via the so-called Connecting Lemma. Next this Lemma and probabilistic arguments are used to show that there is a not too long (length \(\leq \alpha^{9}n\)) `absorbing\'\, square of a path \(P\) such that any set \(U\) of vertices not on \(P\) of order at most \(\alpha^{20}n\) can be inserted into the path so as to keep it a square path. Thus it will be seen that most of what remains is to construct a square of a cycle which will contain \(P\), as then the absorbing properties will allow us to mop up the remaining vertices. This is done by firstly having, for any \(W\subseteq V(G)\) with \(| W| \leq \alpha^{9}n\), a `reservoir\'\, \(R\) of vertices such that we can construct paths between ordered pairs of vertices even if \(\alpha^{9}| R|\) of the vertices of \(R\) are not allowed to be used in this connecting path. When we have a suitably long square of a path, finishing off to a long square of a cycle is not difficult by the absorbing powers. The techniques to get a long enough square of a path include the reservoir techniques just hinted at, and various delicate arguments about bitstrings of neighbours of vertices using a swapping technique. The authors express the hope that further work by them in progress (especially improving on the Connecting Lemma) will bring \(n_{0}\) down to about 100, at which point a computation could result in the conjecture being proved for all \(n\). It also seems likely the ideas of connecting, absorbing and having reservoirs will be usable in various other extremal problem.