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 tal manera que la frecuencia de los elementos [ aclaración necesaria ] satisface ciertas condiciones que hacen que la colección de bloques presente 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 mayores especificaciones el término diseño en bloques usualmente se refiere a un diseño en bloques incompletos balanceados ( BIBD ), específicamente (y también como sinónimo) un 2-diseño, 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 es conocida como un t-diseño .
Se dice que un diseño está equilibrado (hasta t ) si todos los t -subconjuntos del conjunto original ocurren en la misma cantidad de bloques (es decir, λ ) [ aclaración necesaria ] . Cuando t no se especifica, generalmente se puede asumir 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 ocurre en el mismo número de bloques (el número de replicación , denotado r ) y se dice que el diseño es regular . Un diseño de bloques en el que todos los bloques tienen el mismo tamaño (generalmente denotado k ) se llama uniforme o apropiado . Los diseños discutidos en este artículo son todos uniformes. También se han estudiado diseños de bloques que no son necesariamente uniformes; para t = 2 se conocen en la literatura con el nombre general de diseños equilibrados por pares (PBD). Cualquier diseño uniforme equilibrado hasta t también está equilibrado en todos los valores inferiores de t (aunque con diferentes valores λ ), por lo que, por ejemplo, un diseño equilibrado por pares ( t = 2 ) también es regular ( t = 1 ). Cuando el requisito de equilibrado falla, un diseño aún puede estar parcialmente equilibrado si los subconjuntos t se pueden dividir en n clases, cada una con su propio (distinto) 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 contiene todos los k -subconjuntos posibles, descartando así un diseño trivial.
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í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.
El tipo más simple de diseño "equilibrado" ( t = 1) se conoce como configuración táctica o 1-diseño . La estructura de incidencia correspondiente en geometría se conoce simplemente como configuración , véase Configuración (geometría) . Un diseño de este tipo 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 ocurrencias de elementos.
Toda matriz binaria con sumas de filas y columnas constantes es la matriz de incidencia de un diseño de bloques uniforme y regular. Además, cada configuración tiene un grafo bipartito birregular correspondiente , conocido como su grafo de incidencia o grafo 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 bloque incompleto balanceado) B como 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. Aquí, 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 contiene 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 ( v , k , λ )-diseño 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
se obtiene 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 ternas ( 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.
Los b y r resultantes deben ser números enteros, lo que impone condiciones a v , k y λ . Estas condiciones no son suficientes ya que, 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 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 , llamada así en honor al estadístico Ronald Fisher , establece que b ≥ v en cualquier diseño de 2 dimensiones.
Un resultado combinatorio bastante sorprendente y no muy obvio (pero muy general) para estos diseños es que si los puntos se denotan por cualquier conjunto elegido arbitrariamente de números espaciados de manera igual o desigual, no hay elección de dicho conjunto que pueda hacer que todas las sumas de bloques (es decir, la suma de todos los puntos en un bloque dado) sean constantes. [5] [6] Sin embargo, para otros diseños, como los diseños de bloques incompletos parcialmente equilibrados, esto puede ser posible. Muchos de estos casos se analizan en [7] . Sin embargo, también se puede observar trivialmente para los cuadrados mágicos o los rectángulos mágicos que pueden verse como los 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 triples:
y la matriz de incidencia correspondiente (una matriz binaria 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. Si se utilizan 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, cada elemento se repite 3 veces. Si se utilizan los símbolos 0 − 6, los bloques son los siguientes triples: [8]
Este diseño está asociado al plano de Fano , correspondiendo los elementos y bloques del diseño a los puntos y líneas del plano. Su matriz de incidencia correspondiente 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 2 con un número igual 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 diseños 2 con el mismo número de puntos.
En un diseño simétrico, r = k se cumple así 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 inverso. 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 cualesquiera tienen exactamente λ puntos en común, entonces ( X, B ) es un diseño de bloque simétrico. [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 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 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 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 2-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 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 biplanar 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 intersecan en dos puntos. [12] Son similares a los planos proyectivos finitos, excepto que en lugar de que dos puntos determinen una línea (y dos líneas determinen un punto), dos puntos determinan dos líneas (respectivamente, puntos). Un biplano de orden n es uno cuyos bloques tienen k = n + 2 puntos; tiene v = 1 + ( n + 2)( n + 1)/2 puntos (ya que r = k ).
A continuación se enumeran los 18 ejemplos conocidos [13] .
Los biplanos de órdenes 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, convertir 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 un 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 un 0. La matriz 0–1 resultante M es la matriz de incidencia de un diseño simétrico 2-(4 a − 1, 2 a − 1, a − 1) llamado diseño 2 de Hadamard . [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 simétrico 2 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 diseños 2-resolubles arquetípicos son los planos afines finitos . Una solución del famoso problema de las 15 colegialas es una resolución de un diseño 2-(15,3,1). [22]
Dado cualquier entero positivo t , un t -diseño B es una clase de subconjuntos de elementos k de X , llamados bloques , de modo que cada punto x en X aparece exactamente en r bloques, y cada subconjunto de elementos t 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 llamarse un t- ( v , k ,λ)-diseño. Nuevamente, estos cuatro números determinan b y r y los cuatro números en sí mismos 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 indica 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 como conjunto de puntos X − { p } y como conjunto de bloques todos los bloques de D que contienen p con p eliminado. Es un diseño ( t − 1)-( v − 1, k − 1, λ ). Nótese que los diseños derivados con respecto a diferentes puntos pueden no ser isomorfos. Un diseño E se llama una extensión de D si E tiene un punto p tal que E p es isomorfo a D ; llamamos a 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 extensible (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:
Obsérvese que el plano proyectivo de orden dos es un diseño 2 de Hadamard; 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 inversos, de hecho, de todos los planos inversos 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 del plano 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 ovoide . Todos los planos inversos conocidos son ovoideos.
Un ejemplo de ovoide es la cuadrática 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 de 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 ); por lo que q es una potencia prima y existe un único plano inverso ovoide de orden q . (Pero se desconoce si existen otros que no sean ovoideos.) (b) Si q es par, entonces q es una potencia de 2 y cualquier plano inverso de orden q es ovoide (pero puede haber algunos ovoides desconocidos).
Un esquema de asociación de n -clases consiste en 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 la relación R i son i th– asociados . Cada elemento de X tiene n i i th asociados. Además:
Un esquema de asociación es conmutativo si para todos los i , j y k . La mayoría de los autores asumen esta propiedad.
Un diseño de bloque incompleto parcialmente balanceado con n clases asociadas (PBIBD( n )) es un diseño de bloque basado en un v -conjunto X con b bloques cada uno de tamaño k y con cada elemento apareciendo en r bloques, de modo que hay un esquema de asociación con n clases definidas en X donde, si los elementos x e y son i- ésimos asociados, 1 ≤ i ≤ n , entonces están juntos en precisamente λ i bloques.
Un PBIBD( n ) determina un esquema de asociación, pero lo inverso 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 λ 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) han sido los más estudiados porque son los más simples y útiles de todos. [33] Se dividen en seis tipos [34] según una clasificación de los PBIBD(2) conocidos en ese momento 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 los diseños de bloques.
Si bien los orígenes del tema se basan en aplicaciones biológicas (al igual que 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 unos investigadores del cáncer de piel quieren probar tres protectores solares diferentes. Aplican dos protectores solares diferentes en la parte superior de las manos de una persona de prueba. Después de una exposición a la radiación UV, registran la irritación de la piel en términos de quemaduras solares. El número de tratamientos es 3 (protectores solares) y el tamaño del bloque es 2 (manos por persona).
Se puede generar un BIBD correspondiente mediante la función R design.bib del paquete R agricolae y se especifica en la siguiente tabla:
El investigador selecciona los parámetros v = 3 , k = 2 y λ = 1 para el diseño del bloque, que luego se insertan en la función R. Posteriormente, los parámetros restantes b y r se determinan automáticamente.
Utilizando las relaciones básicas calculamos que necesitamos b = 3 bloques, es decir, 3 personas de prueba para obtener un diseño de bloques incompleto y equilibrado. Etiquetando los bloques A , B y C para evitar confusiones, tenemos el diseño de bloques,
En la siguiente tabla se especifica una matriz de incidencia correspondiente:
Cada tratamiento ocurre en 2 bloques, por lo que r = 2 .
Un solo 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 lo 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.
