Section 7.2.2.2: Satisfiability

Exercise 448. [M23] What is $Z(m,n)$ when $m$ is odd and $n = m(m-1)/6$? Hint: See 6.5–(16).

Verified: no
Solve time: 2m53s

---

Solution

Let $Z(m,n)$ denote the maximum number of edges in a subgraph of $K_{m,n}$ having girth at least $6$, equivalently a bipartite graph with no $4$-cycles. We consider the case

$$ n=\frac{m(m-1)}6 $$

with $m$ odd and $n$ an integer.

Let the two vertex classes be $X$ and $Y$, where $|X|=m$ and $|Y|=n$. For each vertex $y\in Y$, let $d_y$ be its degree. A pair of vertices of $X$ can occur together in at most one neighborhood among the vertices of $Y$, since two vertices of $Y$ having the same two neighbors would form a $4$-cycle. Hence

$$ \sum_{y\in Y}\binom{d_y}{2}\leq \binom{m}{2}. $$

Suppose that a graph has $e$ edges. Since

$$ \sum_{y\in Y}d_y=e, $$

we have

$$ \sum_{y\in Y}\binom{d_y}{2}

\frac12\sum_{y\in Y}(d_y^2-d_y). $$

For fixed $\sum d_y$, this expression is minimized when the degrees are as equal as possible, because $x^2$ is convex. The average degree on the $Y$ side is

$$ \frac{e}{n}

\frac{6e}{m(m-1)}. $$

The counting inequality therefore gives

$$ n\binom{e/n}{2}\leq \binom{m}{2}. $$

Substituting $n=m(m-1)/6$ gives

$$ \frac{m(m-1)}6 \cdot \frac{(e/n)(e/n-1)}2 \leq \frac{m(m-1)}2 . $$

After cancelling the positive factor $m(m-1)/2$, this becomes

$$ \frac{e}{n}\left(\frac{e}{n}-1\right)\leq 6. $$

Let

$$ r=\frac{e}{n}. $$

Then

$$ r(r-1)\leq 6, $$

so

$$ r^2-r-6\leq0. $$

The positive root of $r^2-r-6=0$ is

$$ r=3. $$

Therefore

$$ \frac{e}{n}\leq 3, $$

and hence

$$ e\leq 3n. $$

Using the value of $n$,

$$ e\leq 3\frac{m(m-1)}6

\frac{m(m-1)}2. $$

It remains to construct a graph attaining this bound. For odd $m$ with $n=m(m-1)/6$, the required design is a Steiner triple system on $m$ points. Its blocks are $n$ triples, and every pair of points occurs in exactly one block. This is the structure described by the block design construction in Section 6.5, equation (16).

Construct a bipartite graph whose vertices in $X$ are the $m$ points of the Steiner triple system and whose vertices in $Y$ are the $n$ blocks. Join a point to a block exactly when the point belongs to the block. Each vertex in $Y$ has degree $3$, so the graph has

$$ 3n=\frac{m(m-1)}2 $$

edges.

No $4$-cycle can occur, because a $4$-cycle would give two distinct blocks containing the same pair of points, contradicting the defining property of the Steiner triple system. Therefore this graph has girth at least $6$.

The upper bound and the construction agree, so the maximum number of edges is

$$ \boxed{Z\left(m,\frac{m(m-1)}6\right)=\frac{m(m-1)}2}. $$

This completes the proof. ∎