TAOCP 6.5 Exercise 11

Section 6.5: Retrieval on Secondary Keys

Exercise 11. [M25] [M25] The text describes the use of Steiner triple systems in connection with inclusive queries; in order to extend this to all basic queries it is natural to define the following concept. A complemented triple system of order v is an arrangement of 2vu objects {11,...,2v,%1,...,Zv} into triples such that every pair of objects occurs together in exactly one triple, except that complementary pairs {x;,Z;} never occur together. For example,

{v1, 02,03}, {1,£2,%3}, {%1,02,F3}, {%1,%2, x3}

is a complemented triple system of order three. Prove that complemented triple systems of order v exist for all v > 0 not of the form 3k + 2.

Verified: yes
Solve time: 1m08s

---

Solution

A complemented triple system of order $v$ can be reformulated as a decomposition of the edge set of a graph on $2v$ vertices into triples (triangles) with the following structure. Let the vertex set be ${x_1,\dots,x_v,\bar{x}_1,\dots,\bar{x}_v}$. The forbidden pairs are exactly ${x_i,\bar{x}_i}$ for $1\le i\le v$. Every other unordered pair of distinct vertices must occur in exactly one triple.

This is equivalent to a decomposition of the graph $K_{2v}$ with the perfect matching ${{x_i,\bar{x}_i}:1\le i\le v}$ removed, into triangles.

Let $G_v$ denote this graph.

Necessity

Each triangle contributes degree $2$ to each of its three vertices. Hence every vertex of $G_v$ must have even degree.

Each vertex is adjacent in $K_{2v}$ to $2v-1$ vertices, and exactly one incident edge is removed by deleting its complementary pair. Hence every vertex of $G_v$ has degree $2v-2$, which is even for all $v$.

The total number of edges of $G_v$ is

$$ \binom{2v}{2} - v = \frac{2v(2v-1)}{2} - v = v(2v-1) - v = 2v(v-1). $$

A decomposition into triangles requires this number to be divisible by $3$, since each triangle covers $3$ edges. Hence

$$ 3 \mid 2v(v-1). $$

Since $3\nmid 2$, this is equivalent to $3\mid v(v-1)$, which holds exactly when $v \equiv 0 \pmod 3$ or $v \equiv 1 \pmod 3$.

If $v \equiv 2 \pmod 3$, then $v(v-1)\equiv 2\cdot 1 \equiv 2 \pmod 3$, so no decomposition exists.

This completes the necessity.

Sufficiency

Assume $v \not\equiv 2 \pmod 3$. Then $2v+1 \equiv 1 \pmod 6$ or $2v+1 \equiv 3 \pmod 6$. By the classical existence theorem for Steiner triple systems, there exists a Steiner triple system on $2v+1$ points; denote its point set by

$$ V = {0,1,\dots,2v}. $$

Fix a distinguished point $\infty = 0$. In a Steiner triple system, every pair of distinct points occurs in exactly one triple. Each point other than $\infty$ occurs with $\infty$ in exactly one triple, so there are exactly $v$ triples of the form

$$ {\infty,a_i,b_i}, \quad 1\le i\le v, $$

and these pairs ${a_i,b_i}$ form a perfect matching on $V\setminus{\infty}$.

Relabel the remaining $2v$ points as

$$ {x_1,\dots,x_v,\bar{x}_1,\dots,\bar{x}_v} $$

so that each matched pair ${a_i,b_i}$ becomes ${x_i,\bar{x}_i}$.

Remove all triples containing $\infty$. The remaining triples are all triples of the Steiner system that lie entirely in $V\setminus{\infty}$. Each pair ${x_i,\bar{x}_i}$ is absent from these triples, since it appears only in the removed triple containing $\infty$. Every other pair of vertices appears exactly once in the original Steiner system and is not removed, so it appears exactly once in the remaining family.

Thus the remaining triples form a decomposition of all admissible pairs of $G_v$ into triples, with no triple containing any forbidden pair ${x_i,\bar{x}_i}$. This is exactly a complemented triple system of order $v$.

Conclusion

A complemented triple system of order $v$ exists precisely when a Steiner triple system on $2v+1$ points exists, which occurs exactly when $2v+1 \equiv 1 \pmod 6$ or $2v+1 \equiv 3 \pmod 6$, equivalently when $v \not\equiv 2 \pmod 3$.

This completes the proof. ∎