*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.

*Topics:*

* 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