Extremal Combinatorics — ECO

Instructor:  Dr. Ervin GYŐRI
Text: R. Diestel, Graph Theory and handouts

Prerequisite: Some basics of discrete mathematics is needed for this course. No prior knowledge of combinatorics or graph theory is required.

Course description: Classical chapters of (extremal) graph and hypergraph theory, and on extremal problems from discrete geometry and number theory, including "cutting-edge" theorems (some of them have not appeared yet).

Topics:

• Basics: Graphs, paths and cycles, independent sets, cliques, trees, spanning trees, cycle structure of graphs
• Problems from geometry and number theory: Art gallery problems, number theory problems requiring graph theory. Polyominoes, Gyori’s minimax theorem on rectangle covers.
• Matchings, Hamilton cycles, 2-factors: Matchings, Hall's theorem, Tutte's theorem, stable matchings. Sufficient conditions for Hamiltonicity, theorems of Dirac, Ore, Pósa, Hamilton cycles containing given edges. 2-factors of exactly k cycles (with extra requirements).
• Colorings: The concept of chromatic number, its relation to the clique number, theorems on chromatic number. List chromatic number. Thomassen’s theorem on list coloring of planar graphs.
• High connectivity of graphs: Menger's theorems, k-connected and k-linked graphs, Gyori-Lovász theorem on k-connected graphs. Highly connected subgraphs, graph minors and topological complete subgraphs in dense graphs. Haggkvist-Thomassen theorem on cycles containing k prescribed edges.
• Extremal graph theory: Turán's theorem and related results, Erdos-Gallai extremal theorem on paths, maximum bipartite subgraphs, conjectures of Erdos on triangle-free graphs, extremal graphs not containing cycles of given length, graph Ramsey theorems.
• Regularity lemma: Szemerédi's regularity lemma, application: Erdos-Stone-Simonovits theorem.
• Extremal hypergraphs: Triangle-free hypergraphs, their relation to extremal bipartite graphs and combinatorial number theor Chromatic number of hypergraphs, 2-colorable hypergraphs