Maximum number of edges in bipartite $C_4$-free graph

Question

Show that a $C_4$-free bipartite graph between two vertex parts of sizes of $a$ and $b$ has at most $ab^{1/2}+b$ edges.

Let's introduce some basic notations: $\binom{X}{2}$ means the family of 2-subsets of $X$ and $v\sim A$ means that $v$ is adjacent to any vertex in $A$.

Proof: Suppose that $G=G[X,Y]$ is a bipartite graph with vertex parts $X$ and $Y$ such that $|X|=a,\ |Y|=b$ and with $m$ edges.

1. Assume that $a\geq b$ and consider $S=\{(A,v)\in \binom{X}{2}\times Y: v\sim A\}.$ One can obtain the following upper bound for the size of $S$: $$|S|=\sum \limits_{A\in \binom{X}{2}} \sum_{\substack{v\in Y\\v\sim A}} 1 =\sum \limits_{A\in \binom{X}{2}} |\{v\in Y: v\sim A\}|\leq \sum \limits_{A\in \binom{X}{2}}1=\binom{a}{2}.$$ In the same way one can obtain lower bound for the size of $S$: $$|S|=\sum \limits_{v\in Y} \sum_{\substack{A\in \binom{X}2{} \\v\sim A}} 1=\sum \limits_{v\in Y} |\{A\in \binom{X}{2}: v\sim A\}|\geq \sum \limits_{v\in Y}|\{A\subset N(v): |A|=2 \}|=\sum \limits_{v\in Y}\binom{\deg (v)}{2}.$$ Combining bounds, we obtain: $$\sum \limits_{v\in Y} \binom{\deg(v)}{2}\leq \binom{a}{2} \quad \Leftrightarrow \quad \sum \limits_{v\in Y}\deg(v)^2-\sum\limits_{v\in Y}\deg(v)\leq a^2-a.$$ Since $\sum \limits_{v\in Y}\deg(v)=m$ and $\sum \limits_{v\in Y}\deg(v)^2\geq \frac{m^2}{b}$ by Cauchy-Schwarz inequality, we obtain: $$\frac{m^2}{b}-m\leq a^2-a \Leftrightarrow m^2-bm+(ab-a^2b)\leq 0 \Rightarrow$$ $$m\leq \frac{b+\sqrt{b^2-4ab+4ba^2}}{2}\leq \frac{b+\sqrt{b^2+4ba^2}}{2}\leq \frac{b}{2}+\frac{\sqrt{5}}{2}a\sqrt{b}.$$

2. If $b\geq a$, then performing analogous reasoning one can show that $m\leq \frac{a}{2}+\frac{\sqrt{5}}{2}b\sqrt{a}.$

Combining both cases we obtain that $e(G)\leq \min \left(\frac{b}{2}+\frac{\sqrt{5}}{2}a\sqrt{b}, \frac{a}{2}+\frac{\sqrt{5}}{2}b\sqrt{a} \right).$

And you see that what I've obtained is very close to the answer of the problem but I do not see what should I change in order in my reasoning.

If someone can show it, then it would be great!

Answer 1

Technically, OP has correctly solved the problem. I basically repeated what the OP has done.

---

We can use similar reasoning used to show a bound of the number of edges for general $C_4$-free graphs using double counting "cherries" ($K_{1, 2}$).

Proof. We count cherries with the middle point on the right ($b$ nodes). We have the number of cherries = \begin{align} \sum_{v \in Y} \binom{d_v}{2} \geq b \binom{\frac{1}{b} \sum_{v \in Y} d_v}{2} = b \binom{m/b}{2} = m(m-b)/2b, \end{align} where we use Jenson's for the first inequality.

On the other hand, we have the number $\leq \binom{a}{2}$. Otherwise, by Pigeonhole we will have a $K_{2,2} = C_4$.

Therefore, we have $m(m-b)/2b \leq a(a-1)/2$, which is $$m^2 - bm -ab(a-1) \leq 0.$$ The axis of symmetry is $m = b/2$. Since $ab^{1/2} +b > b/2$, when $m > ab^{1/2} + b$, $$m^2 - bm -ab(a-1) > (ab^{1/2} + b)^2 - b * (ab^{1/2} + b) - ab(a-1) > 0,$$ completing the proof.