Maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle

Question

Let $A_{n,m}$ be the maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle. I have calculated some values:

$A_{2,2}=3$, $A_{3,3}=6$, $A_{4,4}=9$, $A_{4,5}=10$, $A_{5,5}=12$.

I am trying to find formula for $A_{n,m}$. Does anyone know it or a hint how to find?

Especially I need the value of $A_{6,6}$. I only know that $A_{6,6}\ge16$.

Answer 1

I will give simple proofs of the evaluations $A_{4,6}=12,\ A_{5,6}=14,\ A_{6,6}=16,\ A_{6,7}=18,\ $ and $A_{7,7}=21$.

1. Since the ratio $\dfrac{A_{m,n}}{mn}$ is a nonincreasing function of $m$ and $n$, we have the recursive upper bound $$A_{m,n+1}\le\lfloor\frac{n+1}nA_{m,n}\rfloor.$$

2. It's easy to see that $A_{1,n}=n$ and $A_{2,n}=n+1$ for all $n$.

3. $$A_{3,4}\le\lfloor\frac32A_{2,4}\rfloor=\lfloor\frac{15}2\rfloor=7$$ $$A_{3,5}\le\lfloor\frac54A_{3,4}\rfloor\le\frac{35}4\rfloor=8$$ $$A_{4,5}\le\lfloor\frac43A_{3,5}\rfloor\le\lfloor\frac{32}3\rfloor=10$$ $$A_{4,6}\le\lfloor\frac65A_{4,5}\rfloor\le\lfloor\frac{60}5\rfloor=12$$ $$A_{{5,5}}\le\lfloor\frac54A_{4,5}\rfloor\le\lfloor\frac{50}4\rfloor=12$$ $$A_{5,6}\le\lfloor\frac65A_{5,5}\rfloor\le\lfloor\frac{72}5\rfloor=14$$ $$A_{6,6}\le\lfloor\frac65A_{5,6}\rfloor\le\lfloor\frac{84}5\rfloor=16$$ $$A_{6,7}\le\lfloor\frac76A_{6,6}\rfloor\le\lfloor\frac{112}6\rfloor=18$$ $$A_{7,7}\le\lfloor\frac76A_{6,7}\rfloor\le\lfloor\frac{126}6\rfloor=21$$

4. Let $G$ be the bipartite graph with vertex sets $U,V$ where $|U|=6,|V|=7$, and:

• The elements of $U$ are the six faces of a cube;
• $V$ has four elements corresponding to four pairwise nonadjacent vertices of the cube, each of those four elements being joined to the three faces incident with the corresponding vertex of the cube;
• $V$ has three elements coresponding to pairs of opposite faces of the cube, and joined to those two faces.

The graph $G$ witnesses the inequality $A_{6,7}\ge18$; moreover, by deleting one, two, or three of the degree $2$ vertices of $G$, we get witnesses to $A_{6,6}\ge16,\ A_{5,6}=A_{6,5}\ge14$, and $A_{4,6}=A_{6,4}\ge12$. Combined with the previously obtained upper bounds, this verifies the exact evaluations $A_{4,6}=12,\ A_{5,6}=14,\ A_{6,6}=16,$ and $A_{6,7}=18$.

5. The point-line incidence graph of a finite geometry is a $C_4$-free bipartite graph. In this way we get the lower bounds $$A_{n^2,\ n^2+n}\ge n^3+n^2$$and $$A_{n^2+n+1,\ n^2+n+1}\ge(n^2+n+1)(n+1)$$ whenever a projective plane of order $n$ exists, e.g., whenever $n$ is a prime power.

Setting $n=2$ (the Fano plane) we get $A_{4,6}\ge12$ (again) and $A_{7,7}\ge21$ which, combined with the previously obtained upper bound, establishes that $A_{7,7}=21$.

Update. Thanks to @David for pointing out that "the graph G in 4 is in fact the incidence graph of the Fano plane with one line (or point) removed."

Answer 2

A slight simplification of bof's answer: sections 4 and 5 could be combined, since the graph $G$ in 4 is in fact the incidence graph of the Fano plane with one line (or point) removed.

Answer 3

Check out these notes by Jacob Fox.