Graph Theory for PhD students, FSF3700

Lecture Plan 2008

Classes are Thursdays 10.15-12.00 in room 3733
Nr	Date	Chapter in Diestel	Important Thm	Exercises
0	4/9	Introduction
1	11/9	1.1-1.4	1.4.3	1.3, 1.10, 1.14, 1.16
2	18/9	1.5-1.7, 2.1	2.1.1	1.20, 1.21, 1.23, 1.25, 2.2
3	25/9	2.2, 2.5	2.5.1	2.7, 2.12, 2.15, 2.21, 2.23, 2.24
4	2/10	3.1-4	3.3.1,3.4.1	3.7,3.9,3.10,3.16,3.17,3.21
5	9/10	7.1-7.3	Turan, Hadwiger Conj.	7.4, 7.9, 7.13, 7.30, 7.32, 7.34
6	16/10	7.4, Tao 1,4	7.4.1	T1,T2,T3 below*
7	20/10	7.5,9.1-2, Tao 4	7.1.2, 9.2.2	T4 below*
8	30/10	4.1-2,4.4	4.4.6	4.1,4.4,4.5,4.12,4.16,4.17,4.19
9	6/11	5.1-5.2	5.1.1, 5.2.4	3,7,15,23
10	13/11	5.3-5.4	5.3.2, 5.4.2	27,30,32
11	20/11	5.5	Strong perfect Graph Theorem	36,38,39,41,42
12	27/11	11.1-11.2	11.1.4, 11.2.2	1,2,3,4
13	1/12	11.3	11.3.2,11.3.4	6,7,8,10
14	11/12	Lovasz text 1.1-2.3	Perron-Frobenius	L1-L6, see below**
15	18/12	Lovasz text 2.4-2.6	Theorem 2.8	L7-L10, see below**

TBA - To Be Announced
* When Terence Tao received his fields medal 2006 at the International
Congress of Mathematicians he gave a talk on "The dichotomy between
structure and randomness, arithmetic progressions, and the primes".
Download Tao's paper and try to read sections 1 and 4 at least. The exercises are:

T1) Prove that the Gowers cube norm is a norm.
T2) Explain the special case of Lemma 4.2 when the weights are 0 or 1.
T3) Extend the sketch of proof 4.3 to a complete proof.
T4) Prove Szemeredi's theorem in the cases k=3 and k=4 by using
the regularity lemma as sketched on page 20-21 of Tao's paper.

**L1-L4 are from Exercise 2.1 on page 6. With spectrum is ment
the eigenvalues of the adjacency matrix A_G, i.e. the \lambda-vector.
L5) Prove Proposition 2.1
L6) Prove Proposition 2.3 a) and b)
L7) Prove Theorem 2.7
L8) Exercise 2.4
L9) Example 2.14 (Petersen + projective planes)
L10) Exercise 2.6
Last updated 2008-12-11.