En matemática combinatoria, un diseño de bloque (o también diseño de bloques) es una estructura de incidencia que consta de un conjunto y de una familia de subconjuntos conocidos como bloques, elegidos de manera que la frecuencia de los elementos satisfaga ciertas condiciones que hacen que la colección de bloques exhiba simetría (esté equilibrada). Los diseños de bloques tienen aplicaciones en muchas áreas, como el diseño experimental, la geometría finita, la fisicoquímica, la pruebas de software, la criptografía y la geometría algebraica.
Sin más especificaciones, el término diseño de bloques generalmente se refiere a un diseño de bloques incompleto equilibrado (BIBD), específicamente (y también como sinónimo) a un 2-diseño, que ha sido el tipo más intensamente estudiado históricamente debido a su aplicación en el diseño experimental. Su generalización se conoce como t-diseño.
Resumen Se dice que un diseño está equilibrado (hasta t) si todos los t-subconjuntos del conjunto original aparecen en el mismo número de bloques (es decir, λ). Cuando t no se especifica, normalmente se puede suponer que es 2, lo que significa que cada par de elementos se encuentra en el mismo número de bloques y el diseño está equilibrado por pares. Para t=1, cada elemento aparece en el mismo número de bloques (el número de replicación, denotado por r) y se dice que el diseño es regular. Cualquier diseño equilibrado hasta t también está equilibrado en todos los valores inferiores de t (aunque con diferentes valores de λ). Así, por ejemplo, para un diseño equilibrado por pares (t=2), el diseño también es regular (t=1). Cuando el requisito de equilibrio falla, un diseño aún puede estar parcialmente equilibrado si los t subconjuntos se pueden dividir en n clases, cada una con su propio valor λ (diferente). Para t=2 estos se conocen como diseños PBIBD(n), cuyas clases forman un esquema de asociación.
Generalmente se dice (o se supone) que los diseños son incompletos, lo que significa que la colección de bloques no son todos los k-subconjuntos posibles, descartando así un diseño trivial.
Un diseño de bloques en el que todos los bloques tienen el mismo tamaño (normalmente denominado k) se denomina uniforme o adecuado. Los diseños discutidos en este artículo son todos uniformes. También se han estudiado diseños de bloques que no necesariamente son uniformes; para t=2 se conocen en la bibliografía con el nombre general diseños equilibrados por pares (PBD).
Los diseños de bloques pueden tener o no bloques repetidos. Los diseños sin bloques repetidos se denominan simples, en cuyo caso la familia de bloques es un conjunto en lugar de un multiconjunto.
En estadística, el concepto de diseño de bloques puede extenderse a diseños de bloques no binarios, en los que los bloques pueden contener múltiples copias de un elemento (véase bloqueado (estadística)). Allí, un diseño en el que cada elemento aparece el mismo número total de veces se denomina equirreplicado, lo que implica un diseño regular solo cuando el diseño también es binario. La matriz de incidencia de un diseño no binario enumera el número de veces que se repite cada elemento en cada bloque.
Diseños uniformes regulares (configuraciones) El tipo más simple de diseño "equilibrado" (t=1) se conoce como configuración táctica o diseño 1. La estructura de incidencia correspondiente en geometría se conoce simplemente como configuración, (véase configuración (geometría)). Este diseño es uniforme y regular: cada bloque contiene k elementos y cada elemento está contenido en r bloques. El número de elementos del conjunto v y el número de bloques b están relacionados por , que es el número total de apariciones de elementos.
Cada matriz booleana con sumas de filas y columnas constantes es la matriz de incidencia de un diseño de bloques uniforme regular. Además, cada configuración tiene un Grafo bipartito birregular correspondiente, conocido como su incidencia o grafo de Levi.
Diseños uniformes equilibrados por pares (2-diseños o BIBD)
Dado un conjunto finito X (de elementos llamados puntos) y tres números enteros k, r, λ ≥ 1, se define un 2-diseño (o BIBD, que significa diseño de bloques incompleto equilibrado) B que es una familia de subconjuntos de k elementos de X, llamados bloques, tales que cualquier x en X está contenido en r bloques, y cualquier par de puntos distintos x e y en X está contenido en λ bloques. En este caso, la condición de que cualquier x en X esté contenido en r bloques es redundante, como se muestra a continuación.
Aquí v (el número de elementos de X, llamados puntos), b (el número de bloques), k, r y λ son los parámetros del diseño (para evitar ejemplos degenerados, también se supone que v > k, de modo que ningún bloque contenga todos los elementos del conjunto. Este es el significado de incompleto en el nombre de estos diseños). La estructura queda reflejada en la tabla siguiente: {|class="wikitable" |v||Puntos, número de elementos de X |- |b||Número de bloques |- |r||Número de bloques que contienen un punto dado |- |k||Número de puntos en un bloque |- |λ||Número de bloques que contienen 2 puntos distintos (o más generalmente t) puntos distintos
El diseño se denomina diseño (v, k, λ) o (v, b, r, k , λ)-diseño. Los parámetros no son todos independientes; v, k y λ determinan b y r, y no todas las combinaciones de v, k y λ son posibles. Las dos ecuaciones básicas que conectan estos parámetros son:
obtenido contando el número de pares (B, p) donde B es un bloque y p es un punto en ese bloque, y
se obtiene al contar para una x fija las tripletas (x, y, B) donde x e y son puntos distintos y B es un bloque que los contiene a ambos. Esta ecuación para cada x también demuestra que r es constante (independiente de x) incluso sin asumirlo explícitamente, demostrando así que la condición de que cualquier x en X' está contenido en r bloques es redundante; y r se puede calcular a partir de otros parámetros.
Estas condiciones no son suficientes porque, por ejemplo, no existe un diseño (43,7,1).Tarry en 1900 demostró que no había ningún par de cuadrados latinos ortogonales de orden seis. El 2-diseño con los parámetros indicados equivale a la existencia de cinco cuadrados latinos de orden seis mutuamente ortogonales.
El orden de un 2-diseño se define como n = r − λ. El complemento de un 2-diseño se obtiene reemplazando cada bloque con su complemento en el conjunto de puntos X. También es un 2-diseño y tiene parámetros v′ = v, b′ = b, r′ = b − r, k′ = v − k, λ′ = λ + b− 2r. Un 2-diseño y su complemento tienen el mismo orden.
Un teorema fundamental, la desigualdad de Fisher, que lleva el nombre del estadístico Ronald Fisher, es que b ≥ v en cualquier 2-diseño.
Un resultado combinatorio bastante sorprendente y no muy obvio pero sí muy general para estos diseños es que si los puntos se denotan mediante cualquier conjunto arbitrariamente elegido de números igualmente o desigualmente espaciados, no se puede elegir un conjunto que pueda formar todas las sumas en bloque (es decir, la suma de todos los puntos en un bloque dado) para obtener un mismo valor constante. Sin embargo, esto puede ser posible para otros diseños, como los diseños de bloques incompletos parcialmente equilibrados. Sin embargo, también se puede observar trivialmente para los cuadrados mágicos o rectángulos mágicos que pueden verse como diseños de bloques incompletos parcialmente equilibrados.
Ejemplos El diseño único (6,3,2) (v = 6, k = 3, λ = 2) tiene 10 bloques (b = 10) y cada elemento se repite 5 veces (r = 5). Usando los símbolos 0 − 5, los bloques son los siguientes tripletes: 012 013 024 035 045 125 134 145 234 235.
y la matriz de incidencia correspondiente (a v×b matriz booleana con suma de fila constante r y suma de columna constante k) es:
Uno de los cuatro diseños no isomorfos (8,4,3) tiene 14 bloques y cada elemento se repite 7 veces. Usando los símbolos 0 − 7, los bloques son las siguientes 4-tuplas:
0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.
El diseño único (7,3,1) es simétrico y tiene 7 bloques con cada elemento repetido 3 veces. Usando los símbolos 0 − 6, los bloques son los siguientes tripletes:
013 026 045 124 156 235 346.
Este diseño está asociado al plano de Fano, y los elementos y bloques del diseño se corresponden con los puntos y las líneas del plano. Su correspondiente matriz de incidencia también puede ser simétrica, si las etiquetas o bloques se ordenan de la forma correcta:
2-diseños simétricos (SBIBD)
El caso de igualdad en la desigualdad de Fisher, es decir, un 2-diseño con igual número de puntos y bloques, se denomina diseño simétrico.También se les ha denominado diseños proyectivos o diseños cuadrados. Estas alternativas se han utilizado en un intento de reemplazar el término simétrico, ya que no hay nada de simétrico (en el significado habitual del término) en estos diseños. El uso de proyectivo se debe a P. Dembowski (Finite Geometries, Springer, 1968), en analogía con el ejemplo más común, los planos proyectivos, mientras que cuadrado se debe a P. Cameron ("Designs, Graphs, Codes and Their Links", Cambridge, 1991) y captura la implicación de que v= b en la matriz de incidencia. Ninguno de los términos ha tenido éxito como sustituto, y estos diseños todavía se denominan universalmente simétricos. Los diseños simétricos tienen la menor cantidad de bloques entre todos los 2-diseños con la misma cantidad de puntos.
En un diseño simétrico, r = k también se cumple que b = v y, aunque generalmente no es cierto en 2-diseños arbitrarios, en un diseño simétrico cada dos bloques distintos coinciden en λ puntos. Un teorema debido a Ryser demuestra la condición recíproca. Si X es un conjunto de v elementos y B es un conjunto de subconjuntos integrados por k de estos v elementos (los bloques), tales que dos bloques distintos tienen exactamente λ puntos en común, entonces (X, B) es un diseño de bloque simétrico.
Los parámetros de un diseño simétrico satisfacen que
Esto impone fuertes restricciones a v, por lo que el número de puntos dista mucho de ser arbitrario. El teorema de Bruck-Ryser-Chowla proporciona condiciones necesarias, pero no suficientes, para la existencia de un diseño simétrico en términos de estos parámetros.
Los siguientes son algunos conocidos ejemplos de 2-diseños simétricos:
Planos proyectivos
Los planos proyectivos finitos son 2-diseños simétricos con λ = 1 y orden n > 1. Para estos diseños, la ecuación de diseño simétrico se convierte en:
Como k = r, se escribir el orden de un plano proyectivo como n = k − 1 y, a partir de la ecuación mostrada arriba, se obtiene que v = (n + 1)n + 1 = n2 + n + 1 puntos en un plano proyectivo de orden n.
Como un plano proyectivo es un diseño simétrico, entonces b = v, lo que significa que b = n2 + n + 1 también. El número b es el número de líneas del plano proyectivo. No puede haber líneas repetidas, ya que λ = 1, por lo que un plano proyectivo es un 2-diseño simple en el que el número de líneas y el número de puntos son siempre los mismos. Para un plano proyectivo, k es el número de puntos en cada línea y es igual a n + 1. De manera similar, r = n + 1 es el número de líneas con las que incide un punto determinado.
Para n = 2 se obtiene un plano proyectivo de orden 2, también llamado plano de Fano, con v = 4 + 2 + 1 = 7 puntos y 7 líneas. En el plano de Fano, cada línea tiene n + 1 = 3 puntos y cada punto pertenece a n + 1 = 3 líneas.
Se sabe que existen planos proyectivos para todos los órdenes que son números primos o potencias de primos. Forman la única familia infinita conocida (con respecto a tener un valor λ constante) de diseños de bloques simétricos.
Biplanos