Combinatorics (Extremal Combinatorics) COM2B

Instructor:  Dr. Ervin GYŐRI
Text: B. Bollobás, Modern 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: A brief overview of the basic concepts of graphs, and hypergraphs will be followed by an in-depth discussion of some classical chapters of graph and hypergraph theory, focusing on extremal graphs and hypergraphs.


Basics: Graphs, paths and cycles, independent sets, cliques, trees, spanning trees, cycle structure of graphs

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

Colorings: The concept of chromatic number, its relation to the clique number, theorems on chromatic number. List chromatic number.

High connectivity of graphs: Menger's theorems, k-connected and k-linked graphs, Győri-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 Erdős on triangle-free graphs, extremal graphs not containing cycles of given length, graph Ramsey theorems,

Regularity lemma: Szemeredi's regularity lemma, Erdos-Stone theorem, and other applications

Extremal hypergraphs: Triangle-free hypergraphs, their relation to extremal bipartite graphs and combinatorial number theor Chromatic number of hypergraphs, 2-colorable hypergraphs