Princeton Discrete Math Seminar


Title:

Embedding theorems in extremal graph theory

Speaker:

Endre Szemeredi
Rutgers University

Place:

Fine Hall 224
Princeton University

Time:

4:00 pm
Thursday February 13, 1997
Abstract:

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