# C8.3 Combinatorics (2019-2020)

## Primary tabs

Part B Graph Theory is helpful, but not required.

16 lectures

### Assessment type:

- Written Examination

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.

The student will have developed an appreciation of the combinatorics of finite sets.

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.

- Bela Bollobás,
*Combinatorics*, CUP, 1986. - Stasys Jukna,
*Extremal Combinatorics*, Springer, 2007

*Please note that e-book versions of many books in the reading lists can be found on SOLO and ORLO.*