Combinatoria extremal · Definición

Sistema triple de Steiner

combinatoria enumerativacombinatoria extremal

Los sistemas triples de Steiner son el caso mas simple de los diseños de bloques de Steiner, con bloques de tamano 3. Aparecen en codificacion, en el diseno de experimentos y en la teoria de cuadrados latinos.

Definición

Un sistema triple de Steiner \(\mathrm{STS}(v)\) es un diseño de bloques en el que \(v\) puntos se agrupan en tramos de 3 puntos, de modo que cada par de puntos distintos aparece en exactamente un tramo.

\[b=\frac{v(v-1)}{6},\quad r=\frac{v-1}{2}\]

Si \(\mathrm{STS}(v)\) existe, cada punto \(x\) pertenece a exactamente \(r=\frac{v-1}{2}\) bloques, porque los demas \(v-1\) puntos deben formar pares con \(x\) en tramos de 2 puntos cada uno. Por eso \(v\) debe ser impar, y el numero de bloques es \(b=\frac{v(v-1)}{6}\), que debe ser entero. La condicion \(v\equiv 1,3 \pmod 6\) es necesaria y, por el teorema de Kirkman-Netto, tambien suficiente.

Para \(v=7\) el plano de Fano es un \(\mathrm{STS}(7)\) con \(b=7\) bloques y \(r=3\). Los bloques \(\{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,1\},\{6,7,2\},\{7,1,3\}\) cubren cada uno de los 21 pares exactamente una vez, comprobable contando pares por bloque: \(7\cdot 3=21=\binom{7}{2}\).

Un error tipico es asumir que cualquier \(v\) impar sirve, por ejemplo \(v=5\): aqui \(b=\frac{5\cdot 4}{6}\) no es entero, asi que no existe un sistema triple. Tambien es erroneo confundir la condicion de pares exactamente una vez con la de pares al menos una vez, que describe un recubrimiento y no un diseno.

Para pensar

¿Por qué exigir que cada par aparezca exactamente una vez, y no al menos una, fija el número de bloques?

Porque los b bloques cubren los pares sin repetir, así que \(3b=\binom{v}{2}\) determina b; con al menos una vez los pares pueden repetirse y el conteo solo daría una desigualdad.

Ejercicios 10

  1. ¿Cuántos pares de puntos distintos contiene un conjunto de \(v\) puntos?
  2. ¿Cuántos pares cubre un bloque de tamaño 3 en un sistema triple de Steiner?
  3. Si \(v=7\), ¿cuántos bloques tiene un \(\mathrm{STS}(7)\)?
  4. ¿Cuántos bloques contiene cada punto en un \(\mathrm{STS}(9)\)?
  5. ¿Qué valor de \(v\) es necesario para que exista un sistema triple de Steiner?
  6. Un \(\mathrm{STS}(v)\) tiene \(b=35\) bloques. ¿Cuál es el valor de \(v\)?
  7. En un \(\mathrm{STS}(v)\), ¿cuántos bloques pasan por un punto fijo si \(v=13\)?
  8. ¿Cuántos bloques tiene un \(\mathrm{STS}(13)\)?
  9. Un \(\mathrm{STS}(v)\) cumple \(r=6\) y \(b=26\). ¿Es \(v=13\) el único valor posible, y qué pasa con \(v=12\)? Justifica con las cotas de \(r\) y \(b\).
  10. Sea \(v=19\). ¿Cuántos bloques tiene un \(\mathrm{STS}(19)\), cuántos bloques pasan por cada punto, y cumple \(v\equiv 1,3 \pmod 6\)?

Referencias

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.