What's the maximum number of 3-sized subsets of $[n]$ that can exist such that no two subsets contain more than one common element?
When $n \equiv 1,3 \mod 6$ then this is equivalent to a Steiner triple system. Each number will appear $\displaystyle\frac{n-1}{2}$ times and there are $\displaystyle\frac{n(n-1)}{6}$ subsets. But what about when $n \not\equiv 1,3 \mod 6$?
For instance, the subsets $\{1,2,3\},\{3,4,5\},\{1,4,6\},\{2,5,6\}$ of $[6]$ satisfy the requirement.
I know a couple of the smaller values:
- $n = 3 \implies 1:\{1,2,3\}$ each number appears $1$ times
- $n = 4 \implies 1:\{1,2,3\}$ each number appears $0 \le t \le 1$ times
- $n = 5 \implies 2:\{1,2,3\},\{3,4,5\}$ each number appears $1 \le t \le 2$ times
- $n = 6 \implies 4: \{1,2,3\},\{3,4,5\},\{1,4,6\},\{2,5,6\}$ each number appears $2$ times
- $n = 7 \implies 7:\{5, 6, 7\},\{1, 4, 6\},\{2, 3, 6\},\{2, 4, 5\},\{1, 3, 5\},\{3, 4, 7\},\{1, 2, 7\}$ each number appears $3$ times
- $n = 8 \implies 8: \{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,8\},\{6,7,1\},\{7,8,2\},\{8,1,3\}$
- $n = 9 \implies 12$: each number appears $4$ times
Is there a closed form solution for the number of subsets when $n \not\equiv 1,3 \mod 6$?
This problem is equivalent to finding the $K_3$-packing number of $K_n$ as outlined in this paper.
$H = K_3$
$d = \text{gcd}(H) = 2$
$h = |V(H)| = \displaystyle\binom{3}{2} = 3$
$\displaystyle\frac{2h}{d} = \frac{2*3}{2} = 3$
We have
$\begin{align*} P(H, K_n) &= \begin{cases} \left\lfloor \frac{dn}{2h} \left\lfloor \frac{n-1}{d} \right\rfloor \right\rfloor - 1, & n \equiv 1 \mod d, \frac{n(n-1)}{d} \equiv b \mod \frac{2h}{d}:1\le b \le d\\ \left\lfloor \frac{dn}{2h} \left\lfloor \frac{n-1}{d} \right\rfloor \right\rfloor, & \text{o/w} \end{cases}\\ P(K_3, K_n) &= \begin{cases} \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor - 1, & n \equiv 1 \mod 2, \frac{n(n-1)}{2} \equiv b \mod 3:1\le b \le 2\\ \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor, & \text{o/w} \end{cases}\\ &= \begin{cases} \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor - 1, & n \equiv 1 \mod 2, \frac{n(n-1)}{2} \not\equiv 0 \mod 3\\ \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor, & \text{o/w} \end{cases} \end{align*}$
We can simplify $n \equiv 1 \mod 2, \displaystyle\frac{n(n-1)}{2} \not\equiv 0 \mod 3$:
Case 1:
$\begin{align*} \frac{n(n-1)}{2} &\equiv 1 \mod 3\\ n(n-1) &\equiv 2 \mod 3\\ n^2 - n - 2 &\equiv 0 \mod 3\\ n &\equiv 2 \mod 3\\ \end{align*}$
Case 2:
$\begin{align*} \frac{n(n-1)}{2} &\equiv 2 \mod 3\\ n(n-1) &\equiv 1 \mod 3\\ n^2 - n - 1 &\equiv 0 \mod 3 \end{align*}$
There are no solutions to $n^2 - n - 1 \equiv 0 \mod 3$, so $\displaystyle\frac{n(n-1)}{2} \not\equiv 0 \mod 3 \iff n \equiv 2 \mod 3$
Now we have $n \equiv 1 \mod 2$ and $n \equiv 2 \mod 3$. Applying the CRT gives us $n \equiv 5 \mod 6$. This reduces the equation to
$P(K_3, K_n) = \begin{cases} \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor - 1, & n\equiv 5 \mod 6\\ \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor, & \text{o/w} \end{cases}$
Additionally,
$\begin{align*} n \equiv 5 \mod 6 &\implies 2|(n-1)\\ &\implies \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor - 1 = \left\lfloor \frac{n}{3} * \frac{n-1}{2} \right\rfloor - 1 = \left\lfloor \frac{n(n-1)}{6} \right\rfloor - 1\\ n \equiv 5 \mod 6 &\implies n(n-1) \equiv 2 \mod 6\\ &\implies \left\lfloor \frac{n(n-1)}{6} \right\rfloor - 1 = \frac{n(n-1)-2}{6} - 1\\ &\implies P(K_3, K_n) = \begin{cases} \frac{n(n-1) - 8}{6}, & n\equiv 5 \mod 6\\ \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor, & \text{o/w} \end{cases} \end{align*}$
Note for $n \not\equiv 5 \mod 6$:
$\begin{align*} n\equiv 1 \mod 2 &\implies \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor = \left\lfloor \frac{n}{3} * \frac{n-1}{2} \right\rfloor = \left\lfloor \frac{n(n-1)}{6} \right\rfloor\\ n(n-1) \equiv 0 \mod 6 &\implies n \equiv 0,1,3,4 \mod 6 \implies \left\lfloor \frac{n(n-1)}{6} \right\rfloor = \frac{n(n-1)}{6}\\ \end{align*}$
If we take the intersection of both of those, we get $n \equiv 1, 3 \mod 6 \implies P(K_3, K_n) = \displaystyle\frac{n(n-1)}{6}$ which is the result obtained from Steiner triple systems.
$\begin{align*} n \equiv 0 \mod 6 \implies \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor &= \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor\\ &= \frac{n}{3} * \frac{n-2}{2}\\ &= \frac{n(n-2)}{6} \end{align*}$
$\begin{align*} n \equiv 2 \mod 6 \implies \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor &= \left\lfloor \frac{n}{3} * \frac{n-2}{2} \right\rfloor\\ &= \left\lfloor \frac{n-2}{3} * \frac{n}{2} \right\rfloor\\ &= \frac{n(n-2)}{6} \end{align*}$
$\begin{align*} n \equiv 4 \mod 6 \implies \left\lfloor \frac{n}{3} \left\lfloor \frac{n-1}{2} \right\rfloor \right\rfloor &= \left\lfloor \frac{n}{3} * \frac{n-2}{2} \right\rfloor\\ &= \left\lfloor \frac{n(n-2)}{6} \right\rfloor\\ &= \frac{n(n-2) - 2}{6} \end{align*}$
Now we have a floor-less formula: $P(K_3, K_n) = \begin{cases} \ \frac{n(n-2)}{6}, &n \equiv 0,2 \mod 6\\ \frac{n(n-1)}{6}, &n \equiv 1,3 \mod 6\\ \frac{n(n-2) - 2}{6}, &n \equiv 4 \mod 6\\ \frac{n(n-1) - 8}{6}, &n \equiv 5 \mod 6 \end{cases}$