Intereting Posts

Which area is larger, the blue area, or the white area?
When does $V/\operatorname{ker}(\phi)\simeq\phi(V)$ imply $V\simeq\operatorname{ker}(\phi)\oplus\phi(V)$?
Why $S^1\times S^{2m-1}$ carries a complex structure.
Does $\lim_{n\rightarrow\infty}\sin\left(\pi\sqrt{n^{3}+1}\right)$ exist?
An example of a function uniformly continuous on $\mathbb{R}$ but not Lipschitz continuous
Finding the Laurent series of $f(z)=\frac{1}{(z-1)^2}+\frac{1}{z-2}$?
Compact space and Hausdorff space
If monotone decreasing and $\int_0^\infty f(x)dx <\infty$ then $\lim_{x\to\infty} xf(x)=0.$
Do all Groups have a representation?
How to show if $ \lambda$ is an eigenvalue of $AB^{-1}$, then $ \lambda$ is an eigenvalue of $ B^{-1}A$?
Multiplying Taylor series and composition
What is the difference between all types of Markov Chains?
Generating the special linear group of 2 by 2 matrices over the integers.
Nice expression for minimum of three variables?
How to find a function mapping matrix indices?

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?

- Bipartite graph. average degree. Euler circuit.
- Bipartite graph with larger average on one side
- counting full bipartite matchings
- Maximum no.of edges in a bipartite graph
- Finding the spanning subgraphs of a complete bipartite graph

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

- Number of spanning trees in a ladder graph
- Combinations problem involving a standard pack of $52$ playing cards and a $4$ sided die: Part 1
- Kind of basic combinatorical problems and (exponential) generating functions
- Frobenius coin problem
- How many words of length $n$ can we make from $0, 1, 2$ if $2$'s cannot be consecutive?
- Strong equidistribution of points on the n-sphere
- Proof of subfactorial formula $!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$
- Number of binary and constant-weight strings of length m which do not contain k consecutive zeros
- Dealing a 5 card hand with exactly 1 pair
- Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 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.”

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.

Check out these notes by Jacob Fox.

- Continuity and the Axiom of Choice
- If $d$ is a metric, then $d/(1+d)$ is also a metric
- Can I get a PhD in Stochastic Analysis given this limited background?
- How to find the Galois group of a polynomial?
- Harmonic number divided by n
- Finding Rational numbers
- Calculating $\int_{\mathcal{S}}x_1^r \, \mathrm dx_1\ldots \, \mathrm dx_n$
- Calculate integrals involving gamma function
- How exactly can't $\delta$ depend on $x$ in the definition of uniform continuity?
- Fundamental group of the special orthogonal group SO(n)
- How many subsets of size $n+1$ can we have so no two of them have intersection of size $n$
- How do you remember theorems?
- Open and closed balls in $C$
- How many ways are there to express a number as the product of groups of three of its factors?
- Find $\int_{ – \infty }^{ + \infty } {\frac{1} {1 + {x^4}}} \;{\mathrm{d}}x$