6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.