Syllabus updated January 13, 2008.
Introduction: 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).
This is primarily a seminar course. Many proofs will be presented
and the homeworks will require proofs, but many results will be
presented without the (often long and complicated) proof.
Grades and
Duties
- Homework 1, due Week 4 (5 or 7 Feb.)
- Homework 2, due Week 8 (4 or 6 Mar.)
- Homework 3, due Week 12 (8 or 10 Apr.)
- 25-minute presentation on a substantial extremal graph theory result,
done Week 14-15 (22, 24 or 29 Apr.)
The main course page at
http://orion.math.iastate.edu/rymartin/ISU608X/ISU608X.shtml
will have updates.
Preliminary Course Outline:
- Weeks 1-3: Basic extremal questions: Turán, Ramsey, König-Hall,
Hajnal-Szemerédi
- Weeks 4-5: An overview of the
probabilistic method
- Week 6: Random graphs
- Week 7: ε-regularity and properties of regular pairs
- Weeks 8-9: The Regularity Lemma -- forms, proofs and early applications
- Week 10: Degree form of the Regularity Lemma, the Key Lemma, number
of copies of H, covering copies of H, super-regular pairs,
early Regularity Lemma results
- Week 11: The Blow-up Lemma and packing results
- Week 12:
More packing results
- Week 13: Mean plus variance gives regularity
- Weeks 14-15: Presentations and additional topics
Texts: There is no formal textbook for the course. I
will cull my notes from a number of texts and papers. Note that Bollobás'
book is only $19.77 new. This is an excellent resource and covers
topics both in this course and beyond the scope of this course.
- General: Reinhard Diestel,
Graph theory. Third edition. Graduate Texts in
Mathematics, 173. Springer-Verlag, Berlin, 2005. xvi+411pp.
ISBN 978-3-540-26182-7; 3-540-26182-6
(Second edition free. Click here.)
- General: Béla Bollobás,
Extremal
graph theory. Reprint of the 1978 original.
Dover Publications, Inc., Mineola, NY, 2004.
xx+488 pp. ISBN 0-486-43596-2 (Price: $19.77)
- General: Stasys Jukna,
Extremal
Combinatorics. With applications in computer science. Texts
in Theoretical Computer Science. An EATCS Series. Springer-Verlag,
Berlin, 2001. xviii+375 pp. ISBN 3-540-66313-4 (Price: $69.95) On reserve in Parks library
- Random Graphs: Svante Janson, Tomasz Łuczak and
Andrzej Ruciński,
Random
graphs. Wiley-Interscience Series in Discrete Mathematics
and Optimization. Wiley-Interscience, New York, 2000.
xii+333 pp. ISBN 0-471-17541-2 (Price: $91.91) On reserve in Parks library
- Random Graphs: Béla Bollobás,
Random
Graphs. Second edition. Cambridge Studies in Advanced
Mathematics, 73. Cambridge University Press, Cambridge,
2001. xviii+498 pp. ISBN 0-521-80920-7; 0-521-79722-5
(Price: $50.00)
- Regularity Lemma: János Komlós and
Miklós Simonovits,
Szemerédi's
regularity lemma and its applications in graph theory.
Combinatorics, Paul Erdõs is eighty, Vol. 2
(Keszthely, 1993), 295--352, Bolyai Soc. Math. Stud., 2,
János Bolyai Math. Soc., Budapest, 1996. (On Reserve
in Math Library, 405 Carver)
- Regularity Lemma: János Komlós, Ali
Shokoufandeh, Miklós Simonovits and Endre Szemerédi,
The
regularity lemma and its applications in graph theory.
Theoretical aspects of computer science (Tehran, 2000),
84-112 , Lecture Notes in Comput. Sci., 2292, Springer,
Berlin, 2002.
- Probabilistic Method: Noga Alon and Joel Spencer,
The
Probabilistic Method. Second edition. With an appendix on
the life and work of Paul Erdõs. Wiley-Interscience Series
in Discrete Mathematics and Optimization. Wiley-Interscience
[John Wiley & Sons], New York, 2000. xviii+301 pp.
ISBN 0-471-37046-0 (Price: $93.58) On reserve in Parks library
- Linear Algebraic Method: László Babai and
Péter Frankl, Linear
Algebra Methods in Combinatorics. Preliminary Version 2.
Department of Computer Science, The University of Chicago, 1992.
(Price: $25.00 +shipping)
- Quasirandomness, Expanders, Spectral graph theory: Fan
R. K. Chung,
Spectral
graph theory. CBMS Regional Conference Series in Mathematics,
92. Published for the Conference Board of the Mathematical
Sciences, Washington, DC; by the American Mathematical Society,
Providence, RI, 1997. xii+207 pp. ISBN 0-8218-0315-8
(Price: $26.00)
Course
Description
In
1941, Turán's Theorem ushered in the era of a discrete
mathematical subtopic known as `extremal graph theory'.
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 a good portion of 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.
