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