Combinatorics and Graphs 1 (Winter 2023/24)
This course covers a number of topics in combinatorics and graph theory:
generating functions, finite projective planes, flows in networks, graph connectivity, Ramsey theory, extremal graph theory, error correcting codes.
Prerequisites: "Discrete Mathematics" (essential). "Linear algebra 1 & 2", "Analysis 1" (recommended).
The exam will be written.
Reading materials:
- Lecture notes by Dr Penev.
- [MN] J. Matoušek, J. Nešetřil: Invitation to Discrete Mathematics (2nd Ed), Oxford University Press.
- [B] B. Bollobás: Modern graph theory (corrected Ed), Springer.
- R. Diestel: Graph Theory (5th Ed), Springer.
Home assignments
There will be 5 homework sheets in total. Each problem is worth 12 points.
To get a zápočet you need 50% of the overall points. Additionally, regular attendance of the tutorials is required.
Old zápočets remain valid if they were obtained last year in *my* course. Otherwise they are not valid.
Solutions are to be submitted via the
The Postal Owl. The deadlines are sharp, no extensions. I recommend using LaTeX.
Tutorial notes
Class Worksheet 1
Class Worksheet 2
Class Worksheet 3
Class Worksheet 4
Class Worksheet 5
Class Worksheet 6
Class Worksheet 7
Class Worksheet 8
Class Worksheet 9
Class Worksheet 10
Class Worksheet 11
Class Worksheet 12
Syllabus
- Lecture 1 (3.10): Inroduction. Recap of the O()-notation, factorials, and binomial coefficients. Stirling's formula and its consequences. Proof of Stirling's formula.
References: Notes chapter 1, Sir Timothy Gowers's blog
- Lecture 2 (10.10): Generating functions: definition, examples. Taylor series, Partial fraction decomposition. Resolving linear recursions: Fibonacci numbers.
References: Notes chapter 2, [MN] chapter 12.
- Lecture 3 (17.10): The toolbox for operations on gf's. Examples: basic applications, Fibonacci revisited, coin exchange problems, Catalan numbers, asymmetric random walks.
References: Notes chapter 2.
- Lecture 4 (24.10): Finite projective planes. Introduction and basic properties. Duality.
References: Notes chapter 3, [MN] chapter 9.1.
- Lecture 5 (31.10): Latin squares: orthogonality and connection to finite projective planes. A construction of projective planes using finite fields.
References: Notes chapter 3, [MN] chapters 9.3 and 9.2.
- Lecture 6 (7.11): Flows in networks. Max-flow min-cut. The Ford-Fulkerson algorithm.
References: Notes chapter 4, [B] chapter 3.1.
- Lecture 7 (14.11): Matchings in graphs. Hall's theorem: two proofs. Completion of Latin rectangles. Theorems of Kőnig and Tutte: statements.
References: Notes chapter 4, [B] chapter 3.3.
- Lecture 8 (21.11): Graph connectivity. Menger's theorem.
References: Notes chapter 5, [B] chapter 3.2.
- Lecture 9 (28.11): Extremal problems and double counting. Theorems of Mantel, Kővari-Sós-Turán (extremal number of the 4-cycle), and Sperner.
References: Notes chapter 6.
- Lecture 10 (5.12): Cayley's formula, Prüfer code. Ramsey's theorem for finite graphs: upper bounds.
References: Notes chapters 6, 7.
- Lecture 11 (12.12): Ramsey lower bound via probabilistic method. Ramsey for hypergraphs and infinite graphs/hypergraphs.
References: Notes chapter 7.
- Lecture 12 (19.12): Error correcting codes. Introduction, examples, general bounds.
References: Notes chapter 8.
- Lecture 13 (9.1.2024): Linear codes. Hamming codes.
References: Notes chapter 8.