18.2: Diseños en T

En un BIBD, cada par aparece juntos\(λ\) veces. En la notación del problema de Woolhouse,\(q = 2\). ¿Qué pasa con los valores más grandes de\(q\)? (Todavía solo consideraremos el caso donde cada\(q\) -set aparece un número igual de veces\(λ\), por lo que el diseño debe ser equilibrado, pero vamos a incluir la situación más general que\(λ ≥ 1\).)

Definición:\(t\)-\((v, k, λ)\) Design

A \(t\)-\((v, k, λ)\) diseño es un diseño en\(v\) puntos con bloques de cardinalidad\(k\), tal que cada\(t\) subconjunto de\(V\) aparece exactamente en\(λ\) bloques.

Hasta el momento, todo lo que hemos mirado han sido\(2\) -diseños.

Teorema\(\PageIndex{1}\)

En un\(t\) -\((v, k, λ)\) diseño,

\[\binom{k-1}{t-1} \text{ is a divisor of } λ\binom{v-1}{t-1} \text{ for every } 0 ≤ i ≤ t − 1. \]

Prueba

Primero consideramos el caso especial donde\(i = 0\). Observe que en cada uno de los\(b\) bloques, hay\(\binom{k}{t}\) subconjuntos de cardinalidad\(t\) que aparecen en ese bloque. Entonces, en todo el diseño, aparecen\(b\binom{k}{t}\) subconjuntos de cardinalidad t.

Existen\(\binom{v}{t}\) subconjuntos de cardinalidad\(t\) desde los\(v\) puntos de\(V\), y cada uno aparece en\(λ\) bloques, por lo que en todo el diseño\(t\) aparecen\(λ\binom{v}{t}\) subconjuntos de cardinalidad.

Por lo tanto,\(b\binom{k}{t} = λ\binom{v}{t}\).

De igual manera, si fijamos algún conjunto de\(i\) variedades, hay\(\binom{v-i}{t-i}\) subconjuntos de cardinalidad\(t\) que incluyen estas\(i\) variedades. Cada uno de esos subconjuntos aparece en\(λ\) bloques. Sin embargo, para cada uno de los bloques que contiene estos\(i\) elementos (el número de estos será nuestro cociente), podemos completar nuestro\(i\) -set a un conjunto de cardinalidad\(t\) que se encuentra dentro de este bloque, de\(\binom{k-i}{t-i}\) maneras. Por lo tanto, hemos contado cualquiera de esos\(\binom{k-i}{t-i}\) tiempos de bloqueo en el recuento anterior. Entonces\(\binom{k-i}{t-i}\) debe ser un divisor de\(λ \binom{v−i}{t−i}\), como se reclama.

Ejemplo\(\PageIndex{1}\)

Demuestre que no hay\(5 − (16, 7, 1)\) diseño.

Solución

Comprobamos las condiciones necesarias dadas en el Teorema 18.2.1. Usando la condición cuando\(i = 0\), vemos eso\(b \binom{7}{5} = 1 \binom{16}{5}\), así\(21b = 4368\). Por lo tanto\(b = 208\). Esta condición está satisfecha.

Cuando\(i = 1\) tenemos\(\binom{k-i}{t-i} = \binom{6}{4} = 15\), y\(λ \binom{v-i}{t-i} = \binom{15}{4} = 15·14·13·12 4·3·2 = 15 · 7 · 13\), que es divisible por\(15\). Esta condición está satisfecha.

Cuando\(i = 2\) tenemos\(\binom{k-i}{t-i} = \binom{5}{3} = 10\), y\(λ \binom{v-i}{t-i} = \binom{14}{3} = 14·13·12 3·2 = 14 · 13 · 2\), que no es divisible por\(10\) ya que no es un múltiplo de\(5\). Esta condición falla. Por lo tanto, no hay\(5 −(16, 7, 1)\) diseño.

diseño. Supongamos que tenemos un\(3-(10, 4, 1)\) diseño. Por Teorema 18.1.1, it

\(b \binom{4}{3} = 1 \binom{10}{3} \)

así\(4b = \dfrac{10 · 9 · 8}{6} = 120\). Por lo tanto,\(b = 30\). También, ya que\(bk = vr\), tenemos\(30 · 4 = 10r\), así\(r = 12\)

Ejemplo\(\PageIndex{2}\)

Aquí hay un\(3-(10, 4, 1)\) diseño.

\[\begin{equation} \begin{split} &\{1, 5, 6, 10\},\;\; &\{1, 2, 8, 9\}, \;\;&\{2, 3, 6, 7\},\;\; &\{3, 4, 9, 10\},\;\; &\{4, 5, 7, 8\}, \;\;&\{1, 3, 4, 7\}, \\ &\{2, 4, 5, 10\},\;\; &\{1, 3, 5, 8\},\;\; &\{1, 2, 4, 6\},\;\; &\{2, 3, 5, 9\},\;\; &\{4, 6, 8, 9\}, \;\;&\{1, 7, 9, 10\}, \\ &\{3, 6, 8, 9\},\;\; &\{5, 6, 7, 9\}, \;\;&\{2, 7, 8, 10\},\;\; &\{1, 2, 3, 10\},\;\; &\{1, 2, 5, 7\}, \;\;&\{1, 4, 5, 9\}, \\ &\{1, 3, 6, 9\}, \;\;&\{1, 6, 7, 8\},\;\; &\{1, 4, 8, 10\},\;\; &\{2, 3, 4, 8\},\;\; &\{2, 4, 7, 9\},\;\; &\{2, 5, 6, 8\}, \\ &\{2, 6, 9, 10\},\;\; &\{3, 4, 5, 6\},\;\; &\{3, 5, 7, 10\}, \;\;&\{3, 7, 8, 9\},\;\; &\{4, 6, 7, 10\}, &\;\;\{5, 8, 9, 10\} \end{split} \end{equation}\]

Aviso: Para\(t ≥ 3\), un\(t\) -diseño también es un\((t − 1)\) -diseño. Si cada\(t\) -set aparece exactamente en\(λ\) bloques, entonces cualquier\((t − 1)\) -set debe aparecer exactamente

\(\dfrac{λ(v − t + 1)}{(k − t + 1)}\)

bloques. Esto se debe a que si arreglamos un\((t − 1)\) -set, se puede convertir en un\(t\) -set agregando cualquiera de los\(v − t + 1\) otros elementos de\(V\). Cada uno de estos\(t\) -conjuntos aparece en\(λ\) de los bloques. Sin embargo, algunos de estos bloques son iguales; de hecho, hemos contado cada bloque que contiene este\((t−1)\) -set una vez por cada otro elemento del bloque (ya que cada otro elemento del bloque forma un\(t\) -set cuando se junta con el\((t − 1)\) -set). Entonces cada bloque que contiene este\((t − 1)\) -set ha sido contado\(k −(t−1)\) veces. El resultado sigue. (De la fórmula anterior podemos ver que\(k −t+ 1\) es un divisor de\(λ(v − t + 1)\); esta es exactamente la condición que da el Teorema 18.2.1 cuando tomamos\(i = t − 1.\))

Por lo tanto, desde

\(\dfrac{1(10 − 3 + 1)}{(4 − 3 + 1)} = 4\),

el\(3 − (10, 4, 1)\) diseño que dimos arriba, también es un\(2 − (10, 4, 4)\) diseño. En más generalidad, un\(t − (v, k, λ)\) diseño con también\(t > 2\) es un\((t − 1) − \left( \dfrac{v, k, λ(v − t + 1)}{(k − t + 1)} \right)\) diseño.

El nombre de Steiner también se usa en este contexto más general, y sin la restricción en el bloque

Definición: Steiner System

Un sistema Steiner es un\(t\) -diseño con\(λ = 1\).

El\(3-(10, 4, 1)\) diseño anterior es un sistema Steiner.

Nuestra capacidad para construir sistemas Steiner cuando\(k > 3\), o cuando\(t > 2\), excepto en casos triviales, es casi inexistencia. De hecho, no hay sistemas Steiner construidos conocidos con\(t > 5\), con la excepción de que tomar cada posible\(t\) -subconjunto de un\(v\) -set es siempre un\(t − (v, t, 1)\) diseño (trivial).

A pesar de ello, en\(2014\) un teorema notable fue probado por Peter Keevash, siguiendo líneas similares al Teorema de Wilson, pero aplicándose a este contexto más general.

Las condiciones necesarias dadas en el Teorema 18.1.1 no son suficientes para garantizar la existencia de un BIBD con un conjunto particular de parámetros. No obstante, el Teorema de Keevash nos dice que si fijamos\(k\) y\(t\), sólo hay finitamente muchos valores para\(v\) que satisfagan las condiciones necesarias pero para los que no existe ningún\(t − (v, k, 1)\) diseño. Su prueba era probabilística, por lo que no produce construcciones para ningún diseño. Aquí hay una declaración formal del teorema de Keevash.

Teorema\(\PageIndex{2}\): Keevash's Theorem

Dado\(k\) y\(t\), hay un entero\(v(k, t)\) tal que por cada\(v > v(k, t)\) que satisface las condiciones:

• \(v ∈ \mathbb{Z}\); y
• para cada\(0 ≤ i ≤ t − 1\)

\[\binom{k-1}{t-1} \text{ is a divisor of } λ\binom{v-1}{t-1} \]

existe un\(t − (v, k, 1)\) diseño.

Prueba

No vamos a dar una prueba de este teorema.

Ejercicio\(\PageIndex{1}\)

1) Sustituir\(t = 2\) en las ecuaciones del Teorema 18.1.1 no se parece inmediatamente a ninguna de las ecuaciones del Teorema 17.1.1. Usa las ecuaciones del Teorema 17.1.1 para deducir que

\(\binom{k}{2} \text{ is a divisor of } λ\binom{v}{2} \)

2) Si\(v = 15\) y\(λ = 1\), ¿cuáles son todos los valores posibles de\(k\) y\(t ≥ 2\) para qué\(t\) diseños podrían existir? No incluya ningún\(t−(v, t, 1)\) diseño trivial, por lo que puede asumir\(v > k > t\).

3) ¿Es posible que exista un\(3-(16, 6, 1)\) diseño? Si es así, ¿cuántos bloques tendrá? ¿Cuál será el valor de\(r\) ser?

4) Dejar\(B\) ser el\((7, 3, 1)\) -diseño. Definir un nuevo diseño de la\(D\) siguiente manera, sobre las variedades\(\{1, . . . , 8\}\). Cuenta con\(14\) bloques, de dos tipos:

(I) los bloques de\(B\) pero con variedad\(8\) agregada a cada uno; y

(II) los bloques del diseño complementario a\(B\).

Demostrar que se trata de un sistema Steiner con\(t = 3\),\(k = 4\), y\(v = 8\). Utilice la estructura de\(B\) y su complemento para mostrar eso\(λ = 1\); no verifique todos los\(\binom{8}{3}\) posibles\(3\) -subconjuntos de\(\{1, . . . , 8\}\).

5) Definir un diseño de la siguiente manera. Etiquete los bordes de la gráfica completa\(K_6\); estas serán las variedades del diseño. Los bloques son de dos tipos:

(I) cualquier juego de tres bordes\(K_6\) que puedan ser adecuadamente coloreados con el mismo color; y

(II) cualquier conjunto de tres aristas que formen un triángulo en\(K_6\).

Determine los parámetros de este\(t\) -diseño (incluyendo el valor más alto\(t\) para el cual este es un\(t\) -diseño, y justificando cada valor que determine), y demuestre que se trata de un sistema Steiner.

6) ¿Podría existir un\(3 − (20, 5, 8)\) diseño de acuerdo a las condiciones necesarias que hemos determinado (Teorema 18.1.1)? Exponga las fórmulas que deben ser satisfechas y muestre su trabajo.