Kovari-Sos-Turan theorem

Question

Let $r \leq s$ be fixed natural numbers. Then by the Kővári–Sós–Turán theorem, any graph on $n$ vertices with at least $cn^{2-\frac{1}{r}}$ edges contains a complete bipartite subgraph $K_{r,s}$ for a constant $c.$

I was wondering if we can say that if we have at least $cn^{2-\frac{1}{r}}+1$ edges, then there are at least $c'n$ complete bipartite subgraphs $K_{r,s}$, for a constant $c'$?

For example, if a graph has at least $\frac{n^2}{4}+1$ edges, then it has at least $n$ triangles! I'm pretty sure the answer to my question should be Yes, but I do not know how to prove it.

Answer 1

The appropriate search term is "supersaturation". I think Theorem 11.1 in

Furedi, Z., Simonovits, M. (2013). The history of degenerate (bipartite) extremal graph problems. In Erdos Centennial (pp. 169-264). arxiv:1306.5167

implies the existence of a constants $c_1=c_1(r,s)$ and $c_2=c_2(r,s)$ such that a graph with $m>c_2n^{2-1/r}$ edges contains at least $c_1c_2^{rs}n^r$ copies of $K_{r,s}$.

Answer 2

@Megan, I think you meant in your original statement

Statement 1: Let $r$ and $s$ be fixed numbers. Then KST theorem says that for some constant $c = c(r,s)$, a graph with at least $c(r,s)n^{2-\frac{1}{r}}$ edges contains a copy of $K_{r,s}$.

[At any rate, it really should be made clear that the constant $c$ is growing with $s$ and $r$. I found myself confused by the original wording at least.]

If a graph w $c(r,s)n^{2-\frac{1}{r}}$ edges contains a copy of $K_{r,s}$ then for any positive $c'$, a graph in $G$ with $c(r,s)n^{2-\frac{1}{r}} + c'n$ edges definitely contains $c'n$ copies of $K_{r,s}$ given KSK stated above. Indeed, you can find a copy of $K_{r,s}$ in $G$ and remove an edge from the copy, and then find a copy of $K_{r,s}$ in the remaining graph ($G$ minus the edge removed), and so on and so forth, $c'n$ times, to get $c'n$ distinct copies of $K_{r,s}$.

If $c'$ is no larger than 1, then $c'n$ is small relative to $c(r,s)n^{2-\frac{1}{r}}$ so the following can be concluded from KSK theorem as written above plus the above paragraph:

Statement 2: Let $r$ and $s$ be fixed numbers. Then for some constant $\tilde{c} = \tilde{c}(r,s)$, a graph with at least $\tilde{c}(r,s)n^{2-\frac{1}{r}}$ edges contains at least $n$ copies of $K_{r,s}$.

In fact, you can use the above line of reasoning plus Statement 1 to show the existence of as many as $c(r,s)n^{2-\frac{1}{r}}$ copies of $K_{r,s}$ where $c(r,s)$ is as in Statement 1, but if you want that many copies then $\tilde{c}(r,s)$ grows to $2c(r,s)$ as in Statement 1.

the above argument probably can be tightened further.

Answer 3

Let's look at the case $r = 2$ and choose to interpret the question as asking how many $K_{2,2}$ or $C_4$'s one has in a graph with $n$ vertices and ex$(n, C_4)$ + 1 edges, where ex$(n, C_4)$ is the largest number of edges in an $n$-vertex graph with no copy of $C_4$. This is known to be approximately $\frac{1}{2} n^{3/2}$.

The exact value of ex$(n, C_4)$ is only known for certain values of $n$, but for those cases the lower bound constructions come from projective planes. The spirit of the extremal examples is that each vertex has neighbourhood of order $\Theta(\sqrt{n})$ and these neighbourhoods cover the pairs of vertices in the graph, with (almost) every pair appearing in exactly one neighbourhood (if a pair were in two neighbourhoods, we would have a $C_4$).

What happens if we add an extra edge to such a construction? Suppose the new edge is $uv$. Then, for every vertex $w \in N(u)$, the edge $vw$, which was already covered by a neighbourhood, is covered by $N(u)$ and so forms a $C_4$. Similarly, for every $w \in N(v)$, the edge $uw$ produces a $C_4$. Overall, we produce $O(\sqrt{n})$ new copies of $C_4$, different to the expectation of $\Omega(n)$ expressed in the question. I suspect that $\Omega(\sqrt{n})$ is the correct answer in this case.