Maximize the number of edges in a bipartite graph with no 4-cycles

Consider an undirected bipartite graph which has $n$ nodes in each component such that there are no cycles of length equal to $4$, and such that each pair of nodes has at most $1$ edge between them. What is the maximum number of the edges in this graph?

An equivalent problem on the field of set theory: There are $n$ sets $A_1,A_2,...,A_n$ where $A_i$ is a subset of $\{1,2,...,n\}$ and where $|A_i \cap A_j| \leq 1$ for $i\neq j$. We want to maximize $$\sum_{i=1}^{n} |A_i|.$$.

• I'm pretty sure that this is a very difficult question to answer. Do you have any reason to suspect otherwise? Mar 25 '16 at 17:13
• @MikePierce, sincerely thank for your editing! I meet this problem when I study in quantum information. Mar 26 '16 at 13:51

1 Answer

This problem was studied by I. Reiman in this paper.

He obtains $E\leq \frac{1}{2}(n+n\sqrt{4n-3})$. The bound is sharp when $n=p^2+p+1$ and $p$ is a prime power (by taking the Levi graph of the projective plane of order $p$).

I found this in the section "Extremal Problems of Paul Erdos on Circuits in Graphs" of this book.

• That's really great! Thanks for you kind answer! Mar 26 '16 at 13:39
• Sure, no problem, although all I did was a little digging. Mar 26 '16 at 15:58