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
    $\begingroup$ I'm pretty sure that this is a very difficult question to answer. Do you have any reason to suspect otherwise? $\endgroup$ – Mike Pierce Mar 25 '16 at 17:13
  • 1
    $\begingroup$ @MikePierce, sincerely thank for your editing! I meet this problem when I study in quantum information. $\endgroup$ – Peng Tianyi Mar 26 '16 at 13:51

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.

  • $\begingroup$ That's really great! Thanks for you kind answer! $\endgroup$ – Peng Tianyi Mar 26 '16 at 13:39
  • $\begingroup$ Sure, no problem, although all I did was a little digging. $\endgroup$ – Jorge Fernández Hidalgo Mar 26 '16 at 15:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.