
Diskrete Mathematik II  Discrete Mathematics IIWinter 20132014 


In a nutshell...
Starting: 15 October 2013
Place: Arnimallee 6, SR 032 Seminarraum
Lectures: Tuesday and Wednesday , 08:0010:00
Problems: Tuesday 12:0014:00
More fun: I will be available in my office at Tuesday 10:0012:00. Of course meetings can be also arranged by appointment.
Prerequisites: basic graph theory, combinatorics, algebra, analysis and probability.
Synopsis: This course serves as a natural continuation of the topics that are studied in an initial course of discrete mathematics. In particular, we will start exploring some basic (but fundamental!) concepts in graph theory, including planarity, matching theory, connectivity, colouring and hamiltonicity.
After this, we will continue to the second part of the course. This part will have the following question as a leivmotiv: how large or how small a collection of finite objects (graphs, sets, numbers, …) can be, if it has to satisfy certain restrictions?. This is the main question in extremal combinatorics, which is the topic we will cover here.
Finally, in the third part of the course we will finish exploring some differente techniques used in combinatorial theory, including probabilistic techniques, counting enumeration formulas and algebraic methods.
The prerequisites for this course are minimal. We shall need the fundamental notions arising from graph theory as well as basic concepts from linear algebra and discrete probability.
Feel free to contact me at jrue at zedat.fuberlin.de with any questions prior to the start of the course!
Requirements: the requirements of the course are here.
NEW: the abstract of the material for the final exam is here
What we have seen so far...
When? 
What? 
Further Reading 
Problems 
15/10/13 
(1^{st} session) (Diestel, Chapter 1) Warmup: graphs and multigraphs, degree and Handshaking Lemma, subgraph and induced subgraph, path and cycles, connectivity and separating sets, walks on graphs (Euler Tour, Hamiltonian cycle), glosarium of graphs. (West, Chapter 6.1) Planarity and Graph Minors: curves in the plane and Jordan's Curve Theorem (No Proof). (2^{nd} session) (West, Chapter 6) Planarity and Graph Minors: drawing of graphs, planar graphs and plane graphs (maps). Faces of maps. Dual map: construction and properties. Length of faces and Handshake Lemma for dual maps. Characterization of planar bipartite maps in terms of the dual. Euler's Relation. 

(see little correction in Probl 1!) 
16/10/13 
(West, Chapter 6, Diestel, Introduction of Chapter 12, Lovász paper) Planarity and Graph Minors: Proof of Euler's Relation by contracting edges, simple observations from ER and further consequences: 3dimensional polytopes, bounds for the number of edges in planar graphs, every planar graph have a vertex of degree <6. Characterization of planarity: K5 is not planar (applying JCT) and K3,3 is not planar (applying ER). Kuratowski's Theorem (No proof). Graphs on surfaces: representation of surfaces as two dimentional objects with identifications. Minor relation. Wagner's Theorem (Homework). Family closed by the minor relation. Wagner's Conjecture  RobertsonSeymour Theorem (No proof). Examples. 


22/10/13 
(Diestel, 12.1 and 12.2) Graph Minors: quasi  ordered and well quasi  ordered sets (wqo). Formulation of RobertsonSeymour Theorem in terms of wqs sets. Equivalence of the two versions of RS Theorem. Kruskal's Theorem for rooted trees: additional properties of wqo sets, a set with a relation is wqo then the subset of sets is also wqo (minimality+deconstruction, construction), Proof of Kruskal's Theorem using the ideas of the previous result. 


23/10/13 
(Diestel, 12.2) Graph Minors: End of the proof of Kruskal's Theorem. (Diestel, 2.1) Matching Theory: matching, perfect matchings and kfactors in graphs. Matching theory in bipartite graphs: alternating and augmenting paths. Vertex cover, König's Theorem and Hall's Theorem (Proof by choosing a convenient vertex cover and proof using König's theorem) 


29/10/13 
(West, 3.3, Diestel 2.12.2) Matching Theory: matchings in general graphs, Tutte's condition and Tutte's Theorem. Lovász proof of Tutte's Theorem. Consequences of Hall's Thm: every kregular bipartite graph with A=B has a perfect matching, every 2kregular graph has a 2factor and every bridgeless cubic graph has a 1factor. LovászPlummer Conjecture (now T) for the number of perfect matchings in bridgeless cubic graphs. 


30/10/13 
(West, 3.3, Diestel 2.12.2) Matching Theory: consequences of Tutte's Thm: every bridgeless cubic graph has a 1factor. LovászPlummer Conjecture (now Thm) for the number of perfect matchings in bridgeless cubic graphs. (Diestel 3.13.2, West 4.1) Connectivity: vertex and edge connectivity: separating sets (separating sets of edges), kconnectivity and kedgeconnectivity. Relation between connectivity and edge connectivity: Whitney's Theorem. Connectivity and edge connectivity is equal for cubic graphs. 


05/11/13 
(Diestel 3.13.2) Connectivity: structure of connected graphs: blocks and the block cutvertex graph. The blockcurtvertex graph is a tree. 2connected graphs: ear decomposition. 3connected graphs: lemma for the existence of an edge such that its contraction gives a 3connected graph. Tutte' Theorem for the structure of 3connected graphs in terms of contractions and K4. 


06/11/13 
(West 4.2) Connectivity: x,yseparating sets, Menger's Theorem (local vertex version, no proof). Applications: local edge version of Menger's Theorem for x,y edge separating sets (proof by using the line graph), global edge version. Global vertex version (proof by showing that deleting and edge reduces vertex connectivity by at most 1). Fans in graphs. 

12/11/13 
(1st session) (West 4.2) Connectivity: Expansion Lemma, Dirac's Fan Lemma and consequences. (Diestel 5.15.2, West 5.1) Colouring: chromatic number of a graph. Bounds for the chromatic number in terms of the clique number, the independence number and the number of edges. Example that the chromatic number could be different to the clique number. Greedy Algorithm to colour vertices. WelshPower Theorem for colouring vertices in terms of degree sequences. Brooks Theorem (No Proof). (2^{nd} session) (Diestel 5.15.2, West 5.2) Colouring: Colouring and planar graphs: 6colour Proposition, 5colour Theorem and 4colour Theorem (No proof for the last one). An example of the Scan Method in the plane. Mycielski 's construction for trianglefree graphs with high chromatic number. 


13/11/13 
Colouring: (Diestel 5.6) Girth of a graph. Erdos Theorem for the chromatic number and the girth. Perfect graphs. Examples: complement of a bipartite graph. Weak and Strong Perfect Graph Conjecture (No proof). (Diestel 5.3) Edge colouring: definitions and trivial bounds. Vizing's Theorem. 

19/11/13 
(Diestel 5.3) Edge colouring: proof of Vizing's Theorem. König's Theorem for bipartite graphs. (Diestel 6.16.2) flows on graphs: oriented graphs, networks, and flows on networks. Capacity and circulation of a cut. FordFulkerson Theorem (MAX flow  MIN cut Thm) 


20/11/13 
(Diestel 6.36.46.6) flows on graphs: sketch of the proof of MAX flow MIN cut Thm. Proof of vertex local version of Menger's Thm from MAX flow  MIN cut. Flows and groups: circulations and nowhere zero flows over abelian groups . kflows and the flow number. Tutte's Theorem for flows modulo k. Consequences: 2flows iff all degrees are even. Bridgeless cubic graphs have3flows iff they are bipartite. 5flow Conjecture. Seymour's 6flow Theorem. 

26/11/13 
Review of Landau's O notation. (Jukna, 7.28.3) Extremal set theory: motivation and questions. Intersecting families of subsets and kintersecting families: ErdosKoRado Theorem. Kruskal's circular proof. Chains and antichains in a lattice. Sperner's Theorem. Proof by means of LYM Inequality. 

NO HW! 
27/11/13 
¡Special session!: Tutorial session 

03/12/13 
(Diestel 7.110.1– Jukna 4.34.4) Extremal graph theory: philosophy and first questions: connectivity in terms of the number of edges, connectivity in terms of the minimum degree, Dirac's Theorem for the existence of Hamilton cycles in terms of the minimum degree. Extremal problems on subgraphs: Turan numbers. Extremal constructions for trianglefree graphs and Mantel's Theorem (via Cauchy – Schwartz). Extremal constructions for K_{r+1}free graphs: Turan graphs T_{r,n}. 
(see the little correction in Probl. 3.1!) 

04/12/13 
(Diestel 7.1 – Jukna 4.4) Turan's graph Theorem (proof by induction). Statement of the ErdösStone Theorem (epsilon notation and big O  little o notation, no proof). Erdos  Simonovits corollary. Examples. Analysis for bipartite graphs: Erdös Theorem for the cycle C_4 (upper bound, proof by double counting), Esther Klein's Theorem (lower bound, Homework using Sidon sets), Kövari  Sós – Turán's Theorem (Homework). 

10/12/13 
(Diestel 7.4) Szemerédi's Regularity Lemma: motivation from random graphs. epsilonpair and epsilonpartition. Szemerédi's Regularity Lemma. Comments on the number of vertices, the number of partite sets and the edge density (dense vs sparse graphs). Applications: counting lemma for triangles. 


11/12/13 
(Personal notes): Triangle Removal Lemma. Applications in combinatorial number theory: kAPs and Szemerédi's Theorem. Roth's Theorem: proof using the Triangle Removal Lemma. History of Szemerédi's Theorem and results for k=3. 

17/12/13 
(Personal notes, Jukna 25.1, Diestel 7.5) Behrend's construction. Sketch of the proof of Erdös  Stone Theorem using Szemerédi's Regularity Lemma. 

18/12/13 
Finish of the sketch of the proof of Erdös – Stone Threorem. (Jukna 4.9, 25.1) Ramsey Theory: connections with extremal combinatorics. Van der Waerden's numbers and Van der Waerden's Theorem. Ramsey number for graphs: upper bounds. 

MOCK EXAM (Deadline: 14^{th} January) The correction of the Mock Exam 

07/01/14 
(Jukna 4.9, Diestel 9.112.1) Ramsey number for graphs: upper bound (4^k) using binomial coefficients, lower bound (2^(k/2)) by counting. Infinite Ramsey Theory: colouring of subsets of infinite sets, and monochromatic sets. Existence of infinite monochromatic sets. Application to wellquasi ordered sets. 


08/01/14 
(Diestel 12.1 personal notes) Application on wellquasi ordered sets. Van der Waerden's Theorem: toy example with W(2,3), sunflowers and generalized VdW numbers. Partial lemmas towards VdW thm proof. 

14/01/14 
(Personal notes) End of the proof of VdW theorem. Upper bounds for W(r,k). The probabilistic method (Alon, Spencer 1): basic notions on finite probability spaces (event, random variable, independence). Union bound, Erdos proof for the lower bound of R(k,k), Erdos proof for the existence of tournaments with property Sk. 


15/01/14 
The probabilistic method (Alon, Spencer 12): lower bound for VdW number W(2,k). Expectation of random variables and the first moment method. Examples: big bipartite graphs in given graph, sumfree subset of size n/3. 

21/01/14 
The probabilistic method (Alon, Spencer 23, 17): first moment method: balanced vectors, crossing number of a graph. Alteration method: existence of large independent subset. 
See the little correction in Probl 4) 

22/01/14 
The probabilistic method (Jukna 20.3, 18.11): Markov's inequality. The random graph model G(n,p). Erdos proof of the existence of graphs with large chromatic number and large girth. 

28/01/14 
The probabilistic method (Alon, Spencer 4): Second Moment Method: Variance and properties. Chebyshev's inequality. Application: distinct sums. Further properties of the variance. Properties of random variables that are assymptotically almost surely. (a.a.s.) 


29/01/14 
The probabilistic method (Alon, Spencer 4): Second Moment Method: more properties of the variance. Threshold functions on random graphs. Threshold function on random graphs for the existence of triangles. 

04/02/14 
Enumerative techniques (Flajolet, Ch1): sequences and generating functions. Linear recurrences: Fibonacci numbers. Triangulations of a polygon and Catalan numbers. Further properties of Generating functions. The philosophy behind the Symbolic Method. 


05/02/14 
Enumerative techniques (Flajolet, Ch2): the formalism of combinatorial classes: combinatorial class, size of an element . Generating function associated to a combinatorial class. Constructions: disjoint union, product, sequence construction. Applications: Fibonacci, decompositions of a polygon, Dyck paths. 

11/02/14 
Enumerative techniques (Flajolet): more examples: rooted embedded trees. Labelled combinatorial families and exponential generating functions. Labelled product and related constructions (set, sequence). 

12/02/14 
Enumerative techniques (Flajolet): Examples: permutations and cyclic permutations, labelled rooted trees. Lagrange inversion Formula and applications. 

The MAKEUP exam 
Some books that could help during the course are the following ones: Matousek, Nesetril: Invitation to Discrete Mathematics (basic reference), Bollobás: Combinatorics, van Lint, Wilson: A course in Combinatorics, Lovász: Combinatorial Problems and Exercises.
In each part we have we have the following references:
Part 1 (Graph Theory)
The basic reference in this part is West: Introduction to Graph Theory. We will will follow it in many of the lectures.We will use also the book Diestel: graph theory, which can be downloaded from the author's webpage.
Part 2 (Extremal Combinatorics)
We will use at certain points Jukna,Extremal Combinatorics and also Diestel: Graph Theory. Additional material will be announced.
Part 3 (Methods in combinatorics)
The classical reference for probabilistic methods in Alon, Spencer: The Probabilistic Method. We will also use Flajolet, Sedgewick: Analytic Combinatorics (which can be downloaded from the webpage of the first author) for enumerative methods.