En matemáticas combinatorias , un diseño de bloques es una estructura de incidencia que consiste en un conjunto junto con una familia de subconjuntos conocidos como bloques , elegidos de manera que la frecuencia de los elementos [ aclaración necesaria ] satisfaga ciertas condiciones que hacen que la colección de bloques exhiba simetría (equilibrio). Los diseños de bloques tienen aplicaciones en muchas áreas, incluido el diseño experimental , la geometría finita , la química física , las pruebas de software , la criptografía y la geometría algebraica .
Sin más especificaciones, el término diseño de bloques suele referirse a un diseño de bloques incompletos equilibrados ( BIBD ), concretamente (y también como sinónimo) un diseño de 2, que ha sido el tipo más intensamente estudiado históricamente debido a su aplicación en el diseño de experimentos . [1] [2] Su generalización se conoce como diseño t .
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, λ ) [ se necesita aclaración ] . 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 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 λ ), por lo que, por ejemplo, un diseño equilibrado por pares ( t =2) 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 (diferente) valor λ . 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 (generalmente denotado k ) se llama 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 literatura con el nombre general de diseños balanceados por pares (PBD).
Los diseños de bloques pueden tener o no bloques repetidos. Los diseños sin bloques repetidos se denominan simples , [3] 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 (ver bloqueo (estadísticas) ). Allí, un diseño en el que cada elemento aparece el mismo número total de veces se denomina equivalente, lo que implica un diseño regular sólo 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.
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 , ver 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 binaria 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 su correspondiente gráfico bipartito biregular conocido como su incidencia o gráfico de Levi .
Dado un conjunto finito X (de elementos llamados puntos ) y números enteros k , r , λ ≥ 1, definimos un diseño de 2 (o BIBD , que significa diseño de bloques incompletos equilibrados) B como una familia de k -subconjuntos de elementos de X , llamados bloques , de modo 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. Aquí, la condición de que cualquier x en X esté contenida 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). En una tabla:
El diseño se denomina diseño ( v , k , λ ) o diseño ( v , b , r , k , λ ). 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 los triples ( 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 puede calcularse a partir de los otros parámetros.
Estas condiciones no son suficientes porque, por ejemplo, no existe un diseño (43,7,1). [4]
El orden de un diseño 2 se define como n = r - λ . El complemento de un diseño a 2 se obtiene reemplazando cada bloque con su complemento en el conjunto de puntos X. También es un diseño 2 y tiene parámetros v ′ = v , b ′ = b , r ′ = b − r , k ′ = v − k , λ ′ = λ + b − 2 r . Un diseño 2 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 diseño 2.
Un resultado combinatorio bastante sorprendente y no muy obvio (pero muy general) para estos diseños es que si los puntos se denotan mediante cualquier conjunto elegido arbitrariamente de números numéricos igualmente o desigualmente espaciados, no se puede elegir un conjunto que pueda formar todas las sumas en bloque. (es decir, suma de todos los puntos en un bloque determinado) constante. [5] [6] Sin embargo, esto puede ser posible para otros diseños, como los diseños de bloques incompletos parcialmente equilibrados. Muchos de estos casos se analizan en [7] 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.
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). [8] Usando los símbolos 0 − 5, los bloques son los siguientes tripletes:
y la matriz de incidencia correspondiente ( matriz binaria a v × b con suma de filas constante r y suma de columnas 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: [8]
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 triples: [8]
Este diseño está asociado al plano de Fano , siendo los elementos y bloques del diseño correspondientes a los puntos y 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:
El caso de igualdad en la desigualdad de Fisher, es decir, un diseño de 2 con igual número de puntos y bloques, se denomina diseño simétrico . [9] Los diseños simétricos tienen el menor número de bloques entre todos los 2 diseños con el mismo número de puntos.
En un diseño simétrico, r = k se cumple tan bien como b = v y, aunque generalmente no es cierto en diseños 2 arbitrarios, en un diseño simétrico cada dos bloques distintos se encuentran en λ puntos. [10] Un teorema de Ryser proporciona lo contrario. Si X es un conjunto de v elementos y B es un conjunto de v elementos de k subconjuntos de elementos (los "bloques"), de modo que dos bloques distintos tengan exactamente λ puntos en común, entonces ( X, B ) es un Diseño de bloques simétricos. [11]
Los parámetros de un diseño simétrico satisfacen
Esto impone fuertes restricciones a v , por lo que el número de puntos está lejos 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 ejemplos importantes de diseños 2 simétricos:
Los planos proyectivos finitos son diseños 2 simétricos con λ = 1 y orden n > 1. Para estos diseños, la ecuación de diseño simétrica se convierte en:
Como k = r podemos escribir el orden de un plano proyectivo como n = k − 1 y, de la ecuación mostrada arriba, obtenemos v = ( n + 1) n + 1 = n 2 + n + 1 puntos en un plano proyectivo plano de orden n .
Como un plano proyectivo es un diseño simétrico, tenemos b = v , lo que significa que b = n 2 + 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 diseño simple de 2 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 dado.
Para n = 2 obtenemos un plano proyectivo de orden 2, también llamado plano de Fano , con v = 4 + 2 + 1 = 7 puntos y 7 rectas. En el plano de Fano, cada recta tiene n + 1 = 3 puntos y cada punto pertenece a n + 1 = 3 rectas.
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. [12]
Un biplano o geometría biplano es un diseño 2 simétrico con λ = 2; es decir, cada conjunto de dos puntos está contenido en dos bloques ("líneas"), mientras que dos líneas cualesquiera se cruzan en dos puntos. [12] Son similares a los planos proyectivos finitos, excepto que en lugar de dos puntos que determinan una línea (y dos líneas que determinan un punto), dos puntos determinan dos líneas (respectivamente, puntos). Un biplano de orden n es aquel cuyos bloques tienen k = n + 2 puntos; tiene v = 1 + ( n + 2)( n + 1)/2 puntos (ya que r = k ).
Los 18 ejemplos conocidos [13] se enumeran a continuación.
Los biplanos de orden 5, 6, 8 y 10 no existen, como lo demuestra el teorema de Bruck-Ryser-Chowla .
Una matriz de Hadamard de tamaño m es una matriz H de m × m cuyas entradas son ±1 tal que HH ⊤ = m I m , donde H ⊤ es la transpuesta de H e I m es la matriz identidad de m × m . Una matriz de Hadamard se puede poner en forma estandarizada (es decir, convertida a una matriz de Hadamard equivalente) donde las entradas de la primera fila y la primera columna son todas +1. Si el tamaño m > 2 entonces m debe ser múltiplo de 4.
Dada una matriz de Hadamard de tamaño 4 a en forma estandarizada, elimine la primera fila y la primera columna y convierta cada −1 en 0. La matriz 0–1 resultante M es la matriz de incidencia de una matriz simétrica 2-(4 a − 1, 2 a − 1, a − 1) diseño llamado diseño Hadamard 2 . [19] Contiene bloques/puntos; cada uno contiene/está contenido en puntos/bloques. Cada par de puntos está contenido exactamente en bloques.
Esta construcción es reversible y la matriz de incidencia de un diseño 2 simétrico con estos parámetros se puede utilizar para formar una matriz de Hadamard de tamaño 4 a .
Un diseño 2 resoluble es un BIBD cuyos bloques se pueden dividir en conjuntos (llamados clases paralelas ), cada uno de los cuales forma una partición del conjunto de puntos del BIBD. El conjunto de clases paralelas se denomina resolución del diseño.
Si un diseño resoluble 2-( v , k ,λ) tiene c clases paralelas, entonces b ≥ v + c − 1. [20]
En consecuencia, un diseño simétrico no puede tener una resolución no trivial (más de una clase paralela). [21]
Los 2 diseños arquetípicos resolubles son los planos afines finitos . Una solución del famoso problema de las 15 colegialas es la resolución de un diseño 2-(15,3,1). [22]
Dado cualquier entero positivo t , un diseño t B es una clase de k subconjuntos de elementos de X , llamados bloques , tales que cada punto x en X aparece exactamente en r bloques, y cada subconjunto de t elementos T aparece exactamente en λ bloques . Los números v (el número de elementos de X ), b (el número de bloques), k , r , λ y t son los parámetros del diseño. El diseño puede denominarse diseño t -( v , k ,λ). Nuevamente, estos cuatro números determinan byr y los cuatro números en sí no pueden elegirse arbitrariamente. Las ecuaciones son
donde λ i es el número de bloques que contienen cualquier conjunto de puntos de i elementos y λ t = λ.
Tenga en cuenta que y .
Teorema : [23] Cualquier diseño t -( v , k ,λ) es también un diseño s -( v , k ,λ s ) para cualquier s con 1 ≤ s ≤ t . (Tenga en cuenta que el "valor lambda" cambia como se indicó anteriormente y depende de s ).
Una consecuencia de este teorema es que todo diseño t con t ≥ 2 es también un diseño 2.
Un diseño t -( v , k ,1) se denomina sistema Steiner .
El término diseño de bloques por sí solo generalmente significa un diseño de 2.
Sea D = ( X , B ) un diseño t-( v , k , λ ) y p un punto de X . El diseño derivado D p tiene un conjunto de puntos X − { p } y como bloque establece todos los bloques de D que contienen p sin p. Es un diseño ( t − 1)-( v − 1, k − 1, λ ). Tenga en cuenta que los diseños derivados con respecto a diferentes puntos pueden no ser isomórficos. Un diseño E se llama extensión de D si E tiene un punto p tal que Ep es isomorfo a D ; llamamos D extensible si tiene una extensión.
Teorema : [24] Si un diseño t -( v , k , λ ) tiene una extensión, entonces k + 1 divide a b ( v + 1).
Los únicos planos proyectivos extensibles (diseños simétricos 2-( n 2 + n + 1, n + 1, 1)) son los de órdenes 2 y 4. [25]
Cada diseño Hadamard 2 es ampliable (a un diseño Hadamard 3 ). [26]
Teorema :. [27] Si D , un diseño simétrico 2-( v , k ,λ), es extensible, entonces se cumple una de las siguientes condiciones:
Tenga en cuenta que el plano proyectivo de orden dos es un diseño de Hadamard 2; el plano proyectivo de orden cuatro tiene parámetros que caen en el caso 2; Los únicos otros diseños 2 simétricos conocidos con parámetros en el caso 2 son los biplanos de orden 9, pero ninguno de ellos es extensible; y no se conoce ningún diseño 2 simétrico con los parámetros del caso 3. [28]
Un diseño con los parámetros de la extensión de un plano afín , es decir, un diseño 3-( n 2 + 1, n + 1, 1), se denomina plano inverso finito , o plano de Möbius , de orden n .
Es posible dar una descripción geométrica de algunos planos inversivos, de hecho, de todos los planos inversivos conocidos. Un ovoide en PG(3, q ) es un conjunto de q 2 + 1 puntos, no tres colineales. Se puede demostrar que cada plano (que es un hiperplano ya que la dimensión geométrica es 3) de PG(3, q ) se encuentra con un ovoide O en 1 o q + 1 puntos. Las secciones planas de tamaño q + 1 de O son los bloques de un plano inverso de orden q . Cualquier plano inverso que surja de esta manera se llama huevo . Todos los planos inversivos conocidos tienen forma de huevo.
Un ejemplo de ovoide es la cuádrica elíptica , el conjunto de ceros de la forma cuadrática
donde f es una forma cuadrática irreducible en dos variables sobre GF( q ). [ f ( x , y ) = x 2 + xy + y 2 por ejemplo].
Si q es una potencia impar de 2, se conoce otro tipo de ovoide: el ovoide Suzuki-Tits .
Teorema . Sea q un entero positivo, al menos 2. (a) Si q es impar, entonces cualquier ovoide es proyectivamente equivalente a la cuádrica elíptica en una geometría proyectiva PG(3, q ); entonces q es una potencia primaria y hay un plano inverso de orden q en forma de huevo único . (Pero se desconoce si existen planos que no tienen forma de huevo.) (b) si q es par, entonces q es una potencia de 2 y cualquier plano inverso de orden q es similar a un huevo (pero puede haber algunos ovoides desconocidos).
Un esquema de asociación de n clases consta de un conjunto X de tamaño v junto con una partición S de X × X en n + 1 relaciones binarias , R 0 , R 1 , ..., R n . Se dice que un par de elementos en relación Ri son asociados i - ésimo . Cada elemento de X tiene n i i ésimos asociados. Además:
Un esquema de asociación es conmutativo si para todos i , j y k . La mayoría de los autores asumen esta propiedad.
Un diseño de bloques incompletos parcialmente balanceados con n clases asociadas (PBIBD( n )) es un diseño de bloques basado en un conjunto v X con b bloques cada uno de tamaño k y con cada elemento apareciendo en r bloques, de modo que exista un esquema de asociación. con n clases definidas en X donde, si los elementos xey son i - ésimos asociados, 1 ≤ i ≤ n , entonces están juntos precisamente en λ i bloques.
Un PBIBD( n ) determina un esquema de asociación pero lo contrario es falso. [29]
Sea A (3) el siguiente esquema de asociación con tres clases asociadas en el conjunto X = {1,2,3,4,5,6}. La entrada ( i , j ) es s si los elementos i y j están en relación R s .
Los bloques de un PBIBD(3) basado en A (3) son:
Los parámetros de este PBIBD(3) son: v = 6, b = 8, k = 3, r = 4 y λ 1 = λ 2 = 2 y λ 3 = 1. Además, para el esquema de asociación tenemos n 0 = n 2 = 1 y n 1 = n 3 = 2. [30] La matriz de incidencia M es
y la matriz de concurrencia MM T es
de donde podemos recuperar los valores de λ y r .
Los parámetros de un PBIBD( m ) satisfacen: [31]
Un PBIBD(1) es un BIBD y un PBIBD(2) en el que λ 1 = λ 2 es un BIBD. [32]
Los PBIBD(2) son los que más se han estudiado porque son los más simples y útiles de los PBIBD. [33] Se dividen en seis tipos [34] según una clasificación de los entonces conocidos PBIBD(2) realizada por Bose y Shimamoto (1952): [35]
El tema matemático de los diseños de bloques se originó en el marco estadístico del diseño de experimentos . Estos diseños fueron especialmente útiles en aplicaciones de la técnica de análisis de varianza (ANOVA) . Esta sigue siendo un área importante para el uso de diseños de bloques.
Si bien los orígenes del tema se basan en aplicaciones biológicas (como parte de la terminología existente), los diseños se utilizan en muchas aplicaciones donde se realizan comparaciones sistemáticas, como en las pruebas de software .
La matriz de incidencia de los diseños de bloques proporciona una fuente natural de códigos de bloques interesantes que se utilizan como códigos de corrección de errores . Las filas de sus matrices de incidencia también se utilizan como símbolos en una forma de modulación de posición de pulso . [36]
Supongamos que los investigadores del cáncer de piel quieren probar tres protectores solares diferentes. Cubren dos protectores solares diferentes en la parte superior de las manos de una persona de prueba. Después de una radiación ultravioleta se registra la irritación de la piel en términos de quemaduras solares. El número de tratamientos es de 3 (protectores solares) y el tamaño del bloque es de 2 (manos por persona).
La función R design.bib del paquete R agricolae puede generar un BIBD correspondiente y se especifica en la siguiente tabla:
El investigador elige los parámetros v = 3 , k = 2 y λ = 1 para el diseño del bloque que luego se insertan en la función R. A continuación se determinan automáticamente los demás parámetros b y r .
Usando las relaciones básicas calculamos que necesitamos b = 3 bloques, es decir, 3 personas de prueba para obtener un diseño de bloques incompletos equilibrado. Etiquetando los bloques A , B y C , para evitar confusiones, tenemos el diseño de bloques,
Una matriz de incidencia correspondiente se especifica en la siguiente tabla:
Cada tratamiento ocurre en 2 bloques, entonces r = 2 .
Solo un bloque ( C ) contiene los tratamientos 1 y 2 simultáneamente y lo mismo se aplica a los pares de tratamientos (1,3) y (2,3). Por tanto, λ = 1 .
Es imposible utilizar un diseño completo (todos los tratamientos en cada bloque) en este ejemplo porque hay 3 protectores solares para probar, pero solo 2 manos en cada persona.
