On a New Method in Graph Theory

Dr. Gabor N. Sarkozy
Department of Mathematics
University of Pennsylvania

Friday, February 16, 1996
11 a.m. - 12 noon
Fuller Labs 320

We present a new method based on the Regularity Lemma for finding certain special spanning subgraphs of dense graphs. Two typical applications of this method:

(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.
(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.

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT