ABSTRACT OF THE DISSERTATION Some problems in Extremal Graph Theory avoiding the use of the Regularity Lemma

In this thesis we present two results in Extremal Graph Theory. The first result is a new proof of a conjecture of Bollobás on embedding trees of bounded degree. The second result is a new proof of the Pósa conjecture. Let G = (W,E) be a graph on n vertices having minimum degree δ(G) ≥ n/2+ c log n, where c is a constant. Béla Bollobás conjectured that every tree on n vertices with bounded degree can be embedded into G. We show that this conjecture is true. In fact we show more, that unless G is very close to either the union of two complete graphs on n/2 vertices, or the complement, then a minimum degree of n/2 is sufficient to embed any tree of bounded degree. The kth power of C is the graph obtained from C by joining every pair of vertices at a distance at most k in C. 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. The conjecture was proven for n> n0 by Komlós, Sárközy and Szemerédi in [17] using the Regularity Lemma and Blow-up Lemma. The new proof removes the use of the Regularity Lemma and establishes the Pósa conjecture using combinatorial arguments, thus vastly reducin