Graph Theory - 0366.3267
Procedural Matters:
Prerequisite Courses:
Discrete Mathematics or Introduction to Combinatorics and Graph
Theory, Linear Algebra, Introduction to Probability.
Exercises will be given during the course and will account for 10% of the
final grade.
There will also be a final exam.
Text books:
Most of the topics covered in the course appear in the
books listed below (especially the first three).
Graph Theory,
by J. A. Bondy and U. S. R. Murty,
Springer, 2008.
Introduction to Graph Theory,
by D. B. West,
Prentice Hall, 1996.
Graph Theory,
by R. Diestel,
Springer, 1997.
The Probabilistic Method, third edition,
by N. Alon and J. H. Spencer, Wiley, 2008.
Brief syllabus:
Graphs and subgraphs, trees, connectivity, Euler tours,
Hamilton cycles, matchings, Hall's Theorem and Tutte's Theorem,
edge coloring and Vizing's Theorem,
independent sets, Turan's Theorem and Ramsey's Theorem,
vertex coloring, planar graphs, directed graphs,
probabilistic methods and linear algebra tools in Graph Theory.
More relevant information, to be updated during the term,
appears in:
Graph Theory
Additional relevant information, including exams from previous years,
appears in:
Graph Theory
Course Outline:
-
Oct. 18
Basic definitions and properties: graph isomorphism,
the adjacency and the incidence matrices, subgraphs and induced
subgraphs, the complement and the line graph of a graph, complete
and empty graphs, cliques and independent sets, bipartite graphs,
vertex degrees,
walks, trails, paths and cycles, girth and circumference,
connectivity and connected components,
Sperner's lemma (in dimension 2).
-
Oct. 25
Brouwer's fixed point theorem (in dimension 2),
trees and forests, basic properties of trees,
edge contraction and the contraction-deletion recursive
formula for the number of spanning trees, Cayley's formula,
Kirchhoff's matrix tree theorem.
-
Nov. 1
Proof(s) of Kirchhoff's matrix tree theorem,
connectivity of a graph.
-
Nov. 8
Highly connected subgraphs in graphs of large average degree
(Mader's theorem), edge-connectivity,
structural characterization of 2-connected graphs ("ear
decomposition"), blocks and block-decompositions, Menger's theorem.
-
Nov. 15
Proof of Menger's theorem,
Eulerian circuits,
Hamilton cycles, Dirac's theorem, Ore's theorem.
-
Nov. 22
The Chvatal-Erdos theorem, matchings, factors, and vertex
covers, Hall's marriage theorem and corollaries: every nonempty
regular bipartite graph has a perfect matching, every regular graph
with positive even degree has a 2-factor, systems of distinct
representatives, Konig's theorem, Tutte's matching theorem.
-
Nov. 29
Every bridgeless 3-regular graph has a perfect matchingr, vertex
coloring,
the Nordhaus Gaddum
theorem, the greedy coloring algorithm, degeneracy of a graph,
Brooks' theorem.
-
Dec. 6
Color-critical graphs, color-critical graphs have no cutvertices,
every (k+1)-critical graph is k-edge-connected (Dirac's theorem), a
construction of triangle-free graphs with large chromatic number,
graphs with large chromatic number and no short cycles, edge
coloring, Konig's theorem.
-
Dec. 13
Hanukkah
-
Dec. 20
Edge coloring: Vizing's Theorem. Ramsey's Theorem, the Ramsey
numbers r(k,ell), their computation for small k, ell, and the
upper bound of Erdos and Szekeres.
-
Dec. 27
Erdos' probabilistic lower bound for the Ramsey number r(k,k),
Multicolor Ramsey numbers, Schur's Theorem. Extremal Graph Theory:
Turan's Theorem.
-
Jan. 3
The theorem of Kovari, Sos and Turan.
Planar graphs: Kuratowski's Theorem, Euler's Formula, comments on
the Four Color Theorem and a proof that five colors suffice.
-
Jan. 10
Tools from linear algebra: the Graham Pollak Theorem (with the
proof of Tverberg), Fisher's Inequality, 3 regular subgraphs.
-
Jan. 17
Solution of homework assignments.
Exercises
List of Theorems
Remark: The final grade was
determined as follows: A=average grade of 4 homework assignments.
B=grade of final exam, where the weight of the best 4 answers is
0.9 and that of the fifth
answer is 0.1. C=max(B,0.9B+0.1A). The final grade is F=C, unless
C is bigger than 50 and smaller than 60, in this case F=60.
redesigned by barak soreq