C8.3 Combinatorics - Material for the year 2020-2021

We have updated our Undergraduate exams guidance in preparation for the Trinity Term examinations.

Please see our new webpages dedicated to TT exams.

Prof. Alex Scott
General Prerequisites: 

B8.5 Graph Theory is helpful, but not required.

Course Term: 
Course Lecture Information: 

16 lectures

Course Weight: 
1.00 unit(s)
Course Level: 

Assessment type:

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.

Intersecting families. Erdos-Ko-Rado Theorem. Cross-intersecting families.

VC-dimension. Sauer-Shelah Theorem.

t-intersecting families. Fisher's Inequality. Frankl-Wilson Theorem. Application to Borsuk's Conjecture.

Combinatorial Nullstellensatz.

Reading List: 
  1. Bela Bollobás, Combinatorics, CUP, 1986.
  2. Stasys Jukna, Extremal Combinatorics, Springer, 2007