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

819 Views Asked by At

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|.$$.

1

There are 1 best solutions below

2
On

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.