Intereting Posts

Common Problems while showing Uniform Convergence of functions
If $H$ is a subgroup of $G$ of finite index $n$, then under what condition $g^n\in H$ for all $g\in G$
How to solve simultaneous modulus / diophantine equations
Intuition or figure for Reverse Triangle Inequality $||\mathbf{a}| − |\mathbf{b}|| ≤ |\mathbf{a} − \mathbf{b}|$ (Abbott p 11 q1.2.5)
A scientist catches 8 butterflies I
Who invented or used very first the double lined symbols $\mathbb{R},\mathbb{Q},\mathbb{N}$ etc
Diagonalisable or not?
Why this vector field $f$ belongs to $C^1({\bf R}^2\times {\bf R})$?
a probability question using percentages
Jacobson radical of a ring finitely generated over $\mathbb Z$
Existence of increasing sequence $\{x_n\}\subset S$ with $\lim_{n\to\infty}x_n=\sup S$
proof of the Krull-Akizuki theorem (Matsumura)
What is the basis for a proof?
Proof of fundamental lemma of calculus of variation.
What is the combinatorial interpretation of the product of binomial coefficients?

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?

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

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

- Words formed from NUMBER with N to the left of U
- what is the summation of such a finite sequence?
- Proof that $\binom{n}{\smash{0}}^2+\binom{n}{1}^2+\cdots+\binom{n}{n}^2=\binom{\smash{2}n}{n}$ using a counting argument
- Combinatorial Proof Of ${n \choose k}={n-1\choose {k-1}}+{n-1\choose k}$
- Counting matrices over $\mathbb{Z}/2\mathbb{Z}$ with conditions on rows and columns
- Show that $C(n,k) = C(n-1,k) + C(n-1,k-1)$
- The probability that each delegate sits next to at least one delegate from another country
- How many triangles
- If I randomly generate a string of length N from an alphabet {A, B, C}, what's the likelihood that exactly k characters will be the same?
- Proving identity $ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} $. How to interpret factorials and binomial coefficients with negative integers.

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.

- Constructing arithmetic progressions
- How come the number $N!$ can terminate in exactly $1,2,3,4,$ or $6$ zeroes but never $5$ zeroes?
- Is every convex-linear map an affine map?
- How do collinear points on a matrix affect its rank?
- Why is ${x^{\frac{1}{2}}}$ the same as $\sqrt x $?
- Trouble with Vakil's FOAG exercise 11.3.C
- Graph theory: minors vs topological minors
- Closed not exact form on $\mathbb{R}^n\setminus\{0\}$
- Explain Carmichael's Function To A Novice
- Origins of the modern definition of topology
- Probabilistic approach to prove a graph theory theorem
- extension of automorphism of field to algebraically closed field
- Maximizing area of a rectangle inscribed in a semicircle
- Brownian motion – Hölder continuity
- In the definition of a group, is stating the set together with the function on it redundant?