graph with $n$ vertices have having no subgraph isomorphic with $K_{2,t}$ can have at most $\frac{\sqrt{t-1}n^{3/2}+n}{2}$ edges

Question

How would you prove that for each $t\geq 2$ any graph with $n$ vertices have having no subgraph isomorphic with $K_{2,t}$ can have at most $\frac{\sqrt{t-1}n^{3/2}+n}{2}$ edges? Wondering if proof via induction would be best approach?

Answer 1

Let $t\ge 2$ and $G$ be any graph with $n$ vertices, $m$ edges and without a subgraph isomorphic to $K_{2,t}$. Thus any two distinct vertices of $G$ have at most $t-1$ common neighbors. Let $N$ be the number of copies a $3$-vertex path $P_3$ in $G$. Thus $N\le (t-1)\binom n2$. On the other hand, each vertex $v$ of $G$ is a midpoint of $\binom {\deg v}{2}$ such paths. Thus $$\sum_{v\in G} \binom {\deg v}{2}\le (t-1)\binom n2.$$ Since $\sum_{v\in G} \deg v=2m$, applying the inequality between an arithmetic mean and a quadratic mean, we obtain $$\frac{2m^2}n-m\le \sum_{v\in G} \binom {\deg v}{2},$$ which implies $$m\le\frac n4\left (1+\sqrt{4(n-1)(t-1)+1}\right).$$

When $t$ is fixed and $n$ tends to infinity, this bound is asymptotically tight, see [Fur].

References

[Fur] Zoltán Füredi, New Asymptotics for Bipartite Turán Numbers, Journal of Combinatorial Theory, Series A 75:1 (1996) 141–144.

Answer 2

Lets consider our graph $G(V,E)$ $\big(V(G)$ is the set of vertices of $G$ and $E(G)$ is the set of edges of $G\big)$. We will denote with $N(v)$ the set of vertices which are linked to $v$.

$G$ has no subgraphs isomorphic to $K_{2,t}$, so $\forall$ $v,u\in V(G)$ we have $|N(v)\cap N(u)|\leq t-1$. Thus:

$$\sum_{v,u\in V(G)}|N(v)\cap N(u)|\leq\binom{|V(G)|}{2}(t-1)$$.

But who is $$\sum_{v,u\in V(G)}|N(v)\cap N(u)|$$

Well, every vertex $v$ is counted for every pair of vertices, both linked to $v$, so $$\sum_{v,u\in V(G)}|N(v)\cap N(u)|=\sum_{v\in V(G)}\binom{\deg(v)}{2}$$ so we get $$\sum_{v\in V(G)}\binom{\deg(v)}{2}\leq\binom{|V(G)|}{2}(t-1)\text{ {a}}$$

One can use the fact that $$x_1^2+...+x_k^2\geq\frac{(x_1+...+x_k)^2}{k}$$ to prove that $$\sum_{v\in V(G)}\binom{\deg(v)}{2}=\frac{1}{2}\bigg(\sum_{v\in V(G)}\deg(v)^2-\sum_{v\in V(G)}\deg(v)\bigg)\geq\frac{1}{2}\Bigg(\frac{1}{|V(G)|}\bigg(\sum_{v\in V(G)}\deg(v)\bigg)^2-\sum_{v\in V(G)}\deg(v)\Bigg)$$

But we know that $$\sum_{v\in V(G)}\deg(v)=2|E(G)|\big(\text{ Remember, $|E(G)|$ is the number of edges in $G$}\big)$$ so substituting in the above equation we get $$\sum_{v\in V(G)}\binom{\deg(v)}{2}\geq\frac{1}{2}\Bigg(\frac{4|E(G)|^2}{|V(G)|}-2|E(G)|\Bigg)$$

Now lets substitute in $\{$a$\}$. We get the following:

$$\frac{1}{2}\Bigg(\frac{4|E(G)|^2}{|V(G)|}-2|E(G)|\Bigg)\leq\binom{|V(G)|}{2}(t-1)$$

But in your statement you said that $|V(G)|=n$; I will also denote $|E(G)|=e$, so we have

$$\frac{4e^2}{n}-2e\leq n(n-1)(t-1)$$

Using the classical quadratic equation bounds, we get $$e\leq\frac{n}{4}\big(1+\sqrt{1+4(n-1)(t-1)}\big)$$

Lets now prove $$\frac{n}{4}\big(1+\sqrt{1+4(n-1)(t-1)}\big)\leq\frac{n}{2}\big(\sqrt{(n-1)(t-1)}+1\big)$$

Let $(n-1)(t-1)=x$. Then the above equation is equivalent to $$\sqrt{4x+1}\leq2\sqrt{x}+1\Leftrightarrow 4x+1\leq4x+1+4\sqrt{x}\Leftrightarrow0\leq4\sqrt{x}$$ which is true.

So we win!