A generalization of Kirkman's schoolgirl problem

Question

A friend of mine asked me this question. "I have $3n$ elements, and I want to know which is the maximum number of triplets $(a,b,c)$ so that no two triplets have more than one element in common".

The first thing which came into my mind was the Kirkman's schoolgirl problem: with 15 elements there are 35 different triplets (which may be arranged in 7 groups of five triplets each, but this is not important for the problem my friend asked me). A bit of research led me to Steiner triples, and I understand that there is always a maximal solution. But is there an algorithm to find one?

Answer 1

I see no reason to assume that the number of elements is divisible by $3$; so I'll work with $m$ elements, where $m$ is your $3n$. This answer has gone through a lot of edits; I now have a complete answer for all $m$.

For $m \equiv 1$ or $3 \bmod 6$, the answer is $(m^2-m)/6$. For $m \equiv 5 \bmod 6$, the answer is $(m^2-m-8)/6$. For $m$ even, the answer is $\lfloor (m^2-2m)/6 \rfloor$, which is $(m^2-2m)/6$ for $m \equiv 0$ or $2 \bmod 6$ and $(m^2-2m-2)/6$ for $m \equiv 4 \bmod 6$.

Upper bounds We have the upper bound $(m^2-m)/6$. The upper bound is because any unordered pair $\{ a,b \}$ can only occur in at most one triple. If $k$ is the number of triples, then every triple contains $3$ pairs, so $3k \leq \binom{m}{2}$ which simplifies to $k \leq (m^2-m)/6$.

For $m \equiv 5 \mod 6$, I can do better. First of all, $(m^2-m)/6$ isn't an integer, so we can improve to $\lfloor (m^2-m)/6 \rfloor = (m^2-m-2)/6$. But, in fact, we can do one better; the true bound is $(m^2-m-8)/6$. Proof: For the sake of contradiction, suppose we could achieve $(m^2-m-2)/6$. Since each triple contains $3$ pairs, there would be $3 (m^2-m-2)/6 = \binom{m}{2} -1$ pairs contained among our triples. In other words, there would be precisely one pair $(x,y)$ not in a triple. There are $m-2$ points other than $x$. By hypothesis, each of these points IS in a triple with $x$, and these triples overlap only at $x$. So these triples look like $(x, z_1, z_2)$, $(x, z_3, z_4)$ etcetera, and we conclude that $m-2$ is even. This contradicts our hypothesis that $m \equiv 5 \bmod 6$. So $(m^2-m-2)/6$ is not achievable and the true bound is $(m^2-m-8)/6$.

Now suppose $m$ is even. For every index $i$ in $\{1,2,\ldots,m\}$, there can only be $m-1$ triples containing $i$. Thus, for every $i$, there is some $f(i)$ such that $(i, f(i))$ is not contained in any triple. That means at least $m/2$ pairs are in no triple. So $3k \leq \binom{m}{2} - (m/2)$ or $k \leq (m^2-2m)/6$.

Lower bounds

1. If $m \equiv 1$ or $3 \bmod 6$, then $(m^2-m)/6$ is achievable. The configurations which achieve this are called Steiner triple systems; see here or here for constructions.

2. If $m \equiv 0$, $2 \bmod 6$ then there is a Steiner system of size $m+1$. Deleting all the $m/2$ triples from this that contain $m+1$ achieves $(m^2-2m)/6$ triples, again hitting the optimal bound.

3. If $m \equiv 5 \bmod 6$, then we can partition $\{1,2,\ldots, m\}$ into $(m-5)(m+4)/6$ triples and one quintuple so that every pair is in exactly one of these sets. See the last slides of these notes. Calling the quintuple $\{a,b,c,d,e\}$, delete it and create the triples $\{ a,b,c \}$ and $\{ c,d,e \}$. This achieves $(m-5)(m+4)/6 + 2 = (m^2-m-8)/6$.

4. If $m \equiv 4 \mod 6$, then take the above system of size $((m+1)^2 - (m+1)-8)/6$ and delete a point which lies in $m/2-1$ triples. This achieves $(m^2-2m-2)/6 = \lfloor(m^2-2m)/6 \rfloor$.