Tutorial 1. (02.03.2023) - VC-dimension
We solved problems 1, 3, 4, and 6. Then we hand-waved the solution for problem 10.
Selected topics in combinatorics
Tutorials
Tutorial 2. (09.03.2023) - VC-dimension
We solved problems 1, 2, 3, and 5. We discussed how problems 5 and 7 relate to the fact that the field of reals is NIP.
Tutorial 3. (16.03.2023) - PAC-learning, VC-dimension, epsilon-nets
We solved problems 5, 6, and 7. Then we discussed the statement of problem 4.
Tutorial 4. (23.03.2023) - Neural nets, PAC-learning, transversals, packings
We solved problems 1, 2, 3, and 4.
Tutorial 5. (30.03.2023) - Transversals, packings, (p, q)-theorem
We solved problems 1, 2, 4, and 5.
Tutorial 6. (13.04.2023) - Sample compression schemes, minimax theorem, (p, q)-theorem
We solved problems 1, 2, 3, and (a more general version of) 4.
Tutorial 7. (20.04.2023) - Haussler’s packing theorem, Szemerédi-Trotter theorem
We solved problems 1, 5, 6, and 7.
Tutorial 8. (27.04.2023) - Matchings with low crossing number, cutting lemma, Haussler’s packing theorem
We solved all problems (form the sheet).
Tutorial 9. (09.05.2023) - Range minimum queries
We discussed different solutions to the RMQ problem by following [Presentation 1] and [Presentation 2].
Tutorial 10. (11.05.2023) - Range minimum queires, Szemerédi regularity lemma
We solved problems 1, 3, 4, 5, 6, and 7.
Tutorial 11. (18.05.2023) - Szemerédi regularity lemma, property testing
We solved problems 1, 2, 6, 7, and 8.
Tutorial 12. (25.05.2023) - Introduction to discrepancy
I was absent and the replacement was done by dr. Kunal Dutta.
Tutorial 13. (01.06.2023) - Stability
We solved problems 1, 2, 3, 4, 5, and 6.
Tutorial 14. (15.06.2023) - Permutations
We solved problems 1, 2, 3, 4, 5, and 6.