Go to course navigation

7. Extremal Graph Theory

In the seminar, we covered extremal graph theory and the Kővári-Sós-Turán theorem for complete bipartite graphs. Recall that $K_{a,b}=(W,F)$ is the complete bipartite graph with $W = A \mathbin{\dot{\cup}} B$ , $|A|=a$ , $|B|=b$ and $F=\{uw : u\in A, w\in B\}$ .

Your task is to choose one of the problems below and prove it.

Problems

Problem 1. Prove that for fixed $b \geq 2$ , every graph $G=(V,E)$ on $n$ vertices containing no $K_{2,b}$ as a subgraph satisfies $|E| = O\!\left(n^{3/2}\right)$ .

Problem 2. Prove the Kővári-Sós-Turán theorem: for fixed $a \geq 2$ and $b \geq a$ , every graph $G=(V,E)$ on $n$ vertices containing no $K_{a,b}$ as a subgraph satisfies $|E| = O\!\left(n^{2-\frac{1}{a}}\right)$ .

Problem 3. Prove that $n$ points in $\mathbb{R}^2$ span at most $O\!\left(n^{3/2}\right)$ pairs of unit distance.

Instructions

Read the task and solve it by yourself. In case of plagiarism, your homework will not be considered solved.
Then, submit a scanned and hand-written solution as a single PDF file using MS Teams.
The deadline for submission is April 13, 2026, 23:59. The deadline is strict.