Diskrete Mathematik II - Discrete Mathematics II

Winter 2013-2014




In a nutshell...

Starting: 15 October 2013

Place: Arnimallee 6, SR 032 Seminarraum

Lectures: Tuesday and Wednesday , 08:00-10:00

Problems: Tuesday 12:00-14:00

More fun: I will be available in my office at Tuesday 10:00-12: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.fu-berlin.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...



Further Reading



(1st session) (Diestel, Chapter 1) Warm-up: 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).

(2nd 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.

Scan -Warm-up

Set 0

Set 1

(see little correction in Probl 1!)


(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: 3-dimensional 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 - Robertson-Seymour Theorem (No proof). Examples.

Lovász, Graph Minor Theory

Scan – Planarity and graph minors


(Diestel, 12.1 and 12.2) Graph Minors: quasi - ordered and well quasi - ordered sets (wqo). Formulation of Robertson-Seymour Theorem in terms of wqs sets. Equivalence of the two versions of R-S 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.

Set 2


(Diestel, 12.2) Graph Minors: End of the proof of Kruskal's Theorem.

(Diestel, 2.1) Matching Theory: matching, perfect matchings and k-factors 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)

Scan - Matching Theory


(West, 3.3, Diestel 2.1-2.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 k-regular bipartite graph with |A|=|B| has a perfect matching, every 2k-regular graph has a 2-factor and every bridgeless cubic graph has a 1-factor. Lovász-Plummer Conjecture (now T) for the number of perfect matchings in bridgeless cubic graphs.

Set 3


(West, 3.3, Diestel 2.1-2.2) Matching Theory: consequences of Tutte's Thm: every bridgeless cubic graph has a 1-factor. Lovász-Plummer Conjecture (now Thm) for the number of perfect matchings in bridgeless cubic graphs.

(Diestel 3.1-3.2, West 4.1) Connectivity: vertex and edge connectivity: separating sets (separating sets of edges), k-connectivity and k-edge-connectivity. Relation between connectivity and edge connectivity: Whitney's Theorem. Connectivity and edge connectivity is equal for cubic graphs.

Scan - Connectivity


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

Set 4


(West 4.2) Connectivity: x,y-separating 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.


(1st session) (West 4.2) Connectivity: Expansion Lemma, Dirac's Fan Lemma and consequences.

(Diestel 5.1-5.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. Welsh-Power Theorem for colouring vertices in terms of degree sequences. Brooks Theorem (No Proof).

(2nd session) (Diestel 5.1-5.2, West 5.2) Colouring: Colouring and planar graphs: 6-colour Proposition, 5-colour Theorem and 4-colour Theorem (No proof for the last one). An example of the Scan Method in the plane. Mycielski 's construction for triangle-free graphs with high chromatic number.

Scan – Graph Colouring

Set 5


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.


(Diestel 5.3) Edge colouring: proof of Vizing's Theorem. König's Theorem for bipartite graphs.

(Diestel 6.1-6.2) flows on graphs: oriented graphs, networks, and flows on networks. Capacity and circulation of a cut. Ford-Fulkerson Theorem (MAX flow - MIN cut Thm)

Scan – Flows on graphs

Set 6


(Diestel 6.3-6.4-6.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 . k-flows and the flow number. Tutte's Theorem for flows modulo k. Consequences: 2-flows iff all degrees are even. Bridgeless cubic graphs have3-flows iff they are bipartite. 5-flow Conjecture. Seymour's 6-flow Theorem.


Review of Landau's O notation.

(Jukna, 7.2-8.3) Extremal set theory: motivation and questions. Intersecting families of subsets and k-intersecting families: Erdos-Ko-Rado Theorem. Kruskal's circular proof. Chains and antichains in a lattice. Sperner's Theorem. Proof by means of LYM Inequality.

Scan – Landau noatation

Scan – Extremal Set Theory



¡Special session!: Tutorial session


(Diestel 7.1-10.1– Jukna 4.3-4.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 triangle-free graphs and Mantel's Theorem (via Cauchy – Schwartz). Extremal constructions for K_{r+1}-free graphs: Turan graphs T_{r,n}.

Aigner, Turan's graph Theorem

Scan: Extremal Graph Theory + Szemerédi's Regularity lemma

Set 7

(see the little correction in Probl. 3.1!)


(Diestel 7.1 – Jukna 4.4) Turan's graph Theorem (proof by induction). Statement of the Erdös-Stone 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).


(Diestel 7.4) Szemerédi's Regularity Lemma: motivation from random graphs. epsilon-pair and epsilon-partition. 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.

Notes with more details on SRL

Set 8


(Personal notes): Triangle Removal Lemma. Applications in combinatorial number theory: k-APs 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.


(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.


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.

Ramsey Theory

Set 9

MOCK EXAM (Deadline: 14th January)- The correction of the Mock Exam


(Jukna 4.9, Diestel 9.1-12.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 well-quasi ordered sets.

Note on the proof of Van der Waerden's Theorem

Set 10


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


(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.

The Probabilistic Method

Set 11


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


The probabilistic method (Alon, Spencer 2-3, 17): first moment method: balanced vectors, crossing number of a graph. Alteration method: existence of large independent subset.

Set 12

See the little correction in Probl 4)


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.


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.)

Set 13


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.


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.

Enumerative Methods


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.


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


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

The FINAL exam, and the solution of Problem 5

The MAKE-UP 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.