Princeton Discrete Math Seminar


Embedding theorems in extremal graph theory


Endre Szemeredi
Rutgers University


Fine Hall 224
Princeton University


4:00 pm
Thursday February 13, 1997

Posa's conjecture states that if a graph G has minimum degree at least 2/3 n (n is the number of vertices of G) then G contains the square of a Hamiltonian cycle. Seymour's conjecture states that if the minimum degree is at least (k-1)/k n then G contains the (k-1)'th power of a Hamiltonian cycle. We prove that for any fixed k and all large enough n, Seymour's conjecture is true. We will discuss a method which can be used for similar problems. (Joint work with Janos Komlos and Gabor Sarkozy.)

Document last modified on February 12, 19997