# 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