Discrete Mathematics II
Winter 2011/12.
|
Exercises.
Exercise Sheet 1. (23.10: slight misprint corrected, 10.25:
Problem 4 shifted for next week)
Exercise Sheet 2.
Exercise Sheet 3. (26.10: Problem 2 and 3 swapped, error corrected)
Exercise Sheet 4. (7.11: Problem 5(ii) fixed; 10.11: Problem 3 clarified)
Exercise Sheet 5.
Exercise Sheet 6.
Exercise Sheet 7.
Mock Final (2.12: Problem 3 fixed)
Exercise Sheet 8.
Exercise Sheet 9.
Exercise Sheet 10.
Exercise Sheet 11. (16.1: corrected Problem 4, both parts; added
clarification to Problem 2.)
Exercise Sheet 12.
Exercise Sheet 13.
Exercise Sheet 14.
Covered material.
Week 1: (West, Chapter 6) planar drawing/embedding, planar graphs, plane graphs,
Jordan Curve Theorem (JCT) (no proof), face of a plane graph, dual graph, Handshaking
Lemma for dual graphs, charcterization of cycles of a graph in
terms of the dual,
characteriztaion of planar bipartite graphs in terms of the dual;
outerplanar graphs (K_4 and K_2,3 are not outerplanar,
the minimum degree of outerplanar graphs is at most 2);
Euler's formula, Applications: maximum number of edges in a
planar graph, in planar bipartite graph; the Platonic polyhedra,
two proofs of K_5 and K_3,3 not being planar (conflicting edges +
JCT, Euler's formula);
Kuratowski's Theorem (no proof), minors in graphs, Wagner's
Theorem (exercise), Graph Minor Theorem of Robertson and
Seymour (no proof -:)); Four Color Problem, Six Color Proposition,
Five Color Theorem.
Week 2: (West Chapter 6, Chapter 3.3)
proof idea of 4CT, Corollary of Graph Minor Theorem: every
minor-closed family of graphs (like planar graphs) has a
characterization with a finite set of forbidden minors. crossing
number, crossing number of K_6 and K_3,2,2, estimates for crossing
number of K_n, (lower bound based on averaging, upper bound based on
drawing on the ctlinder) asymptotic notation (Big O), conjecture on
the crossing number of the complete bipartite graph (drawing with
points on the two coordintae axis);
matchings: recall thms about matchings in bipartite graphs,
Tutte's condition for existence of perfect matching in general
graphs, application: Petersen's Thm on the existence of a perfect
matching in 3-regular graphs without a cut-edge.
Week 3: (West Chapter 3.3, 5.1)
Tutte's Theorem characterizing graphs with a perfect matching;
Berge's Formula for the size of a maximum matching;
colorings: committee-scheduling problem,
proper coloring, chromatic number, color-critical graphs, lower bound
for the chromatic number in terms of the clique number, lower
bound in terms of the independence number, examples when these
bounds are not tight, interval graphs, greedy coloring
procedure, perfect graphs, Strong
Perfect Graph Theorem (no proof) Weak Perfect Graph Theorem (no
proof), upper bounds for the chromatic number in terms
of maximum degree, in terms of degeneracy;
Week 4: (West Sections 5.1, 5.2, 7.1) Brooks' Theorem,
Block-decomposition of connected graphs, Mycelski's Construction,
Hajos' Conjecture, every 4-chromatic graph contains a K_4 subdivision
Hadwiger's Conjecture (no proof); Edge-colorings: line graphs,
Examples: clique, bipartite graphs, Petersen graph, Vizing's Theorem.
Week 5: (West Sections 7.1, 8.4, 3.2) Vizing's Theorem (proof by Schrijver);
scheduling committees with common members and individual time
restrictions, list coloring, k-choosable/list-k-colorable graph, list-chromatic number, simple upper and lower bounds, it can be arbirarily far
from chromatic number, List Coloring Conjecture, Stable Matching Theorem.
Week 6: (West Sections 8.4, 7.2, Appendix B) Galvin's Theorem (List Coloring Conjecture
for the line-graph of the complete bipartite graph), kernel of a digraph,
kernel-perfect orientation, every planar
graph is 5-choosable; Hamilton cycle, Hamiltonian graphs, P vs. NP and
co-NP (perfect matching in bipartite graphs vs. Hamiltonicity),
toughness, Hamiltonian graphs are 1-tough, examples, Toughness
Conjecture of Chvatal, sufficient condition for Hamiltonicity involving the minimum
degree (Dirac's Theorem)
Week 7: (transparencies, West Sections 7.2, 5.2.2, Diestel Section
7.1)
sufficient condition for Hamiltonicity involving connectivity
(Chvatal-Erdos), Ore's Theorem, Hamiltonian closure; extremal
problems, examples, maximum number of edges in r-colorable graphs,
Turan's Theorem, Turan number, Erdos-Stone
Theorem, Erdos-Simonovits Corollary, The Turan number of the
four-cycle, further results and conjectures
Week 8: (transparencies, notes, Diestel Sections 7.4, 7.5) Erdos-Stone Theorem (proof by counting), Regularity Lemma of
Szemeredi (no proof), epsilon-regular pair, epsilon-regular partition,
Proof of Erdos-Stone by Regularity Lemma
Week 9: (transparencies, notes) Erdos-Turan Conjecture, Szemeredi's
Theorem (no proof), Roth's Theorem, Triangle Removal Lemma (HW),
Behrend's Construction, van der Waerden's Theorem
Week 10: (transparencies, notes) van der Waerden's Theorem, bounds,
Turan-type problems/Ramsey-type problems, Ramsey's Theorem for
graphs, bounds, constructions (Paley graph, Turan graph),
Happy Ending Problem (theorem of Erdos and Szekeres),
Week 11: (transparencies, notes) Ramsey's Theorem for hypergraphs, Hypergraph Turan numbers
(3-uniform 4-clique and Fano plane), Erdos-Rado Sunflower Lemma, bounds, posets
Sperner's Theorem (max width of the Boolean poset), min/max theorems
for posets (Dilworth's Theorem),
Week 12: (Jukna: 14.1, 14.2, 14.3.3, transparencies)
Erdos-Ko-Rado Theorem on the maximum
size of a k-uniform intersecting family, Eventown Construction,
Oddtown Theorem, Linear Algebra Bound,
Not-necessarily-uniform Fischer Inequality, chromatic number of the
unit-distance graph of the n-dimensional Euclidean space
Week 13: (Jukna, transparencies) Even More General Oddtown Theorem
(linear independence of functions to F, multilinearization);
existence proofs, averaging, probabilistic method, exponential lower
bound for Ramsey number R(k,k), for van der Waerden number W(2,k),
linearity of expectation, Crossing Lemma, application: maximum number of edges in a
unit-distance graph on n vertices (improvement on HW exercise).
Week 14: (Jukna) lower bound for independence number of a graph (proof using
linearity of expectation), proof of Turan's Theorem by probabilistic
method, graphs with large girth and large chromatic number (Erdos, deletion method),
mutual independence, Lovasz Local Lemma (proof with constant 4,
statement with constant e),
improvement of the lower bounds for the van der Waerden number W(2,k)
and the Ramsey number R(k,k)
Week 15:committee selection problem, problem of independent transversals
in bounded degree graphs, proof of an upper bound of 2ed using the
Local Lemma, construction of graphs without independent transversal
and part size 2d-1, topological proof of the tightness of this
construction (triangulations, Sperner's Lemma, 2m-degenerate
triangulation of the m-dimensional ball with triangulated boundary.)
Below are some transparencies that contain a skeleton of many
(but certainly NOT all) topics of the lectures;
Planarity
Matchings
Vertex coloring
Edge coloring
List coloring
Hamilton cycles and NP
Extremal graph theory
Regularity Lemma (7.1: small corrections)
Supplementary notes for the Erdos-Stone Theorem
van der Waerden's Theorem and Ramsey's Theorem (10.1.: small correction
to unify notation)
Notes for vdW and Ramsey
Extremal problems for hypergraphs
Linear Algebra Method