# MA3J2 Content

**Content:
**• Partially order sets: Dilworth's theorem, Sperner's theorem

• Planar graphs: MacLane's criterion, Whitney's theorem, Five Color Theorem and its list coloring generalization

• Algebraic combinatorics: Symmetric functions, Young Tableaux, RSK correspondance

• Designs and codes: Latin squares, finite projective planes, self-correcting codes

• Geometric combinatorics: simplicial complexes, combinatorics of polytopes, relation to optimization

• Probabilistic method: the existence of high-girth graphs with high chromatic number, use of concentration bounds

• Matroid theory: basic concepts, relation to algorithms and optimization, matroid intersection theorem

• Regularity method: regularity lemma without a proof, the existence of 3-APs in dense subsets of integers

**Aims:
**To give the students an opportunity to learn some of the more advanced combinatorial methods, and to see combinatorics in a broader context of mathematics.

**Objectives:
** By the end of the module the student should be able to:

• state and prove particular results presented in the module

• adapt the presented methods to other combinatorial settings

• apply simple probabilistic and algebraic arguments to combinatorial problems

• use presented discrete abstractions of geometric and linear algebra concepts

• derive approximate results using the regularity method

**Books:
**R. Diestel: Graph Theory, Springer, 4th edition, 2012.

R. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux and More, Springer, 2013.