Steiner triple sistema de con $\lambda \le 1$

Question

¿Cuál es el número máximo de 3-tamaño de los subconjuntos de a $[n]$ que puede existir tal que no hay dos subconjuntos contener más de un elemento común?

Al$n \equiv 1,3 \mod 6$, esto es equivalente a una Steiner sistema de triple. Cada número aparecerá $\displaystyle\frac{n-1}{2}$ veces y no se $\displaystyle\frac{n(n-1)}{6}$ subconjuntos. Pero ¿qué pasa cuando $n \not\equiv 1,3 \mod 6$?

Por ejemplo, los subconjuntos $\{1,2,3\},\{3,4,5\},\{1,4,6\},\{2,5,6\}$ $[6]$ satisfacer el requisito.

Yo conozco a un par de los más pequeños valores:

• $n = 3 \implies 1:\{1,2,3\}$ cada número aparece $1$ veces
• $n = 4 \implies 1:\{1,2,3\}$ cada número aparece $0 \le t \le 1$ veces
• $n = 5 \implies 2:\{1,2,3\},\{3,4,5\}$ cada número aparece $1 \le t \le 2$ veces
• $n = 6 \implies 4: \{1,2,3\},\{3,4,5\},\{1,4,6\},\{2,5,6\}$ cada número aparece $2$ veces
• $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\}$ cada número aparece $3$ veces
• $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$: cada número aparece $4$ veces

Hay una solución de forma cerrada para el número de subconjuntos de al $n \not\equiv 1,3 \mod 6$?

Answer 1

Este problema es equivalente a encontrar el $K_3$-embalaje número de $K_n$ como se indica en este documento.

$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$

Tenemos
$\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{casos}\\ P(K_3, K_n) y= \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{casos}\\ y= \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{casos} \end{align*}$

Podemos simplificar $n \equiv 1 \mod 2, \displaystyle\frac{n(n-1)}{2} \not\equiv 0 \mod 3$:
Caso 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*}$
Caso 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*}$
No hay soluciones a $n^2 - n - 1 \equiv 0 \mod 3$, lo $\displaystyle\frac{n(n-1)}{2} \not\equiv 0 \mod 3 \iff n \equiv 2 \mod 3$

Ahora tenemos $n \equiv 1 \mod 2$$n \equiv 2 \mod 3$. La aplicación de la CRT nos da $n \equiv 5 \mod 6$. Esto reduce la ecuación a
$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{casos}$

Además,
$\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{casos} \end{align*}$

Nota para $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*}$

Si tomamos la intersección de los dos, conseguimos $n \equiv 1, 3 \mod 6 \implies P(K_3, K_n) = \displaystyle\frac{n(n-1)}{6}$ cual es el resultado obtenido de Steiner triple sistemas.

$\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*}$

Ahora tenemos un piso de menos de fórmula: $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{casos}$