|
|
Course Announcement: (21-801)
The
Regularity Lemma/Extremal Graph Theory
In 1941, Turán's theorem ushered in the era of a discrete mathematical subtopic known as `extremal graph theory'. Extremal graph theory is the study of how the intrinsic structure of graphs ensures certain types of properties (e.g., cliques, colorings and spanning subgraphs) under appropriate conditions (e.g., edge density and minimum degree).
A sterling example of this is Dirac's theorem (1952), which ensures a Hamilton cycle in an n-vertex graph whenever the minimum degree is at least n/2. In addition, there is the Hajnal-Szemerédi result (1970) which implies that every graph on n vertices (n divisible by k) with minimum degree at least (k-1)n/k has a spanning subgraph of vertex-disjoint k-cliques.
We shall discuss these, but focus our attention on two recent tools that have become powerful tools in this area of mathematics: the Regularity lemma (1978) and the Blow-up lemma (1997). These have been used, often in tandem, to produce a variety of surprising results.
In fact, the Regularity lemma has proven quite versatile. It has applications not only in graph theory, but also among other topics from hypergraphs to number theory. We will discuss some of these as well.
This is a very active area of research and in this course we will investigate these techniques and how they have been used in recent publications.
Prerequisites: A knowledge of graph theory and some discrete probability.
Website: http://www.math.iastate.edu/rymartin/CMU801/CMU801.html
Email:
rymartin@math.iastate.edu
