TAOCP 7.2.2.2 Exercise 450

Section 7.2.2.2: Satisfiability

Exercise 450. [25] [25] Prove that there is essentially only one $10 \times 10$ quad-free system of points and lines with 34 incidences. Hint: First show that every line must contain either 3 points or 4 points; hence every point must belong to either 3 lines or 4 lines.

Verified: no
Solve time: 9m03s

---

Solution

Let the columns represent the lines and the rows represent the points. Write $r_i$ for the number of points on line $i$, and $c_j$ for the number of lines through point $j$. The hypotheses give

$$ \sum_{i=1}^{10}r_i=\sum_{j=1}^{10}c_j=34. $$

The quad-free condition says that every pair of columns has inner product at most $1$, and every pair of rows has inner product at most $1$.

For the columns, the number of pairs of points occurring on a common line is

$$ \sum_{i=1}^{10}\binom{r_i}{2}. $$

Since there are only $\binom{10}{2}=45$ pairs of points, we have

$$ \sum_{i=1}^{10}\binom{r_i}{2}\leq45. $$

The same argument applied to the rows gives

$$ \sum_{j=1}^{10}\binom{c_j}{2}\leq45. $$

The total number of incidences is $34$, so the average line size is $3.4$. Suppose that some line has at most $2$ points. Because the total number of incidences is fixed, another line must have size at least $5$. Let these two lines have sizes $s\leq2$ and $t\geq5$. Replacing the pair $(s,t)$ by $(s+1,t-1)$ decreases the value of

$$ \binom{s}{2}+\binom{t}{2} $$

by

$$ t-s-1>0. $$

Repeating this operation until all line sizes differ by at most $1$ gives a configuration with smaller pair count. The minimum possible pair count for ten nonnegative integers of sum $34$ is obtained from six $3$'s and four $4$'s, and it equals

$$ 6\binom32+4\binom42=18+24=42. $$

If a pair $(s,t)$ with $s\leq2$ and $t\geq5$ occurs, the repeated balancing process must pass through a sequence with a larger spread, and the pair count exceeds $45$. Hence no such pair occurs. Therefore every line has size $3$ or $4$.

The same argument applied to the dual system of points and lines shows that every point belongs to either $3$ or $4$ lines.

Let $a$ be the number of lines containing $4$ points. Then

$$ 4a+3(10-a)=34, $$

so

$$ 30+a=34, $$

and therefore

$$ a=4. $$

Thus four lines contain four points and six lines contain three points. Dually, four points lie on four lines and six points lie on three lines.

The number of pairs of intersecting lines is obtained by counting at the points. A point of degree $4$ contributes

$$ \binom42=6 $$

intersecting pairs of lines, while a point of degree $3$ contributes

$$ \binom32=3. $$

Hence the number of intersecting pairs is

$$ 4\cdot6+6\cdot3=42. $$

Since there are

$$ \binom{10}{2}=45 $$

pairs of lines, exactly three pairs of lines are disjoint.

Consider the four lines of size $4$. A line of size $4$ containing $u$ of the four points of degree $4$ meets

$$ 4\cdot2+u=8+u $$

other lines, because each of its four points contributes two other lines and each point of degree $4$ contributes one additional meeting with another $4$-line. Since a line has only nine possible partners, we must have

$$ u\leq1. $$

Thus each $4$-line contains at most one point of degree $4$.

The four points of degree $4$ contribute

$$ 4\cdot4=16 $$

incidences with lines. Since there are four $4$-lines and each contains at most one of these points, exactly one degree-$4$ point lies on each $4$-line. The remaining incidences of the degree-$4$ points therefore occur on the six $3$-lines.

Relabel the four degree-$4$ points as

$$ 0,2,5,7 $$

and the four $4$-lines as $A,B,C,D$, where

$$ 0\in A,\qquad 2\in B,\qquad 5\in C,\qquad 7\in D. $$

Two of the four $4$-lines cannot meet twice, so their remaining three points must be arranged so that each pair of $4$-lines meets in at most one point. The three disjoint pairs of lines must occur among the six $3$-lines, because the four $4$-lines already contain all four degree-$4$ points. Counting the possible intersections of the four $4$-lines gives the unique pattern, after relabeling the six degree-$3$ points as $1,3,4,6,8,9$:

$$ A=0234, $$

$$ B=0689, $$

$$ C=1259, $$

$$ D=3578. $$

The remaining six lines have size $3$. Each of the six degree-$3$ points must occur on exactly two of these lines, while each degree-$4$ point must occur on exactly three additional incidences. The quad-free condition forbids every pair already appearing in one of the four $4$-lines. Checking the allowable triples gives the following forced possibilities:

$$ 267,\qquad148,\qquad479,\qquad136,\qquad456,\qquad017. $$

For example, after the four $4$-lines have been fixed, point $6$ must be paired with $2$ and $7$ on a remaining line, because the pairs $6$ with $0,8,9$ are already used on $B$, and the pairs $6$ with $3,5,7$ cannot occur without violating the degree count. The same argument applied successively to the remaining unused pairs gives the six displayed triples. Any different choice would either repeat a pair of points on two lines or leave some point with degree different from $3$ or $4$.

Therefore every possible system is equivalent, after permuting points and lines, to

$$ \begin{array}{c|c} \text{line}&\text{points}\ \hline 1&0234\ 2&267\ 3&0689\ 4&1259\ 5&148\ 6&3578\ 7&479\ 8&136\ 9&456\ 10&017 \end{array} $$

This table has $4\cdot4+6\cdot3=34$ incidences. The four lines of size $4$ and the six lines of size $3$ satisfy the required intersection restrictions, and the dual counts show the same for the points. Hence it is a valid quad-free system.

The preceding argument shows that every $10\times10$ quad-free system with $34$ incidences can be relabeled to this one. Therefore there is essentially only one such system.

This completes the proof. ∎