Supersaturation of $K_{s,t}$ in graphs with many edges

Question

I was trying to solve the following problem from Yufei Zhao's book "Graph Theory and Additive Combinatorics":

Exercise 1.4.12 (Density KST). Prove that for every pair of positive integers $s\leq t$, there are constants $C,c>0$ such that every $n$-vertex graph with $p\binom{n}{2}$ edges contains at least $cp^{st}n^{s+t}$ copies of $K_{s,t}$, provided that $p\geq Cn^{-1/s}$.

Before this problem he discusses Kovari-Sos-Turan theorem which says that

For any positive integers $s\leq t$ and for any $n\in \mathbb{N}$ we have $$ex(n,K_{s,t})\leq \frac{(t-1)^{1/s}}{2}n^{2-1/s}+\frac{s-1}{2}n.$$

Also he discusses the Supersaturation Theorem

For every $\varepsilon>0$ and graph $H$ there exist some $\delta>0$ and $n_0$ such that every graph on $n\geq n_0$ vertices with at least $(\pi(H)+\varepsilon)\binom{n}{2}$ edges contains at least $\delta n^{\nu(H)}$ copies of $H$ as a subgraph.

I am trying to combine the last two result to obtain the first one but do not know how to do it.

I'd be very grateful if someone can show the proof! Thanks a lot!

Answer 1

I think double-counting reasoning should work.

---

If suffices to show that it holds when $n$ is sufficiently large.

Let $G = (V, E)$ be a graph with $|V| = n$ and $|E| = p\binom{n}{2}$. Define $M = |\{(S \in \binom{V}{s}, v \in V): S \subseteq N(v)\}|$, where $N(v)$ is the set of neighbors of $v$ in $G$. We define $f(S) = |\{v \in V: S \subseteq N(v)\}|, \forall S \in \binom{V}{s}$. Then we have $$M = \sum_{v \in V} \binom{|N(v)|}{s} = \sum_{S \in \binom{V}{s}} f(S).$$ We use Jensen's to obtain $$\sum_{S \in \binom{V}{s}} f(S) = M = n * \frac{M}{n} = n * {\sum_{v \in V} \binom{|N(v)|}{s}} \geq n \binom{\sum_{v \in V}|N(v)| /n}{s} = n \binom{2p\binom{n}{2} /n}{s} = n \binom{p(n-1)}{s}.$$

We use Jensen's again to the number of copies of $K_{s,t}$: $$\sum_{S \in \binom{V}{s}} \binom{f(s)}{t} \geq \binom{n}{s} \binom{\sum_{S} f(S)/\binom{n}{s}}{t} \geq \binom{n}{s} \binom{n \binom{p(n-1)}{s}/\binom{n}{s}}{t} = \Omega(n^s) * \binom{n \frac{(pn-p)(pn-p-1)\ldots(pn-p-s+1)}{n(n-1)\ldots(n-s+1)}}{t} \geq \Omega(n^s) * \binom{((pn-p)n^{1/s}/n)^s}{t} = \Omega(n^s) * \binom{\Omega(p^s n)}{t} = \Omega(n^s) * \Omega(p^{st}n^t) = \Omega(p^{st} n^{s+t}).$$

More specifically, when $n \geq 100s$ and $p^s n \geq C^s \geq 100t / 0.99^s$, $$ \sum_{S \in \binom{V}{s}} \binom{f(s)}{t} \geq \frac{0.99^s}{s!} n^s \times \binom{(0.99p n^{1/s})^s}{t} \geq \frac{0.99^s}{s!} n^s \times \binom{0.99^s p^s n}{t} \geq \frac{0.99^s}{s!} n^s \times \frac{0.99^{s+t}}{t!} (0.99^s p^s n)^t \geq \frac{0.99^s}{s!} * \frac{0.99^{s+t}}{t!} * 0.99^{st} * p^{st}n^{s+t}.$$

---

The condition on $p$ ($p = \Omega(n^{-1/s})$) is used to guarantee that $\Omega(p^s n)$ is not $o(1)$ (when $n \rightarrow \infty$).

Answer 2

UPD: The proof was already given by @VezenBU. So in this answer I am just filling out some details.

Assume that $G=(V,E)$ is a graph such that $\nu(G)=n\geq s+t$ and $e(G)=p\binom{n}{2}$.

Let's consider the set of $s$-stars in graph $G$: \begin{equation*} M:=\left\{(A,v)\in \binom{V}{s}\times V: v\sim A\right\}. \end{equation*}

Easy to see that \begin{align*} |M|&=\sum \limits_{v\in V}\sum_{\substack{A\in \binom{V}{s} \\A\sim v}} 1=\sum_{v\in V}\left|\left\{A\in \binom{V}{S}:v\sim A\right\} \right|=\\ &=\sum \limits_{v\in V}\left|\left\{A:A\in \binom{N(v)}{s}\right\} \right|=\sum_{v\in V}\binom{\deg(v)}{s}. \end{align*} The function $f_s:\mathbb{R}\to \mathbb{R}$ defined by \begin{equation*} f_s(x) = \begin{cases} \dfrac{x(x-1)\dots(x-(s-1))}{s!}, & \text{if } x\geq s-1 \\ 0, & \text{otherwise } \end{cases} \end{equation*} is convex and for any $n\in \mathbb{Z}_{\geq 0}$ we have $f_s(n)=\binom{n}{s}$ (also $f_s$ is nondecreasing). Therefore by Jensen's inequality, \begin{align*} |M|&=\sum \limits_{v\in V}f_s(\deg(v))=n\sum \limits_{v\in V}\frac{1}{n}f_s(\deg(v))\\ &\geq nf_s\left( \sum \limits_{v\in V}\frac{\deg(v)}{n}\right)=nf_s\left(\frac{2e(G)}{n}\right)\\ &=nf_s\left(p(n-1)\right). \end{align*}

For each $A\in \binom{V}{s}$, consider $f(A):=\left|\left\{ v\in V: v\sim A\right\} \right|$. The definition of $M$ implies that $|M|=\sum \limits_{A\in \binom{V}{s}}f(A)$. The number of copies of $K_{s,t}$ in graph $G$ is \begin{align*} \sum \limits_{A\in \binom{V}{s}}\binom{f(A)}{t}&=\sum \limits_{A\in \binom{V}{s}}f_t(f(A))=\binom{n}{s}\sum \limits_{A\in \binom{V}{s}}\binom{n}{s}^{-1}f_t(f(A))\\ &\geq\binom{n}{s}f_t \left(\sum_{A\in \binom{V}{s}}\binom{n}{s}^{-1}f(A)\right)=\binom{n}{s}f_t\left(\frac{|M|}{\binom{n}{s}}\right). \end{align*}

If one takes $C=2s t^{1/s}$, i.e. $p\geq 2s t^{1/s} n^{-1/s}$, then $p\geq \dfrac{2s}{n^{1/s}}\geq \dfrac{2s}{n}>\dfrac{2s-2}{n}\geq \dfrac{s-1}{n-1}$, i.e. $p(n-1)> s-1$.

The following inequality holds: \begin{equation} \label{size of M} |M|\geq \frac{1}{(2s)^s s!}p^sn^{s+1}. \end{equation}

Since $p\geq 2s t^{1/s} n^{-1/s}$ which implies that $p(n-1)>s-1$ and hence \begin{align*} |M|&\geq nf_s(p(n-1))=n\cdot \dfrac{(pn-p)(pn-p-1)\cdot (pn-p-(s-1))}{s!}=\\ &=p^sn^{s+1}(s!)^{-1}\left(1-\frac{1}{n} \right)\left(1-\frac{1}{n} -\frac{1}{pn}\right)\dots \left(1-\frac{1}{n} -\frac{s-1}{pn}\right). \end{align*} Each of these brackets is positive since $p(n-1)>s-1$ because we assumed that $p\geq 2s t^{1/s} n^{-1/s}$. Therefore, \begin{equation*} |M|\geq p^sn^{s+1}(s!)^{-1}\left(1-\frac{1}{n} -\frac{s-1}{pn}\right)^s. \end{equation*} Since $n\geq 2$, then $1-\frac{1}{n}\geq \frac{1}{2}$. Also since $p\geq 2s t^{1/s} n^{-1/s}$, then $pn\geq 2s$ and hence $$1-\frac{1}{n} -\frac{s-1}{pn}\geq \frac{1}{2}-\frac{s-1}{2s}=\frac{1}{2s}.$$ Therefore, \begin{equation*} |M|\geq \frac{1}{(2s)^s s!}p^sn^{s+1}. \end{equation*}

So we know that the number of copies of $K_{s,t}$ in graph $G$ is at least $\binom{n}{s}f_t\left(|M|\binom{n}{s}^{-1}\right)$ and since $f_t$ is nondecreasing it follows that \begin{equation*} \#\ \text{of copies of} \ K_{s,t} \ \text{in graph} \ G\geq \binom{n}{s}f_t\left(\frac{p^sn^{s+1}}{(2s)^s s!}\binom{n}{s}^{-1}\right). \end{equation*} One can show that $\beta:=\dfrac{p^sn^{s+1}}{(2s)^s s!}\dbinom{n}{s}^{-1}\geq t$ since $p\geq \dfrac{2s t^{1/s}}{n^{1/s}}$ and hence \begin{equation*} f_t(\beta)=\frac{\beta\cdot (\beta-1)\cdot\dots \cdot(\beta-(t-1))}{t!} \geq \frac{\beta\cdot (\beta-1)\cdot\dots \cdot(\beta-(t-1))}{\beta!}. \end{equation*}

Therefore, \begin{align*} \#\ &\text{of copies of} \ K_{s,t} \ \text{in graph} \ G\geq \binom{n}{s}\frac{\beta\cdot (\beta-1)\cdot\dots \cdot(\beta-(t-1))}{t!}\geq \\ &\geq \frac{n(n-1)\cdot (n-(s-1))}{s!}\times \frac{\beta\cdot (\beta-1)\cdot\dots \cdot(\beta-(t-1))}{t!}\geq \\ & \geq \frac{n^s\beta^t}{s!t!} \left(1-\frac{s-1}{n}\right)^s\left(1-\frac{t-1}{\beta}\right)^t. \end{align*} Since $n\geq s+1$ and $\beta\geq t$ it follows that \begin{align*} \#\ &\text{of copies of} \ K_{s,t} \ \text{in graph} \ G\geq \frac{n^s\beta^t}{s!t!t^t}\left(\frac{2}{s+1}\right)^s. \end{align*} Notice that \begin{align*} \beta^t&=\frac{p^{st}n^{st+t}}{(2s)^{st}(s!)^t}\times \frac{(s!)^t}{\left[n(n-1)\dots (n-(s-1)) \right]^t}\geq \\ &\geq \frac{p^{st}n^{st+t}}{(2s)^{st}n^{st}}=\frac{p^{st}n^t}{(2s)^{st}}. \end{align*} Therefore, we obtain that \begin{equation*} \#\ \text{of copies of} \ K_{s,t} \ \text{in graph} \ G\geq\left( \frac{2^s}{s!t!t^t (2s)^{st}(s+1)^s}\right)p^{st}n^{s+t}. \end{equation*}

In summary, we were able to show that for every pair of positive integers $s\leq t$, there are constants $C:=2st^{1/s},\ c:=\dfrac{2^s}{s!t!t^t(2s)^{st}(s+1)^s}$ such that every $n$-vertex graph $(n\geq s+t)$ with $p\binom{n}{2}$ edges, where $p\geq Cn^{-1/s}$ contains at least $cp^{st}n^{s+t}$ copies of $K_{s,t}$.