Combinatorics 2021/22 – tutorials

This is a tutorial session for the lecture on Combinatorics (NMAG403) taught by Pavel Valtr and Jan Kratochvíl. The language (English/Czech) is yet to be decided. We are meeting on Wednesdays at 9.00 in K9. See the schedule.

• There will be 4 or 5 problem sets, each with a deadline.
• Each problem will be worth 1 point, there will be around 12 problems in total.
• Solutions submitted after the deadline will be worth 1/2 pnt.
• To get the credit ("zápočet"), you need to get 50 % of the total points.

Submitting the solutions

• You can submit the solutions by e-mail to matej AT kam.mff.cuni.cz
• Make sure that I can open (no absurd formats like docx, please use PDF) and read your solutions.
• You can use any language I will understand.
• The deadline is always before the start of the tutorial (that is, Wed at 9.00)!

Preliminary schedule

Date	Plan
29. 9. 2021	The basics. Problems.
6. 10. 2021	Some problems where randomness helps. Problems.
13. 10. 2021	Hall's theorem. Problems. HW set #1.
20. 10. 2021	Deadline for HW set #1.
27. 10. 2021	Tutte's theorem. Problems.
3. 11. 2021	Edmonds' algorithm. Problems. Bonus HW #1.
10. 11. 2021	List colouring. Problems. Deadline for bonus HW #1.
24. 11. 2021	Heawood and Vizing. Problems. HW #2
1. 12. 2021	Hamiltonian cycles. Problems. HW #3
8. 12. 2021	Kuratowski's theorem. Problems.
15. 12. 2021	Projective planes etc. Problems. HW #4
22. 12. 2021	Homomorphisms, graph convergence, graphons. Watch the recording from last year. Peter Cameron's note on homomorphisms, What is ... a Graphon?
5. 1. 2022	Additive combinatorics, monochromatic progressions and Szemerédi's regularity lemma. Watch the recording from last year.

Homework results

If you wish to be listed here, send me your permission and a nickname :).

Name	1.1	1.2	1.3	B.1	2.1	2.2	2.3	3.1	3.2	3.3	4.1	4.2	Sum
Pál Erdős	1	1	1	1	1	1	1	1	1	1	1	1	12
Erystil	1	1	1		1	1	1						6
Uaaaa	1	1	1		1	1	1						6
Enrico	1	1	1		1	1	1	1	1				8
Vingi	1	1	1		1	1	1						6
Melissa	1	1	1		1	1	1						6
BT168	1	1	1		1	1	1						6
Ollie	1	1	1		1	1	1						6
Parmenides	1				1	1	1	1	1	1			7
Martin	1			1	1	1	1	1	1	1			8
DH8/24		1	1					1	1				4