Syllabus updated October 5, 2005.
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
Grades will be determined by four
equally-weighted items:
- Your service as scribe, transcribing
3 lectures into LaTeX.
- Homework 1, due around February
9.
- Homework 2, due around March 23.
- Homework 3, due around
April 25.
Scribe service: - The due date is 13 days from the time of
the lecture, so that I can post it in a timely fashion.
- Your name and the date of the lecture must appear in
the manuscript.
- No particular format is necessary.
- Email to rymartin@iastate.edu
the following files:
- .tex file
- .ps file
- .pdf file
- Any auxiliary files (.eps)
All files will be posted on the archive
page.
- If you are planning to give a seminar talk this semester
in any related seminar (see
Discrete
Math seminar, for example) you can be excused from a scribe
duty. See me first, this is subject to class registration.
|
Homework assignments: - Scheduled due dates for these
are R 2/9, R 3/23 and T 4/25. These dates can easily be
changed upon request.
- These problems will be distributed at least two weeks before the due date
and posted on the archive
page.
- Students may work together but must submit their own
work.
- Typed solutions are preferred. You may submit them electronically
if you wish.
|
The main course page at http://orion.math.iastate.edu/rymartin/ISU690I/ISU690I.shtml will have
updates as well as a general outline for the course.
Preliminary Course Outline:
- Week 1: Basic extremal questions: Turán, Dirac,
Hajnal-Szemerédi, Ramsey, anti-Ramsey
- Week 2: Brief intro to probabilistic methods and random graphs
- Week 3: ε-regularity and properties of regular pairs
- Weeks 4-5: The Regularity Lemma -- forms, proofs and early applications
- Week 6: Turán-type applications
- Week 7: (ε,δ)-super-regularity and the Blow-up Lemma
- Week 8-9: Applications of the Regularity and Blow-up Lemmas
- Week 10: Algorithmic aspects of the Regularity and Blow-up Lemmas
- Week 11: Expander graphs
- Week 12-15: Additional topics
Additional topics will be influenced by class interest. They can include:
The random graph: giant components, Hamiltonicity, k-cores
Linear algebraic methods in combinatorics
Linear programming methods in combinatorics
Probabilistic methods: second moment, Lovász Local Lemma, Chernoff bounds (2 weeks)
Partially ordered sets (2 weeks)
Sparse graph and hypergraph versions of the Regularity Lemma
Hereditary properties and using the Regularity Lemma inside the clusters
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 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.
