More than 19 blocks are required

The full argument

Proof. Suppose five 12-subsets of a 22-set $V$ cover every pair. They have 60 incidences, so some point $q$ has degree at most 2. A single block through $q$ meets only 11 of the 21 other points, so $q$ lies in exactly two blocks $A$ and $B$, and $A \cup B = V$. Then $|A \cap B| = 2$, and $X = A \setminus B$ and $Y = B \setminus A$ have 10 points each.

The 100 pairs $\{x,y\}$ with $x \in X$, $y \in Y$ lie in neither $A$ nor $B$, so the other three blocks cover them. A block with $a$ points of $X$ and $b$ points of $Y$ covers $ab$ such pairs, and $a + b \le 12$ gives $ab \le 36$. A block containing all of $X$ (or all of $Y$) covers at most $10 \cdot 2 = 20$, so if one did, the three blocks would cover at most $20 + 36 + 36 = 92 < 100$. So no block contains a whole side. Then each point of $X$ must lie in at least two of the three blocks: a single block through it would have to contain all of $Y$. The same holds for $Y$, so the three blocks need at least 40 incidences, but they have only 36. $\square$

Deriving and counting incidences now gives $C(23,13,3) \ge \lceil 23 \cdot 6/13 \rceil = 11$ and $C(24,14,4) \ge \lceil 24 \cdot 11/14 \rceil = 19$. These are the previous lower bounds.

Proof. The derived covering at a point is a $(23,13,3)$ covering, and at a pair it is a $(22,12,2)$ covering. $\square$

From here until Step 8, $\mathcal T$ is a $(24,14,4)$ covering of a 24-set $V$ by exactly 19 blocks. The goal is a contradiction.

The full argument

The 19 blocks have $19 \cdot 14 = 266 = 24 \cdot 11 + 2$ incidences, and every degree is at least 11. So the degrees are either

• (a) one point of degree 13 and all others 11, or
• (b) two points of degree 12 and all others 11.

Call the degree-11 points low and the others high. Let $L$ be the set of low points, so $|L| = 23$ or $22$.

For distinct points, let the excess be $w(x,y) = \lambda(x,y) - 6 \ge 0$. Each block through $x$ contains 13 other points, so $\sum_{y \ne x} \lambda(x,y) = 13\, d(x)$, and

$\sum_{y \ne x} w(x,y) = 13\, d(x) - 23 \cdot 6 = \begin{cases} 5 & d(x) = 11,\\ 18 & d(x) = 12,\\ 31 & d(x) = 13.\end{cases}$

The excess graph $\Gamma$ has vertex set $L$, with an edge of weight $w(x,y)$ between low points whenever $w(x,y) > 0$. Write $\delta(x) = \sum_{y \in L} w(x,y)$ for the weighted degree of $x$ in $\Gamma$; it is at most 5.

The full argument

Call a connected component $K$ of $\Gamma$ balanced if it is bipartite, with sides of equal size, and every vertex of $K$ has $\delta = 5$.

Proof. Let $M$ be the $L \times 19$ incidence matrix of low points against blocks and $G = MM^{\mathsf T}$ its Gram matrix. Its diagonal entries are 11 and its off-diagonal entries are $\lambda(x,y) = 6 + w(x,y)$, so

$G = 5I + 6J + W,$

where $W$ is the weighted adjacency matrix of $\Gamma$. For any real vector $z$ on $L$,

$z^{\mathsf T}(5I + W)z = \sum_{x} \bigl(5 - \delta(x)\bigr) z_x^2 + \sum_{\{x,y\}} w(x,y)\,(z_x + z_y)^2 .$

Both sums are nonnegative, so $5I + W$ is positive semidefinite, and $z$ is in its kernel exactly when $z_x = 0$ wherever $\delta(x) < 5$ and $z_y = -z_x$ along every edge. So kernel vectors live on bipartite components whose vertices all have $\delta = 5$, with opposite signs on the two sides. In such a component the total edge weight is $5|K^+| = 5|K^-|$, so the sides have equal size: these are exactly the balanced components. The kernel of $5I + W$ is spanned by their alternating vectors ($+1$ on one side, $-1$ on the other).

An alternating vector sums to zero, so $Jz = 0$ and it is also in the kernel of $G$. Conversely, $z^{\mathsf T} G z = z^{\mathsf T}(5I + W) z + 6\,(\mathbf 1^{\mathsf T} z)^2$, so $Gz = 0$ forces $z$ into the kernel of $5I + W$. Hence the nullity of $G$ is the number of balanced components. Since $G = MM^{\mathsf T}$ has rank at most 19, there are at least $|L| - 19$ of them. This is part 1.

For an alternating vector $z$, $\lVert M^{\mathsf T} z\rVert^2 = z^{\mathsf T} G z = 0$, so every block meets the two sides equally. This is part 2.

A vertex of a balanced component has $\delta(x) = 5$, which is its entire excess, so it has no excess to high points or to low points outside its component. It has none to its own side either, because the component is bipartite. This is part 3.

For part 4, let $U$ be the union of the balanced components. By part 3 no high point has excess to $U$, and each low point has total excess 5. In case (a), the degree-13 point has excess 31, all of it to low points outside $U$, at most 5 each; so at least 7 low points lie outside $U$, and $|U| \le 23 - 7 = 16$. In case (b), the two degree-12 points $h_1, h_2$ have excess 18 each and $w(h_1,h_2) \le 12 - 6 = 6$, so together they send at least $36 - 12 = 24$ excess to low points outside $U$. Each low point absorbs at most 5, so at least 5 low points lie outside $U$, and $|U| \le 17$. Since $|U|$ is even (part 5), $|U| \le 16$.

For part 5, the sides have equal size, so the size is even. In a size-2 component $\{x,x'\}$ the edge has weight 5, so $\lambda(x,x') = 11 = d(x) = d(x')$, and $x$ and $x'$ lie in the same blocks. $\square$

The full argument

Both remaining cases lead to an 11-block covering of 22 points. This lemma shows such a covering, if regular, has a unique shape: a doubled symmetric design, in which every point has a twin.

Proof. Every codegree is at least 2: the blocks through $x$ and $y$, with $x,y$ removed, are 10-sets covering the other 20 points. If $\lambda(x,y) = 2$, those two 10-sets partition the other 20 points, so the two blocks through $x$ and $y$ have union $Y$ and intersection $\{x,y\}$.

Codegree-2 pairs form a matching. Suppose $\lambda(u,v) = \lambda(u,w) = 2$ with $v \ne w$. The two blocks through $u,v$ and the two through $u,w$ share a block $A$ (they cannot share both, since two blocks with union $Y$ meet in only two points). Let $B$ and $C$ be the others. Then $A \supseteq \{u,v,w\}$, and with $Y' = Y \setminus A$ (10 points) and $Z = A \setminus \{u,v,w\}$ (9 points) we have $B = \{u,v\} \cup Y'$ and $C = \{u,w\} \cup Y'$. The other three blocks through $u$ avoid $v$ and $w$, and they must cover all 90 triples $\{u,y,z\}$ with $y \in Y'$, $z \in Z$. Each has 11 points besides $u$, so it covers at most $\lfloor 11^2/4 \rfloor = 30$ of the pairs $\{y,z\}$. All three must attain 30, splitting 5/6 between $Y'$ and $Z$. Then no block contains a whole side, so every point of $Y' \cup Z$ needs two of these blocks: 38 incidences, but only 33 are available.

Codegrees are 3 or 4 off the matching. Let $\{x,y\}$ be a codegree-2 pair. Besides the two common blocks, $x$ and $y$ each lie in 4 more blocks, all different, which uses 8 of the other 9 blocks; call the remaining one $N$. Any other point $z$ is in exactly one of the two common blocks and in 5 of the other 9, so

$\lambda(x,z) + \lambda(y,z) = 7 - [z \in N].$

Since $z$ is not matched to $x$ or $y$, both terms are at least 3, so each is 3 or 4.

No codegree-2 pairs at all. Let $M$ be the $22 \times 11$ incidence matrix, and let $W$ have off-diagonal entries $\lambda(x,y) - 3$ and zero diagonal, so $MM^{\mathsf T} = 3I + 3J + W$. Each row of $W$ sums to $66 - 63 = 3$. A matched point has row entries $-1$ (its partner) and otherwise 0 or 1, so its row has four entries 1 and squared sum 5. An unmatched point has nonnegative entries summing to 3, so its squared sum is at most 9.

Let $K = MM^{\mathsf T} - 3J = 3I + W$. Since $MM^{\mathsf T}\mathbf 1 = 72\,\mathbf 1$, the matrix $K$ has the eigenvector $\mathbf 1$ with eigenvalue 6 and agrees with $MM^{\mathsf T}$ on $\mathbf 1^\perp$. So $K$ is positive semidefinite with rank at most 11 and trace 66. By Cauchy–Schwarz on its eigenvalues, $\operatorname{tr}(K^2) \ge 66^2/11 = 396$. But $\operatorname{tr}(K^2) = 22 \cdot 9 + \sum_{x \ne y} W_{xy}^2$, so the squared row sums of $W$ total at least 198. With $f$ matching edges they total at most $198 - 8f$. So $f = 0$, and every row of $W$ has squared sum exactly 9: one entry 3 and the rest 0. The entry 3 marks a partner $\sigma(y)$ with $\lambda = 6$, a twin, and all other codegrees are 3.

Consequences. Collapsing twin pairs gives 11 blocks of 6 classes on 11 classes, with every two classes in 3 common blocks: a symmetric $2$-$(11,6,3)$ design. Its incidence matrix $N$ satisfies $N^{\mathsf T} N = 3I + 3J$, which is invertible, so it has rank 11, and in a symmetric design two blocks share $\lambda = 3$ classes, which is 6 points. If $z$ sums to zero on each block, then $\bar z(c) = z(y) + z(\sigma(y))$ is a vector on classes that sums to zero on each block of the quotient, so $\bar z = 0$ by invertibility. $\square$

Proof. Two 10-sets through $x$ reach at most 18 other points, so pair coverage needs 3, and 60 incidences make every degree exactly 3. Add two new points to every block of $\mathcal H$. The result, together with $\mathcal E$, is 11 blocks of size 12 on 22 points with every degree 6, and it covers every triple: triples inside $X$ by assumption, and triples through a new point because $\mathcal H$ covers pairs. Lemma 4 applies. The two new points are twins of each other, so $\sigma$ restricts to $X$, and parts 2–4 follow from Lemma 4 (blocks share 6 points, 2 of them new). If $\lambda_{\mathcal H}(x,y) = 3$ for a non-twin $y$, then $\lambda_{\mathcal E}(x,y) = 0$, and $x$ and $y$ would need disjoint triples of the five $\mathcal E$-blocks, which is impossible. That gives the bound in part 4 and part 5. $\square$

Part 5 matters below: two completions $\mathcal E$ and $\mathcal F$ of the same $\mathcal H$ give the same pairing.

The full argument

Proof. A balanced component of size 4 has sides $\{u,v\}$ and $\{s,t\}$; Lemma 3 gives the three conditions with $\lambda(u,v) = 6$ because $u,v$ are on the same side. Two balanced components of size 2, $\{u,s\}$ and $\{v,t\}$, are twin pairs, and again Lemma 3 gives the conditions. Otherwise every component has size 2 or at least 6, with at most one of size 2. By Lemma 3 there are at least 3 components on at most 16 points, so the sizes are $\{2,6,6\}$ or $\{2,6,8\}$. Case (a) would need four components, at least $2 + 6 + 6 + 6 = 20$ points. $\square$

The full argument

Proof. Suppose $u,v,s,t$ is one, and let $X$ be the other 20 points. Sort the 19 blocks:

The gadget-point column follows from the balance condition. On $X$, $\mathcal H$ covers every pair (the 4-set $\{u,v,x,y\}$ needs a block through $u$ and $v$), and $\mathcal H \cup \mathcal E$ and $\mathcal H \cup \mathcal F$ each cover every triple (look at $\{u,x,y,z\}$ and $\{v,x,y,z\}$). By Corollary 5 every $x \in X$ has $d_{\mathcal H}(x) = 3$, so $d_{\mathcal E}(x) = \lambda(u,x) - 3 = 3$, and likewise $d_{\mathcal F}(x) = 3$. So $(\mathcal H, \mathcal E)$ and $(\mathcal H, \mathcal F)$ are both completions, and by part 5 of Corollary 5 they share one pairing $\sigma$ of $X$ into ten twin classes.

The quotient graph. Let $C$ be the $6 \times 10$ incidence matrix of $\mathcal H$ against twin classes. Rows have 5 ones, columns have 3, and two rows share 2 classes, so $CC^{\mathsf T} = 3I + 2J$. The off-diagonal entries of $C^{\mathsf T}C$ are class codegrees in $\mathcal H$, which are 1 or 2 (at least 1 because $\mathcal H$ covers pairs). Let $A$ be the 0/1 matrix marking codegree 2, so $C^{\mathsf T}C = 2I + J + A$. Then

$(C^{\mathsf T}C)^2 = C^{\mathsf T}(3I + 2J)C = 3\,C^{\mathsf T}C + 18J,$

using $\mathbf 1^{\mathsf T}C = 3\,\mathbf 1^{\mathsf T}$. Row sums of $C^{\mathsf T}C$ are $3 \cdot 5 = 15$, so $A\mathbf 1 = 3\,\mathbf 1$. Expanding the square then gives

$A^2 + A - 2I = J.$

So the graph with adjacency matrix $A$ is 3-regular on 10 vertices, adjacent vertices have no common neighbour, and non-adjacent vertices have exactly one. (This is the Petersen graph, though the argument never needs that.)

Removing two vertices leaves it connected. Let $D$ be a set of at most 2 vertices, and suppose the graph minus $D$ is disconnected. Fix a remaining vertex $z$. A remaining vertex $x$ outside $z$‘s component is not adjacent to $z$, so they have exactly one common neighbour, and it lies in $D$ (otherwise it would join the two components). A vertex of $D$ adjacent to $z$ has only two other neighbours, so at most $2|D|$ remaining vertices lie outside $z$‘s component. So every component contains all but at most $2|D|$ of the $10 - |D|$ remaining vertices. If $|D| \le 1$, two components would each have at least 7 vertices, which is too many. If $|D| = 2$, there are exactly two components of 4 vertices each, and the count is tight only if every remaining vertex is adjacent to both vertices of $D$. Then the vertices of $D$ have degree 8, not 3.

Colours. Every $x \in X$ has degree $9 + d_{\mathcal G}(x) \ge 11$, so $d_{\mathcal G}(x) \ge 2$. The three $\mathcal G$-blocks have 42 incidences on 20 points, so exactly two points $a,b$ have $d_{\mathcal G} = 3$ and the other 18 have $d_{\mathcal G} = 2$. Each of those 18 misses exactly one $\mathcal G$-block; call that block its colour. A $\mathcal G$-block misses exactly 6 points of $X$, so each colour has at most 6 points.

Edges force equal colours. If classes $i,j$ are adjacent, then for any $x$ in $i$ and $y$ in $j$, $\lambda_{\mathcal H}(x,y) = 2$ and $\lambda_{\mathcal E}(x,y) = \lambda_{\mathcal F}(x,y) = 3 - 2 = 1$ by Corollary 5. Since $\lambda(x,y) \ge 6$, the two points share at least 2 $\mathcal G$-blocks. If both have $d_{\mathcal G} = 2$, they are in the same two blocks and have the same colour.

Contradiction. Delete the at most two classes containing $a$ or $b$. The remaining classes (at least 8) induce a connected graph, every remaining class has a neighbour, and all their points (at least 16) have $d_{\mathcal G} = 2$. Colours agree along every edge, for both points of each class, so all of these points share one colour. But a colour has at most 6 points. $\square$

The full argument

Proof. Let $h_1,h_2$ be the high points and $\{q,q'\}$ the size-2 component, a twin pair. Let $\mathcal P$ be the 11 blocks through $q$ (and $q'$), let $\mathcal R$ be the other 8, and let $Y$ be the other 22 points.

The providers are rigid. On $Y$, $\mathcal P$ consists of 11 blocks of size 12 covering every triple (look at $\{q,x,y,z\}$). By Lemma 3, $\lambda(q,y) = 6$ for every $y \in Y$, so every point of $Y$ has degree 6 in $\mathcal P$. Lemma 4 gives a twin involution $\sigma$ of $Y$ with $\lambda_{\mathcal P} = 3$ off the twin pairs. In $\mathcal R$, low points of $Y$ have degree $11 - 6 = 5$ and $h_1,h_2$ have degree $12 - 6 = 6$.

Components split twin pairs. Let $K$ be one of the two larger components, with alternating vector $z$. By Lemma 3, $z$ sums to zero on every block, in particular on every block of $\mathcal P$, so Lemma 4 gives $z(\sigma(y)) = -z(y)$. Hence $\sigma$ maps each side of $K$ onto the other.

Selected points. Let $S$ be one side of the size-6 component together with one side of the other large component: 6 or 7 low points, no two of them twins. For distinct $x,y \in S$, $\lambda(x,y) = 6$ by Lemma 3 and $\lambda_{\mathcal P}(x,y) = 3$, so $\lambda_{\mathcal R}(x,y) = 3$. For $x \in S$, likewise $\lambda(x,h_1) = 6$ and $\lambda_{\mathcal P}(x,h_1) = 3$ (the twin of $x$ is a low point on the other side), so $\lambda_{\mathcal R}(x,h_1) = 3$.

Counting in $\mathcal R$. For $x \in S$ let $O(x)$ be the 3 blocks of $\mathcal R$ missing $x$, and let $O(h_1)$ be the 2 missing $h_1$. Inclusion–exclusion in the 8 blocks gives

$|O(x) \cap O(y)| = 8 - (5 + 5 - 3) = 1, \qquad |O(x) \cap O(h_1)| = 8 - (5 + 6 - 3) = 0.$