Robert Šámal

Combinatorics and graph theory 3 -- Kombinatorika a grafy III (NDMI073) 2020/21

Extent: Fall 2/2 Ex, C

Lecture: Mon 10:40 in Zoom
Exercises: Mon 12:20 in another Zoom

Exam

There are two versions of the exam. The first is the usual oral exam (in Zoom). Exam dates are in SIS. (If you need more, we can discuss -- doing exams after the exam period is possible.) The second version is a take-home exam. To pass with "an A", you need to solve two out of the three problems in this list. Write down the solutions, if needed we will settle the unclear points over email (or perhaps over zoom :) ). If you use the second method, please give me a couple of days before you need the grade.

Literature

[ZD] Web of Zdeněk Dvořák
[D] R. Diestel: Graph Theory
[AS] N.Alon, J.Spencer: Probabilistic method

Covered material

5.10.2020

Classes closed on subgraphs/induced subgraphs/topological minors/minors.
Defining a class of graphs by a list of forbidden subgraphs/minors/etc.
Video from the class.
Lecture notes by Zdeněk Dvořák that we mostly followed.
Whiteboard from the class.
Exercises
Exercises with some solutions
The video from the exercise session has basically no content (nothing was recording during the break-out rooms). I will try a different setting next time, or possibly we will spend more time presenting the solutions. Let me know if you want to take part in the class but cannot participate in the Zoom meetings!

12.10.2020

Minor - alternative definition.
Clique-sum decomposition.
Hadwiger conjecture
Forcing clique (subgraph/topological minor/minor) by many edges.
Linkedness.
Video from the class.
Whiteboard from the class.
Exercises.

19.10.2020

Forcing clique (subgraph/topological minor) by many edges.
Linkedness.
Video from the class.
Whiteboard from the class.
Exercises.

26.10.2020

2.11.2020

Tree decompositions: brambles, algorithms.
Video from the class.
Whiteboard from the class.
Exercises.

9.11.2020

Final notes on tree decompositions (mostly just statements of results): complexity to find, grid theorem, WQO, graph minor theorem, description of graphs of tw at most k.
Szemerédi's regularity lemma: definitions, statements. Lemma finding enough graph with many neighbors in a set (with a proof). Blow-up lemma (without a proof).
Video from the class.
Whiteboard from the class.
Exercises.

16.11.2020

Applying Szemerédi's regularity lemma to prove the blow-up lemma. Applying that to prove Erdos-Stone theorem.
Video from the class.
Whiteboard from the class.
Exercises.

23.11.2020

Proof of Szemerédi's regularity lemma.
Video from the class.
Whiteboard from the class.
Exercises -- same as last time. Last week we did 1,2, and part of 4.

30.11.2020

7.12.2020

Polynomials -- Chevalley–Warning theorem and Alon-Tarsi combinatorial Nullstellensatz.
Video from the class.
Whiteboard from the class.
Exercises.

14.12.2020

Packings and coverings -- overview of results of this type plus Tutte/Nash-Williams result for spanning trees.
Video from the class.
Whiteboard from the class.
Exercises.

21.12.2020

Graph limits -- intro, motivation, application for extremal graph theory.
Video from the class.
Whiteboard from the class.
Exercises.
Solution to part 2.

4.1.2021