SUBJECT
Discrete mathematics II
lecture
master
6
Semesters 1-4
Autumn/Spring semester
Probabilistic methods: deterministic improvement of a random object. Construction of graphs with large girth and chromatic number.
Random graphs: threshold function, evolution around p=logn/n. Pseudorandom graphs.
Local lemma and applications.
Discrepancy theory. Beck-Fiala theorem.
Spencer’s theorem. Fundamental theorem on the Vapnik-Chervonenkis dimension.
Extremal combinatorics
Non- bipartite forbidden subgraphs: Erdős-Stone-Simonovits and Dirac theorems.
Bipartite forbidden subgraphs: Turan number of paths and K(p,q). Finite geometry and algebraic constructions.
Szemerédi’s regularity lemma and applications. Turán-Ramsey type theorems.
Extremal hypergraph problems: Turán’s conjecture.
Alon-Spencer: The probabilistic method, Wiley 2000.