17.2: Construcción de diseños y existencia de diseños
- Page ID
- 114379
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Hay una serie de buenos métodos para construir diseños. Discutiremos algunos de estos métodos en esta sección. Para algunos de ellos, debes comenzar con un diseño, y usarlo para crear un diseño diferente.
Método\(1\): Repetir Bloques
Este es probablemente el más fácil, y (no es sorprendente) el menos útil de nuestros métodos de construcción.
Comience con un BIBD\((v, k, λ)\). Para cada bloque del diseño, cree\(t\) copias de ese bloque. El resultado será un BIBD\((v, k, tλ)\).
Método\(2\): Tomar el complemento
Este método también requiere comenzar con un diseño. Empezar con\((V, B)\), un BIBD\((v, k, λ)\).
Reemplazar cada bloque\(B ∈ \mathcal{B}\) con su bloque complementario,\(B^c = V \setminus \mathcal{B}\). Entonces
\((V, \{B^c | B ∈ B\})\)
es un diseño.
Definición: Diseño Complementario
Llamamos al diseño construido por este método, el diseño complementario o complemento del diseño con el que comenzamos.
Proposición\(\PageIndex{1}\)
El complemento de un BIBD\((v, k, λ)\) es un BIBD\((v, v − k, b − 2r + λ)\).
- Prueba
-
La prueba de esta proposición se deja al lector, como Ejercicio 17.2.1 (1).
Ejemplo\(\PageIndex{1}\)
El complemento del diseño dado en el Ejemplo 17.2.2, es el siguiente:
\ [\ comenzar {ecuación}\ comenzar {dividir} &\ {e, f, g, h, i, j, k, l, m, n, o, p\},\;\;\;\; &\ {a, b, c, d, i, j, k, l, m, m, n, o, p\}\\
&\ {a, b, c, d, e, f, g, h, m, n, o, p\},\;\;\;\; &\ {a, b, c, d, e, f, g, h, i, j, k, l\}\\ &\ {b, c, d, f, g, h, j, k, l, n, o, p\},\;\;\; &\ {b, c, d, e, g, h, i, k, l, m, o, p\}\\\ &\ {b, c, d, e, f, h, i, j, l, m, n, p\},\;\;\;\; &\ {b, c, d, e, f, g, i, j, k, m, n, o\}\\ &\, c, d, f, g, h, i, k, l, m, n, p\},\;\;\; &\ {a, c, d, e, g, h, j.k.l, m, n, o\}\\ &\ {a, c, d, e, f, h, i, j, k, n, o, p\},\;\;\;\; &\ {a, c, d, e, f, g, i, j , l, m, o, p\}\\ &\ {a, b, d, f, g, h, i, j, k, m, n, p\},\;\;\;\; &\ {a, b, d, e, g, h, i, j, l, m, n, o\}\\ &\ {a, b, d, e, f, h, j, k, l, m, o, p\},\;\;\;\; &\ {a, b, d, e, f, g, i, k, l, n, o, p\}\\ &\ {a, b, c, e, g, h, i, j, k, n, o, p\},\;\;\; y\ {a, b, c, e, g, h, i, j, k, n, o, p\} \\ &\ {a, b, c, e, f, h, i, k, l, m, n, o\},\;\;\;\; &\ {a, b, c, e, f, g, j, k, l, m, n, p\}\ final {división}\ final {ecuación}\]
Sus parámetros son\(b = 20\),\(v = 16\),\(r = 15\),\(k = 12\),\(λ = 11\).
Método 3: diseños cíclicos
Este método puede ser más fácil de pensar en términos de la coloración de la gráfica asociada. Existen varias versiones más complicadas de esta construcción que nos permiten construir diseños adicionales, pero para los fines de este curso, nos centraremos en la versión más básica. Esta versión más básica desafortunadamente solo funciona cuando\(v\) es impar.
Definición: Colección de diferencias y conjunto de diferencias
Arreglar un entero impar\(n\). Una colección de conjuntos\(D_1, . . . , D_m ⊆ \{1, . . . , n\}\) es una colección de diferencias para\(n\), si tomando las diferencias\(j − i\) para cada par\(i \neq j\) con\(i\),\(j ∈ D_k\) para cada conjunto\(D_k\), alcanza cada uno de los valores\(±1, . . . , ±\dfrac{(n − 1)}{2}\), exactamente una vez, cuando se realizan cálculos módulo \(n\). Si\(m = 1\) entonces\(D_1\) se llama un conjunto de diferencias.
Ejemplo\(\PageIndex{2}\)
La colección\(\{1, 2, 5\}\),\(\{1, 3, 10\}\),\(\{1, 7, 15\}\) es una colección de diferencia para\(n = 19\). Las diferencias que alcanzamos aparecen en la siguiente tabla.
| Conjunto de Diferencia | \(i\) | \(j\) | \(j − i, i − j\) | ||
|---|---|---|---|---|---|
| \(D_1\) | \ (i\) ">\(1\) | \ (j\) ">\(2\) | \ (j − i, i − j\) ">\(±1\) | ||
| \(D_1\) | \ (i\) ">\(1\) | \ (j\) ">\(5\) | \ (j − i, i − j\) ">\(±4\) | ||
| \(D_1\) | \ (i\) ">\(2\) | \ (j\) ">\(5\) | \ (j − i, i − j\) ">\(±3\) | ||
| \(D_2\) | \ (i\) ">\(1\) | \ (j\) ">\(3\) | \ (j − i, i − j\) ">\(±2\) | ||
| \(D_2\) | \ (i\) ">\(1\) | \ (j\) ">\(10\) | \ (j − i, i − j\) ">\(±9\) | ||
| \(D_2\) | \ (i\) ">\(3\) | \ (j\) ">\(10\) | \ (j − i, i − j\) ">\(±7\) | ||
| \(D_3\) | \ (i\) ">\(1\) | \ (j\) ">\(7\) | \ (j − i, i − j\) ">\(±6\) | ||
| \(D_3\) | \ (i\) ">\(1\) | \ (j\) ">\(15\) | \ (j − i, i − j\) ">\(±14 ≡ ±5 (\text{mod } 19)\) | ||
| \(D_3\) | \ (i\) ">\(7\) | \ (j\) ">\(15\) | \ (j − i, i − j\) ">\(±8\) | ||
Supongamos que tenemos una colección de diferencia para\(v\) en la que cada conjunto\(D_1, . . . , D_m\) tiene la misma cardinalidad. Usar\(D_i + \ell\) para denotar el conjunto
\(\{d + \ell (\text{mod } v) | d ∈ D_i\}\),
realizando la aritmética modular para asegurar que\(D_i + \ell ⊆ \{1, . . . , v\}\). Luego los sets
\(\{D_i + \ell | 1 ≤ i ≤ m, 0 ≤ \ell ≤ v − 1\}\)
formar un BIBD\((v, |D_1|, 1)\).
En el ejemplo anterior, tomando los 57 conjuntos\(\{1, 2, 5\} + \ell\),\(\{1, 3, 10\} + \ell\), y\(\{1, 7, 15\} + \ell\), donde\(0 ≤ \ell ≤ 18\), da un BIBD\((19, 3, 1)\).
Repasemos de nuevo esta construcción, pensando en la versión gráfica del problema. Por simplicidad, solo veremos el estuche especial\(λ = 1\). Entonces nuestro objetivo es colorear los bordes de la gráfica\(K_v\) completa para asegurar que cada clase de color sea una\(K_k\). Si dibujamos los vértices de la gráfica en un círculo, y pensamos en la longitud de un borde como uno más que el número de vértices entre sus extremos a medida que viaja alrededor del círculo en la dirección que sea más corta, entonces por cada longitud posible entre\(1\) y\(\dfrac{(v − 1)}{2}\),\(K_v\) tiene \(v\)bordes de esa longitud. (Aquí es donde surge el problema si\(v\) es par: solo hay\(\dfrac{v}{2}\) bordes de longitud\(\dfrac{v}{2}\).) Además, si giramos cualquier borde en un paso alrededor de la gráfica (es decir, mover ambos puntos finales un paso en la misma dirección) repetidamente, después de\(v\) tales rotaciones habremos movido el borde sobre cada otro borde de esa longitud.
Estas ideas demuestran que si podemos llegar a un conjunto de\(K_k\) s, de tal manera que cada longitud de borde aparezca exactamente en uno de los\(K_k\) s, entonces tomando cada uno de estos así como cada rotación posible de cada uno de estos, como clase de color, encontramos nuestra deseada coloración de bordes de\(K_v\).
Una imagen vale más que mil palabras. El ejemplo anterior equivale a la coloración de bordes para\(K_{19}\) que cada clase de color forme una\(K_3\), ya que\(v = 19\) y\(k = 3\). Las longitudes de borde en\(K_{19}\) son\(\{1, . . . , 9\}\). Mostraremos tres\(K_3\) s, de tal manera que cada longitud de borde de\(\{1, . . . , 9\}\) aparece exactamente en uno de ellos. Al rotar cada uno de ellos, dando a cada rotación un nuevo color, obtenemos\(57\)\(K_3\) s que usan cada borde de\(K_{19}\) exactamente una vez. Hemos etiquetado los vértices\(19\) para que\(1\) las longitudes de los bordes sean más fáciles de calcular. Este libro de texto está impreso en blanco y negro, por lo que, en lugar de dibujar colores reales en los bordes, dibujaremos bordes sólidos para azul, bordes punteados para rojo y bordes discontinuos para verde.
El triángulo sólido (o azul) tiene bordes de longitudes\(1\),\(3\), y\(4\); el triángulo punteado (o rojo) tiene bordes de longitudes\(2\)\(7\),, y\(9\); y el triángulo discontinuas (o verde) tiene bordes de longitudes\(6\),\(8\), y\(5\).
Un diseño creado usando este método se denomina diseño cíclico, ya que un pequeño número de “bloques de arranque” se están rotando cíclicamente (en la gráfica) para encontrar los bloques restantes del diseño.
Observe que para que exista un diseño cíclico, ya que cada conjunto en la colección de diferencias conduce a\(v\) bloques en el diseño final,\(b\) debe ser un múltiplo de\(v\).
Aunque estos métodos pueden crear exitosamente diseños con muchos conjuntos diferentes de parámetros, no son suficientes para permitirnos determinar los parámetros para los cuales existen BIBD. Señalamos anteriormente que las condiciones necesarias dadas en el Teorema 17.1.3 no son suficientes para garantizar la existencia de un BIBD con un conjunto particular de parámetros. Sin embargo, hay un resultado muy poderoso en esta línea, conocido como Teorema de Wilson. Nos dice que si arreglamos\(k\), solo hay finitamente muchos valores para\(v\) que satisfagan las condiciones necesarias pero para los que no\((v, k, 1)\) existe BIBD. Entonces por Método\(1\) (bloques repetitivos), si\((v, k, 1)\) existe un BIBD, entonces también lo hace un BIBD\((v, k, λ)\) para cualquiera\(λ\). Aquí hay una declaración formal del teorema de Wilson.
Teorema\(\PageIndex{1}\): Wilson's Theorem
Dado\(k\), hay un entero\(v(k)\) tal que por cada\(v > v(k)\) que satisface las tres condiciones:
- \(v ∈ \mathbb{Z}\);
- \(\dfrac{v(v − 1)}{[k(k − 1)]} ∈ \mathbb{Z}\); y
- \(\dfrac{(v − 1)}{(k − 1)} ∈ \mathbb{Z}\),
\((v, k, 1)\)existe un BIBD.
- Prueba
-
No vamos a dar una prueba de este teorema.
Ejercicio\(\PageIndex{1}\)
1) Demostrar que el complemento de un BIBD es efectivamente un diseño, y que tiene los parámetros que afirmamos en la Proposición 17.2.1.
[Pista: Use inclusión-exclusión para determinar cuántos bloques del diseño original no contienen ningún punto de un par arbitrario.]
2) Encontrar el complemento del BIBD\((8, 4, 3)\) dado por\(V = \{1, 2, 3, 4, 5, 6, 7, 8\}\) y
\[\mathcal{B}=\left\{ \begin{array}{ll} \{1, 2, 3, 4\}, \{5, 6, 7, 8\}, \{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{2, 4, 6, 8\},\\ \{1, 3, 5, 7\}, \{1, 3, 6, 8\}, \{2, 4, 5, 7\}, \{1, 4, 5, 8\}, \{1, 4, 6, 7\}, \{2, 3, 5, 8\}, \{2, 3, 6, 7\}\end{array}\right\}.\]
3) Al agregar dos conjuntos más a los conjuntos\(\{1, 3, 7\}\) y\(\{1, 6, 13\}\), se puede crear una colección de diferencias para\(25\) en la que cada uno de los conjuntos tenga\(3\) elementos, y así un BIBD cíclico\((25, 3, 1)\). Encuentra dos juegos para agregar.
4) Utilice un conjunto de diferencias para construir un\((11, 11, 5, 5, 2)\) diseño cíclico.
5) Demostrar que la colección\(\mathcal{C} = \left\{ \{0, 1, 3\}, \{0, 4, 5\}, \{0, 4, 7\}, \{0, 5, 7\} \right\} \) es una colección de diferencia para\(13\). Construir el diseño y dar sus parámetros.
6) Determinar si el conjunto dado\(D\) es un conjunto de diferencias para el valor dado de\(n\). Si se trata de un conjunto de diferencias, encuentre los parámetros del BIBD cíclico resultante.
(a)\(D = \{1, 2, 4, 10\}\) para\(n = 13\).
b)\(D = \{2, 4, 5, 6, 10\}\) para\(n = 21\).
7) Demostrar que en cualquier diseño cíclico, existe un entero\(c\) tal que\(b = cv\),\(ck(k − 1) = λ(v − 1)\), y\(r = ck\). ¿Cuál es la significación\(c\) en términos del diseño?
8) Explicar por qué un BIBD con\(v = 6\),\(b = 10\),\(k = 3\),\(r = 5\), y\(λ = 2\) no puede ser cíclico.
9) ¿La condición que probaste en Problem\(7\) muestra que un BIBD con\(v = 61\),\(b = 305\),\(k = 4\),\(r = 20\), y\(λ = 1\) no puede ser cíclico?