5
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Not a formula exactly but the comment after Theorem 2.2 here ma3.upc.edu/users/balbuena/PAPERS/ExtBipartite.pdf might be of interest to you. In particular, looks like $A_{6,6}=16$. $\endgroup$ – Casteels Jan 12 '14 at 1:08
  • 2
    $\begingroup$ The simple observation that $A_{m,n+1}\le\lfloor\frac{n+1}nA_{m,n}\rfloor$ gets you from $A_{5,5}\le12$ to $A_{6,6}\le16$. $\endgroup$ – bof Jan 12 '14 at 4:24
  • $\begingroup$ @bof, simple but lovely. $\endgroup$ – Casteels Jan 12 '14 at 17:59
  • 1
    $\begingroup$ Related, but without restriction to bipartite graphs: Maximum edges in a square free graph. $\endgroup$ – hardmath Jan 13 '14 at 23:34
  • $\begingroup$ Linked $\endgroup$ – Alex Ravsky Nov 7 '16 at 9:26
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It seems a subscript is missing +1 in your "recursive upper bound" on $A_{m,n}$ above. Compare to Comment on the Question. $\endgroup$ – hardmath Jan 13 '14 at 23:26
  • $\begingroup$ @hardmath Thanks! $\endgroup$ – bof Jan 13 '14 at 23:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Good point, thanks! I have updated my answer to include your observation. $\endgroup$ – bof Jan 14 '14 at 1:56
1
$\begingroup$

Check out these notes by Jacob Fox.

$\endgroup$

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.