C8.3 Combinatorics (2024-25)
Main content blocks
- Lecturer: Profile: Alexander Scott
Course information
General Prerequisites:
B8.5 Graph Theory is helpful, but not required.
Course Term: Michaelmas
Course Lecture Information: 16 lectures
Course Weight: 1
Course Level: M
Assessment Type: Written Examination
Course Overview:
An important branch of discrete mathematics concerns properties of collections of subsets of a finite set. There are many beautiful and fundamental results, and there are still many basic open questions. The aim of the course is to introduce this very active area of mathematics, with many connections to other fields.
Learning Outcomes:
The student will have developed an appreciation of the combinatorics of finite sets.
Course Synopsis:
Chains and antichains. Sperner's Lemma. LYM inequality. Dilworth's Theorem.
Shadows. Kruskal-Katona Theorem. Isoperimetry in the cube.
Intersecting families. Erdos-Ko-Rado Theorem. Cross-intersecting families. t-intersecting families. Fisher's Inequality. Frankl-Wilson Theorem. Application to Borsuk's Conjecture.
VC-dimension. Sauer-Shelah Theorem.
Combinatorial Nullstellensatz.
Shadows. Kruskal-Katona Theorem. Isoperimetry in the cube.
Intersecting families. Erdos-Ko-Rado Theorem. Cross-intersecting families. t-intersecting families. Fisher's Inequality. Frankl-Wilson Theorem. Application to Borsuk's Conjecture.
VC-dimension. Sauer-Shelah Theorem.
Combinatorial Nullstellensatz.
Section outline
-
-
Introductory questions. There will not be classes on this problem sheet, but solutions are available on the course webpage.
-
-
-
Registration start: Wednesday, 9 October 2024, 12:00 PMRegistration end: Friday, 8 November 2024, 12:00 PM
-
Class Tutor's Comments Assignment
Class tutors will use this activity to provide overall feedback to students at the end of the course.
-