Gabor Sarkozy (WPI)
We present a new method based on the Regularity Lemma and the Blow-up Lemma for finding certain special spanning subgraphs of dense graphs. Two typical applications of this method:
1. (Bollobas Conjecture, 1978) We show that any constant degree tree on sufficiently many vertices can be embedded into any dense graph on the same number of vertices.
2. (Posa-Seymour Conjecture, 1962) We show that a graph on sufficiently many vertices and with minimum degree at least 2/3 n (where n is the number of vertices) contains the square of a Hamiltonian cycle.
Algorithmic implications of the method will also be discussed.