Let K_{s,t} denote the complete bipartite graph where the two parts of the bipartite graph have s and t vertices respectively. For given s, t ≥ 1, what is the maximum number of edges in a graph on n vertices which does not contain K_{s,t} as a subgraph? An upper bound for this number is given by the well-known Kővári-Sós-Turán theorem. During the lecture, we will introduce this theorem and discuss the intuition behind proving a far reaching generalisation of it using a powerful method called Dependent random choice. If time permits, we will also briefly discuss the ordered variants of these theorems which have many connections to other areas of mathematics and theoretical computer science.
Dependent random choice and its variants
21.05.2024 09:00 - 09:20
Organiser:
Fakultät für Mathematik, Dekan Radu Ioan Boţ
Location:
Seminarraum 06, 1. OG