*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