Spring 12: Monday, Wednesday, Friday 10:30am-11:20am (Ry 277)
Office hours.
Alexander Razborov
razborov@cs.uchicago.edu
Ryerson 257E Friday 11:30am-1pm and by appointment
Yuan Li
jsliyuan@gmail.com
Ryerson 178
Tuesday 1:30pm-2:55pm
Homeworks. There will be weekly homework assignments due at the beginning of class each Wednesday.
The first set will be released on April 3 (and due April 11). You are encouraged to work together on
solving homework problems. All students must turn in their own write-up of the solutions. If you work
with other people, you must put their names clearly on the write-up.
Exams. There will be a midterm (April 25) and a second exam (May 30).
Literature.
J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, available at Bondy's home page.
D. West, Introduction to Graph Theory (2nd ed.), Prentice Hall, 2001.
K. Rosen, Discrete Mathematics and Its Applications (6th Edition), McGraw-Hill Higher Education, 2012.
L. Babai, Automorphism groups, isomorphism, reconstruction.
Chapter 27 of the ``Handbook of Combinatorics'',
R. L. Graham, M. Grotschel, L. Lovasz, eds.,
North-Holland -- Elsevier, 1995, pp. 1447--1540, a preliminary version is available here.
A. Schrijver, On the history of the transportation and maximum flow problems, Mathematical Programming, 91 (2002) 437-445.
V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
R. Graham, B, Rothschild, J. Spencer, Ramsey Theory,
Wiley-Interscience, 1990.
N. Alon, J. Spencer, The Probabilistic Method, Wiley-Interscience, 2008.
B. Barak, G. Kindler, R. Shaltiel, B. Sudakov and A. Wigderson, Simulating independence: New constructions of condensers, Ramsey graphs, dispersers, and extractors, Journal of the ACM, Volume 57, Number 4, April 2010.
A. Razborov, On the Minimal Density of Triangles in Graphs, Combinatorics, Probability and Computing, Vol. 17, No 4, 2008, pages 603-618.
V. Nikiforov, The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc., 363:1599–1618, 2011.
A. Razborov, On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's (3,4)-problem, Proceedings of the Steklov Institute of Mathematics, Vol. 274, 2011, pages 247-266.
L. Lovasz, On the Shannon Capacity of a Graph, IEEE Transactions on Information Theory, IT-25 (1), 1979.
Progress and references.
First week: overview of the course. Graphs: pictorial and mathematical representations [1, Sct. 1.1]. Variations on simple graphs: loops and parallel edges [1, Sct. 1.1], directed graphs [1, Sct. 10.1], weighted graphs [1, Sct. 1.8], hypergraphs. Isomorphic graphs [1, Sct. 1.1], if you want to learn more about the Graph Isomorphism Problem, read the Wikipedia article. Degree sequences [1, Sct. 1. 5]. Handshaking theorem [1, Theorem 1.1]. If you have never encountered the double counting technique before, you can read Wikipedia article, and plenty of simple examples and applications (both related and unrelated to graph theory) are scattered across the textbook [3]. Erdos-Gallai theorem (with a sketch of a proof) [1, Exc. 1.5.6]. Havel-Hakimi theorem [2, Thm 1.3.31]. Walks, trails, paths; connectedness and connected components [1, Sct. 1.6]. Konigsberg bridges, Euler tours and trails [1, Sct. 4.1]. Subgraphs, induced and spanning subgraphs [1, Sct. 1.4]. Characterization of connected graphs possessing an Euler tour [1, Thm 4.1].
Second week: Characterization of connected graphs possessing an Euler tour cntd. The "kettle principle". Characterization of connected graphs with Euler trails [1, Cor. 4.1]. Hamiltonian paths and cycles [1, Sct. 4.2]. Dirac's theorem [1, Thm. 4.3]. Trees [1, Sct. 2]; various pieces of our "tree description" theorem are scattered along [1, Sct. 2.1], [1, Sct. 2.2], [2, Sct. 2.1], [3, Sct. 10.1] and numerous exercises therein. Spanning trees [1, Sct. 2.2] and a recursive formula to compute their number [1, Thm 2.8]. The determinant representation (just mentioned in class) [1, Sct. 12.2]. Cayley's formula [1, Thm 2.9]; our proof belongs to Pitnam, only we used a slightly different language (explicitly talked about rooted forests). It can be found (along with some useful references) in the Wikipedia article on double counting, and it is referred there as “the most beautiful of them all.”
Third week: Proof of Cayley's formula cntd. Vertex connectivity and edge connectivity [1, Sct. 3.1]. Relation between them [1, Thm. 3.1]. Blocks and cut vertices [1, Sct. 3.2]. Block-decomposition theorem: [2, Definition 4.1.20 + Alg. 4.1.23 + Exc. 4.1.34], see also [1, Fig. 3.3]. Menger's theorems (proof postponed): [1, Sct. 11.4] and [2, pages 166-169]. Whitney's theorem (stand-alone proof): [1, Thm. 3.2]. Digraphs [1, Sct. 10]; handshaking theorem [1, Exc. 10.1.2]. For a very good (but a bit outdated) exposition of the Caccetta-Haggkvist conjecture see West's page, and this is my own paper on the subject (with a comprehensive list of references). Reachability, diconnectivity, diconnected components [1, Sct 10.1].
Fourth week: Graph automorphisms (guest lecture by Prof. Babai) [4]. Isomorphic graphs [1, Sct. 1.2]; examples. Self-complementary graphs [1, Exc. 1.2.11]; examples. Graph automorphisms [1, Exc. 1.2.12]; examples. Vertex-transitive graphs [1, Exc. 1.2.13]; examples. Connected vertex-transitive graphs have long cycles [4, Prop. 3.16]. Networks [1, Sct. 11]. Flows [1, Sct. 11.1]. The colorful history of the max-flow min-cut theorem can
be found in [5]. Connection to the edge version of Menger's theorem [1, Thm 11.5]. Cuts [1, Sct. 11.2]. Max-flow min-cut theorem [1, Sct. 11.3].
Fifth week: Algorithmic issues behind the max-flow min-cut theorem: see the Wikipedia page. The vertex version of Menger's theorem [1, Thm. 11.6]. Matchings [1, Sct. 5]. Konig's theorem (with a stand-alone proof) [1, Thm 5.3]. Hall's theorem [Theorem 5.1] and its set-theoretic interpretation [1, Exc. 5.2.4]. Midterm. Marriage theorem: [1, Cor. 5.2]. You can read about algorithmic/complexity aspects of minimum vertex cover in Wikipedia article, and the book [6] remains a very good source of information about approximation algorithms in general. Characterization of graphs with a perfect matching [1, Thm 5.4].
Sixth week: Characterization of graphs with a perfect matching (cntd.) Independence
number [1, Sct. 7.1], cliques [1, Sct. 7.2] and their simple properties. Line graphs [2,
Sct. 7.1], see also Wikipedia article.
Gallai's theorem [1, Thm. 7.2]. Trade-off between independence and clique numbers in
vertex-transitive graphs [4, Corollary 3.11]. Ramsey's theorem [1, Thm. 7.5] (this is
a small improvement over what we did in class). [7] is an excellent and comprehensive
source of info on Ramsey theory. Lower bounds on Ramsey numbers [1, Thm. 7.6],
and [8] is a comprehensive source on the probabilistic method in combinatorics. Very recent advance on explicit constructions of Ramsey graph is [9] (the text is challenging!),
and the simple weak construction we did in class based on lexicographical products is taken from [1, Exc. 7.2.4]. This is a
little zoo of various graph
products, with links to almost all its inhabitants, and a sneak
preview of what we will (hopefully) do in the advanced part of this course can be found in
an article about Lovasz's theta-function.
Seventh week: You can read about Szemeredi's theorem in (as usual) Wikipedia article.
Try also to explore the links therein, and if you feel really adventurous and will be here
in 2013-14, you may request a repetition of my advanced course in arithmetic combinatorics. Mantel-Turan theorem: [1, Thm. 7.9] (as I remarked, we did only the simpler case $r=3$, where $r$ is the size of the forbidden clique). The quantitative version of Mantel-Turan theorem for $r<=5$ is solved in [10, 11], and some partial results toward Turan's (3,4)-problem, with references to the previous research, can be found in [12] (note to the wise: all this reading is very challenging). Chromatic number [1, Sct. 8] and its simple properties [1, Sct. 8.1]. $k$-critical graphs [1, Sct. 8.1] and their simple properties [1, Thm. 8.1 and 8.2]. Triangle-free graphs with arbitrarily large chromatic number [1, Thm. 8.7]. Graphs with arbitrarily large girth and chromatic number (with ideas of the proof) [2, Thm. 8.5.11]. Chromatic polynomial [1, Sct. 8.4] and the contraction-deletion formula for computing it [1, Thm. 8.6]. Stanley's theorem on the number of acyclic orientations [2, Thm. 5.3.27]. Planar graphs [1, Sct. 9]; that chapter contains an unusual amount of advanced material. Euler's formula [1, Sct. 9.3] (we did it slightly more generally).
Eighth week: Euler's formula cntd. Dual graphs [1, Sct. 9.2] and dual handshaking [1, Thm. 9.4]. Bounds on the number of edges in planar graphs [1, Cor. 9.5.2] and [1, Exc. 9.3.1]. $K_5$ and $K_{3,3}$ are not planar [1, Cor. 9.5.4] and [1, Cor. 9.5.5]. Graph minors [2, Def. 6.2.12], see also Wikipedia article where you can in particular read about Robertson-Seymour work. We stated Kuratowski's theorem without a proof, but, surprisingly, the latter can be found in [1, Sct. 9.5], even in a stronger form (subdivisions instead of minors). Five-color theorem [1, Thm. 9.11]. I encourage you to read about the history of the four-color theorem, it is entertaining and if you were ever curious what the British mathematician Lewis Carrollpossibly meant by snarks, check out this page. For Hadwiger conjecture see here; note that its stronger version known as Hajos' conjecture [1, Sct. 8.3] has been disproved. Hadwiger conjecture for $k=4$ [1, Thm. 8.5]. I am not aware of an accessible textbook covering fractional graph theory. Drop me a word if you know any, but meanwhile your best shot is your class notes and this Wikipedia page. Yes, and [13] is Lovasz's original article (that, among its many other virtues, is also a pleasure to read).
Ninth week: Adjacency matrix [1, Sct. 1.3]. We did parts and pieces of Lovasz's paper, significantly adapted. Notably (in the order of appearance) [13, Thm. 3], [13, Thm. 10], [13, Thm. 1] and [13, Thm. 2]. Questions and answers session. You can read about Hadwiger-Nelson problem in the Wikipedea article.