Cauchy in Combinatorial Estimates

In one sentence

Counting problems often produce an expression like this: the number of “pairs” formed from some quantities $d_{1}, \dots, d_{n}$ is under control, that is, $\sum C_{d_{i}}^{2} \leq K$ . But what we want to estimate is the total $D = \sum d_{i}$ . The missing step in between is exactly the Cauchy inequality:

\sum d_{i}^{2} \geq \frac{( \sum d _{i} ) ^{2}}{n} = \frac{D ^{2}}{n} .

So $\frac{D ^{2}}{n} - D \leq \sum d_{i}^{2} - \sum d_{i} = 2 \sum C_{d_{i}}^{2} \leq 2 K$ , and solving this quadratic inequality in $D$ gives an upper bound. Counting in two ways bounds the sum of squares; Cauchy turns that into a bound on the total. Equality needs all the $d_{i}$ to be equal, which also tells you what the best construction looks like.

How many cells of a 7 × 7 board can be filled without a rectangle?

Step 1 / 5

A rectangle = two rows sharing two columns
A rectangle with all four corners filled means that two rows both have cells in the same two columns. So “no rectangle” is the same as: every pair of columns is used by at most one row.

$no rectangle ⟺ each column pair is used by at most one row$
Count in two ways: column pairs inside rows
Cauchy: from the sum of squares to the total
Solve for the bound
It really exists: the Fano plane

Predict first

On a $5 \times 5$ board with no rectangle, how many cells can be filled at most? (First work out the bound with the method above, then go back to the top of the page and build it.)

cells

Choose an answer first; then you can see the result.

Stop 1 · Graph theory: graphs with no 4-cycle

A simple graph on $n$ vertices contains no cycle of length $4$ . At most how many edges can it have?

Replace “rows of the board” by “vertices”. Vertex $v$ has degree $d_{v}$ ; pairing up its neighbors gives $C_{d_{v}}^{2}$ “paths with middle vertex $v$ ”. Having no 4-cycle is the same as any two vertices have at most one common neighbor, so

v \sum C_{d_{v}}^{2} \leq C_{n}^{2}, v \sum d_{v} = 2 e .

Cauchy: $\sum d_{v}^{2} \geq \frac{4 e ^{2}}{n}$ , so $\frac{4 e ^{2}}{n} - 2 e \leq n (n - 1)$ , which solves to

e \leq \frac{n}{4} (1 + 4 n - 3) .

For $n = 5$ the right side is about $6.4$ , so $e \leq 6$ ; two triangles sharing one vertex (a “bow tie”) have exactly $6$ edges and no 4-cycle.

$9$ people form several $4$ -person committees, and any two committees have at most one member in common. At most how many committees can there be?

This time let the people be the “rows”: person $p$ sits on $d_{p}$ committees. Pairing up the committees that person is on gives pairs of committees, and no pair of committees appears twice (otherwise those two committees would share two members), so

p = 1 \sum 9 C_{d_{p}}^{2} \leq C_{m}^{2}, p \sum d_{p} = 4 m .

Cauchy: $\sum d_{p}^{2} \geq \frac{16 m ^{2}}{9}$ . Substituting gives $\frac{16 m ^{2}}{9} - 4 m \leq m (m - 1)$ , i.e. $7 m \leq 27$ , so $m \leq 3$ . A construction: ${1, 2, 3, 4}$ , ${4, 5, 6, 7}$ , ${7, 8, 9, 1}$ .

All three have exactly the same skeleton: bound the number of pairs (counting in two ways) → Cauchy turns the sum of squares into the total → solve a quadratic inequality → check with a construction.

Practice

Exercise 1Basic

Fill some cells of a $4 \times 4$ board so that no rectangle has all four corners filled. At most how many cells can you fill?

Exercise 2Basic

$6$ people form several $3$ -person groups, and any two groups have at most one member in common. At most how many groups can there be?

Exercise 3Advanced

A simple graph on $5$ vertices has no cycle of length $4$ . At most how many edges can it have?

Exercise 4Challenge

On a $6 \times 6$ board, no rectangle may have all four corners filled. At most how many cells can be filled?

In one sentence

How many cells of a 7 × 7 board can be filled without a rectangle?

Stop 1 · Graph theory: graphs with no 4-cycle

Practice

Mistake Museum · Exhibits from this stop

Treating “the average row” as “every row”

Cauchy in Combinatorial Estimates

In one sentence

Stop 1 · Graph theory: graphs with no 4-cycle

Stop 2 · Families of sets: any two share at most one element

Practice

Mistake Museum · Exhibits from this stop