Syllabus
Notation, motivating problems, the concept of a proof, proof by induction.
Combinatorics:
- Relation: mapping (function, permutation), equivalence.
- Partial ordering: chains and antichains, large implies tall or wide.
- Combinatorial counting: the number of subsets, of subsets of size k, of all mappings, of all injective mappings, of permutations.
- The binomial theorem. Estimates the factorial function and binomial coefficients.
- Inclusion-exclusion formula, applications (hatcheck lady).
Probability:
- Probability space (at most countable, all subsets are events).
- Independent events, conditional probability.
- Random variable: distribution function, expectation, linearity, most common distributions.
Graph theory:
- Elementary notions: complete graph, complete bipartite graph, path, cycle, vertex degree, subgraph, isomorphism.
- Handshaking lemma.
- Eulerian graphs: trail, walk, characterisation, including directed case, strong and weak connectivity.
- Trees: various characterisations, existence of a leaf.
- Planar graphs: Euler's formula, maximum number of edges.
- Graph coloring: characterisation of bipartite graphs, d-degenerate graphs, 5-color theorem for planar graphs (Kempe's chains).
Optional topics:
- Erdős-Szekeres lemma on monotone subsequences.
- Probabilistic proofs (e.g. existence of a 3-paradoxical tournament).
- Graph score.
- Platonic solids.
- Sperner's lemma, application on the HEX game.
Annotation
Introduction to combinatorics and graph theory. We lay stress on active knowledge of basic definitions and methods (relation, mapping, graph, exact formulation of mathematical theorems, problem solving and proofs of simple statements).