Hispanopedia Wiki
Articulo de referencia

Diseño de bloques

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 , el...

Hispanopedia WikiContenido en espanolLectura gratuita

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 el número de ocurrencias de cada elemento satisfaga ciertas condiciones, lo que hace que la colección de bloques presente simetría (equilibrio). Los diseños de bloques tienen aplicaciones en muchas áreas, incluyendo 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 generalmente se refiere a un diseño de bloques incompletos balanceados ( BIBD ), específicamente (y también como sinónimo) un diseño 2, que ha sido el tipo más estudiado históricamente debido a su aplicación en el diseño de experimentos . [ 1 ] [ 2 ] Su generalización se conoce como un diseño t .

Descripción general

Se dice que un diseño está equilibrado (hasta t ) si todos los subconjuntos de t elementos del conjunto original aparecen en la misma cantidad de bloques (es decir, λ ) . Cuando t no está especificado, generalmente se puede asumir que es  2, lo que significa que cada par de elementos se encuentra en la misma cantidad de bloques y el diseño está equilibrado por pares . Para t  =  1, cada elemento aparece en la misma cantidad de bloques (el número de replicación , denotado por 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 por k ) se llama uniforme o propio . Los diseños que se analizan 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 de λ ), por lo que, por ejemplo, un diseño equilibrado por pares ( t  =  2) también es regular ( t  =  1). Cuando falla el requisito de equilibrio, un diseño aún puede estar parcialmente equilibrado si los subconjuntos t se pueden dividir en n clases, cada una con su propio valor de λ (diferente) . Para t  =  2, estos se conocen como diseños PBIBD( n ) , cuyas clases forman un esquema de asociación .

Por lo general, se dice (o se supone) que los diseños son incompletos , lo que significa que la colección de bloques no son todos los subconjuntos k posibles , lo que descarta 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 (véase bloqueo (estadística) ). En este caso, un diseño en el que cada elemento aparece el mismo número total de veces se denomina equirréplica, 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 indica el número de veces que se repite cada elemento en cada bloque.

Diseños (configuraciones) uniformes regulares

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) . Dicho 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 porbk=vr{\displaystyle bk=vr}, que es el número total de ocurrencias del elemento.

Toda 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 un grafo bipartito birregular correspondiente , conocido como su grafo de incidencia o grafo de Levi .

Diseños uniformes equilibrados por pares (diseños de 2 dimensiones o BIBD)

Dado un conjunto finito X (de elementos llamados puntos ) y enteros k , r , λ ≥ 1, definimos un 2-diseño (o BIBD , por sus siglas en inglés, que significa diseño de bloques incompletos balanceados) 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 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 relacionan estos parámetros son:

bk=vr,{\displaystyle bk=vr,}

obtenido al contar el número de pares ( B , p ) donde B es un bloque y p es un punto en ese bloque, y

λ(v−1)=r(k−1),{\displaystyle \lambda (v-1)=r(k-1),}

Se obtiene contando, para un x fijo, 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, lo que prueba que la condición de que cualquier x en X esté contenido en r bloques es redundante y que r puede calcularse a partir de los demás parámetros.

Los valores resultantes de b y r deben ser 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 , que lleva el nombre del estadístico Ronald Fisher , establece que b  ≥ v en cualquier diseño 2-dimensional. 

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 arbitrariamente elegido de números igualmente o desigualmente espaciados, no hay elección de tal 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 balanceados esto puede ser posible. Muchos de estos casos se discuten en. [ 7 ] Sin embargo, también puede observarse trivialmente para los cuadrados mágicos o rectángulos mágicos que pueden verse como diseños de bloques incompletos parcialmente balanceados.

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). [ 8 ] Usando los símbolos 0 − 5, los bloques son las siguientes ternas:

012 013 024 035 045 125 134 145 234 235.                  

y la matriz de incidencia correspondiente (una matriz binaria v × b con suma de filas constante r y suma de columnas constante k ) es:

(111110000011000111001010010011010100101100101011100001110101){\displaystyle {\begin{pmatrix}1&1&1&1&1&0&0&0&0&0\\1&1&0&0&0&1&1&1&0&0\\1&0&1&0&0&1&0&0&1&1\\0&1&0&1&0&0&1&0&1&1\\0&0&1&0&1&0&1&1&1&0\\0&0&0&1&1&1&0&1&0&1\\\end{pmatrix}}}

Uno de los cuatro diseños no isomorfos (8,4,3) tiene 14 bloques con cada elemento repetido 7 veces. Usando los símbolos 0 − 7, los bloques son las siguientes 4-tuplas: [ 8 ]

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 las siguientes ternas: [ 8 ]

013 026 045 124 156 235 346.            

Este diseño está asociado al plano de Fano , cuyos elementos y bloques corresponden 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 correctamente.

(1110000100110010000110101010010010100110010010110){\displaystyle \left({\begin{matrix}1&1&1&0&0&0&0\\1&0&0&1&1&0&0\\1&0&0&0&0&1&1\\0&1&0&1&0&1&0\\0&1&0&0&1&0&1\\0&0&1&1&0&0&1\\0&0&1&0&1&1&0\end{matrix}}\right)}

Diseños simétricos de 2 componentes (SBIBD)

El caso de igualdad en la desigualdad de Fisher, es decir, un diseño 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 diseños 2 con el mismo número de puntos.

En un diseño simétrico, r = k se cumple, al igual que b = v , y, si bien generalmente no es cierto en diseños 2-arqueados arbitrarios, en un diseño simétrico, cada dos bloques distintos se encuentran en λ puntos. [ 10 ] Un teorema de Ryser proporciona el recíproco. Si X es un conjunto de v elementos y B es un conjunto de v elementos de subconjuntos de k elementos (los "bloques"), de tal manera que dos bloques distintos cualesquiera tienen exactamente λ puntos en común, entonces ( X, B ) es un diseño de bloques simétrico. [ 11 ]

Los parámetros de un diseño simétrico satisfacen

λ(v−1)=k(k−1).{\displaystyle \lambda (v-1)=k(k-1).}

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 función de estos parámetros.

Los siguientes son ejemplos importantes de diseños 2-simétricos:

Planos proyectivos

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étrico se convierte en:

v−1=k(k−1).{\displaystyle v-1=k(k-1).}

Dado que 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² + 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 líneas 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 ]

biplanos

Un biplano o geometría biplana 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 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.

  • (Trivial) El biplano de orden 0 tiene 2 puntos (y líneas de tamaño 2; un diseño 2-(2,2,2)); son dos puntos, con dos bloques, cada uno compuesto por ambos puntos. Geométricamente, es el digon .
  • El biplano de orden 1 tiene 4 puntos (y líneas de tamaño 3; un diseño 2-(4,3,2)); es el diseño completo con v = 4 y k = 3. Geométricamente, los puntos son los vértices de un tetraedro y los bloques son sus caras.
  • El biplano de orden 2 es el complemento del plano de Fano : tiene 7 puntos (y líneas de tamaño 4; un 2-(7,4,2)), donde las líneas se dan como los complementos de las líneas (de 3 puntos) en el plano de Fano. [ 14 ]
  • El biplano de orden 3 tiene 11 puntos (y líneas de tamaño 5; un 2-(11,5,2)), y también se conoce como elBiplano de Paley segúnRaymond Paley; está asociado aldigrafo de Paleyde orden 11, que se construye utilizando el campo con 11 elementos, y es el2-diseño de Hadamardasociado a la matriz de Hadamard de tamaño 12; véasela construcción de PaleyI.
Algebraicamente, esto corresponde a la incrustación excepcional del grupo lineal especial proyectivo PSL (2,5) en PSL (2,11) – véase grupo lineal proyectivo: acción sobre puntos p para más detalles. [ 15 ]
  • Hay tres biplanos de orden 4 (y 16 puntos, líneas de tamaño 6; un 2-(16,6,2)). Uno de ellos es la configuración de Kummer . Estos tres diseños son también diseños de Menon .
  • Hay cuatro biplanos de orden 7 (y 37 puntos, líneas de tamaño 9; un 2-(37,9,2)). [ 16 ]
  • Hay cinco biplanos de orden 9 (y 56 puntos, líneas de tamaño 11; un 2-(56,11,2)). [ 17 ]
  • Se conocen dos biplanos de orden 11 (y 79 puntos, líneas de tamaño 13; un 2-(79,13,2)). [ 18 ]

Los biplanos de órdenes 5, 6, 8 y 10 no existen, como lo demuestra el teorema de Bruck-Ryser-Chowla .

Hadamard 2 diseños

Una matriz de Hadamard de tamaño m es una matriz H de m × m cuyas entradas son ±1, de modo 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 puede transformarse en una forma estandarizada (es decir, convertirse en 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 4a 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-(4a − 1 , 2a − 1 , a − 1) llamado diseño Hadamard 2. [ 19 ] Contiene      4a−1{\displaystyle 4a-1}bloques/puntos; cada uno contiene/está contenido en2a−1{\displaystyle 2a-1}puntos/bloques. Cada par de puntos está contenido en exactamentea−1{\displaystyle a-1}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 .

Diseños 2-resolubles

Un diseño 2-resoluble es un BIBD cuyos bloques pueden particionarse 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 ]

Diseños equilibrados generales ( diseños t )

Dado cualquier entero positivo t , un diseño t - B es una clase de subconjuntos de k elementos de X , llamados bloques , tales que cada punto x en X aparece en exactamente r bloques, y cada subconjunto de t elementos T aparece en exactamente λ 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 diseño t- ( v , k , λ). Nuevamente, estos cuatro números determinan b y r , y los cuatro números en sí mismos no pueden elegirse arbitrariamente. Las ecuaciones son:

λi=λ(v−it−i)/(k−it−i) para i=0,1,…,t,{\displaystyle \lambda _{i}=\lambda \left.{\binom {v-i}{t-i}}\right/{\binom {k-i}{t-i}}{\text{ for }}i=0,1,\ldots ,t,}

donde λ i es el número de bloques que contienen cualquier conjunto de puntos de i elementos y λ t = λ.

Tenga en cuenta queb=λ0=λ(vt)/(kt){\displaystyle b=\lambda _{0}=\lambda {v \choose t}/{k \choose t}}yr=λ1=λ(v−1t−1)/(k−1t−1){\displaystyle r=\lambda _{1}=\lambda {v-1 \choose t-1}/{k-1 \choose t-1}}.

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 . (Nótese que el "valor lambda" cambia como se indicó anteriormente y depende de s .)   

Una consecuencia de este teorema es que todo t -diseño con t ≥ 2 es también un 2-diseño.

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.

Diseños t derivados y ampliables

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 extensión de D si E tiene un punto p tal que E p es isomorfo a D ; decimos que D es 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 ]      

Todo diseño de Hadamard 2 es extensible (a un diseño de 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:

  1. D es un diseño Hadamard 2,
  2. v  =  (λ  +  2)(λ 2  +  4λ  +  2), k  =  λ 2  +  3λ  +  1,
  3. v  =  495, k  =  39, λ  =  3.

Nótese que el plano proyectivo de orden dos es un diseño de Hadamard de orden 2; el plano proyectivo de orden cuatro tiene parámetros que corresponden al caso 2; los únicos otros diseños simétricos de orden 2 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 simétrico de orden 2 con los parámetros del caso 3. [ 28 ]

Planos inversos

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 inversivo 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² + 1 puntos, sin tres puntos colineales. Se puede demostrar que todo plano (que es un hiperplano, ya que la dimensión geométrica es 3) de PG(3, q ) interseca 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 denomina plano ovoide . Todos los planos inversos conocidos son planos ovoides.       

Un ejemplo de ovoide es la cuádrica elíptica , el conjunto de ceros de la forma cuadrática.

x 1 x 2 + f ( x 3 , x 4 ),

donde f es una forma cuadrática irreducible en dos variables sobre GF( q ) . [ f ( x , y ) = x² + xy + y² 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 tanto, q es una potencia de un número primo y hay un único plano inverso con forma de huevo de orden q . (Pero se desconoce si existen planos que no tengan forma de huevo). (b) Si q es par, entonces q es una potencia de 2 y cualquier plano inverso de orden q tiene forma de huevo (pero puede haber algunos ovoides desconocidos).

Diseños parcialmente equilibrados (PBIBD)

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 . Un par de elementos en la relación R i se denominan asociados i . Cada elemento de X tiene n asociados i . Además : 

  • R0={(incógnita,incógnita):incógnita∈incógnita}{\displaystyle R_{0}=\{(x,x):x\in X\}}y se denomina relación de identidad .
  • DefiniciónR∗:={(incógnita,y)∣(y,incógnita)∈R}{\displaystyle R^{*}:=\{(x,y)\mid (y,x)\in R\}}Si R está en S , entonces R* está en S.
  • Si(incógnita,y)∈Rk{\displaystyle (x,y)\in R_{k}}, el número dez∈incógnita{\displaystyle z\in X}de tal manera que(incógnita,z)∈Ri{\displaystyle (x,z)\in R_{i}}y(z,y)∈Rj{\displaystyle (z,y)\in R_{j}}es una constantepagijk{\displaystyle p_{ij}^{k}}dependiendo de i , j , k pero no de la elección particular de x e y .

Un esquema de asociación es conmutativo sipagijk=pagjik{\displaystyle p_{ij}^{k}=p_{ji}^{k}}para todo i , j y k . La mayoría de los autores asumen esta propiedad.

Un diseño de bloques incompleto parcialmente equilibrado con n clases asociadas (PBIBD( n )) es un diseño de bloques basado en un v -conjunto X con b bloques, cada uno de tamaño k y con cada elemento apareciendo en r bloques, de tal manera que hay un esquema de asociación con n clases definidas en X donde, si los elementos x e y son asociados i, 1 ≤ i ≤ n , entonces están juntos en precisamente λ i bloques.

Un PBIBD( n ) determina un esquema de asociación, pero lo contrario es falso. [ 29 ]

Ejemplo

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       

(111100001100110000111100101000110100101100010111){\displaystyle {\begin{pmatrix}1&1&1&1&0&0&0&0\\1&1&0&0&1&1&0&0\\0&0&1&1&1&1&0&0\\1&0&1&0&0&0&1&1\\0&1&0&0&1&0&1&1\\0&0&0&1&0&1&1&1\end{pmatrix}}}

y la matriz de concurrencia MM T es

(422211242121224112211422121242112224){\displaystyle {\begin{pmatrix}4&2&2&2&1&1\\2&4&2&1&2&1\\2&2&4&1&1&2\\2&1&1&4&2&2\\1&2&1&2&4&2\\1&1&2&2&2&4\\\end{pmatrix}}}

a partir de lo cual podemos recuperar los valores de λ y r .

Propiedades

Los parámetros de un PBIBD( m ) satisfacen: [ 31 ]

  1. vr=bk{\displaystyle vr=bk}
  2. ∑i=1metronortei=v−1{\displaystyle \sum _{i=1}^{m}n_{i}=v-1}
  3. ∑i=1metronorteiλi=r(k−1){\displaystyle \sum _{i=1}^{m}n_{i}\lambda _{i}=r(k-1)}
  4. ∑tú=0metropagjtúh=nortej{\displaystyle \sum _{u=0}^{m}p_{ju}^{h}=n_{j}}
  5. norteipagjhi=nortejpagihj{\displaystyle n_{i}p_{jh}^{i}=n_{j}p_{ih}^{j}}

Un PBIBD(1) es un BIBD y un PBIBD(2) en el que λ 1  = λ 2 es un BIBD. [ 32 ] 

Dos PBIBD de clase asociada

Los PBIBD(2) han sido los más estudiados ya que son los más simples y útiles de los PBIBD. [ 33 ] Se dividen en seis tipos [ 34 ] según una clasificación de los PBIBD(2) conocidos entonces por Bose y Shimamoto (1952) : [ 35 ]

  1. grupo divisible;
  2. triangular;
  3. tipo cuadrado latino;
  4. cíclico;
  5. tipo de geometría parcial;
  6. misceláneas.

Aplicaciones

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) . Este sigue siendo un ámbito importante para el uso de diseños de bloques.

Si bien los orígenes de la materia 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 correctores de errores . Las filas de sus matrices de incidencia también se utilizan como símbolos en una forma de modulación por posición de pulso . [ 36 ]

Aplicación estadística

Supongamos que investigadores del cáncer de piel quieren probar tres protectores solares diferentes. Aplican dos protectores solares distintos en el dorso de las manos de una persona de prueba. Tras la 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 design.bib del paquete agricolae de R , y se especifica en la siguiente tabla:

El investigador selecciona los parámetros v = 3 , k = 2 y λ = 1 para el diseño de bloques, los cuales 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 equilibrado. Etiquetando los bloques A , B y C , para evitar confusiones, tenemos el diseño de bloques,

A = {2, 3 }, B = {1, 3 } y C = {1, 2 }.  

En la siguiente tabla se especifica la matriz de incidencia correspondiente:

Cada tratamiento se realiza en 2 bloques, por lo que 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 lo tanto, λ = 1 .

En este ejemplo es imposible utilizar un diseño completo (todos los tratamientos en cada bloque) porque hay 3 protectores solares para probar, pero solo 2 manos por persona.

Véase también

Notas

  1. ^ Colbourn y Dinitz 2007 , págs.17-19
  2. ↑ Stinson 2003 , pág. 1
  3. ↑ P. Dobcsányi, DA Preece. LH Soicher (2007-10-01). "Sobre diseños de bloques incompletos equilibrados con bloques repetidos" . European Journal of Combinatorics . 28 (7): 1955– 1970. doi : 10.1016/j.ejc.2006.08.007 . ISSN 0195-6698 . 
  4. ↑ Demostrado por Tarry en 1900, quien mostró que no existía ningún par de cuadrados latinos ortogonales de sexto orden. El diseño 2 con los parámetros indicados es equivalente a la existencia de cinco cuadrados latinos mutuamente ortogonales de sexto orden.
  5. ↑ Khattree 2019
  6. ↑ Khattree 2022
  7. ↑ Khattree 2022
  8. ^ Colbourn y Dinitz 2007 , pág. 27
  9. ↑ 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 simétrico (en el sentido 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 v = b en la matriz de incidencia. Ninguno de los dos términos se ha popularizado como reemplazo y estos diseños todavía se denominan universalmente simétricos .
  10. ↑ Stinson 2003 , pág. 23, Teorema 2.2
  11. ^ Ryser 1963 , págs. 102-104
  12. 1 2 Hughes y Piper 1985 , pág. 109
  13. ↑ Hall 1986 , págs. 320-335
  14. ↑ Assmus y Key 1992 , pág. 55
  15. ↑ Martin, Pablo; Singerman, David (17 de abril de 2008), De los biplanos a la cuártica de Klein y el buckybola (PDF) , pág. 4 
  16. ↑ Salwach y Mezzaroba 1978
  17. ↑ Kaski y Östergård 2008
  18. ↑ Aschbacher 1971 , págs. 279–281
  19. ↑ Stinson 2003 , pág. 74, Teorema 4.5
  20. ↑ Hughes y Piper 1985 , pág. 156, Teorema 5.4
  21. ↑ Hughes y Piper 1985 , pág. 158, Corolario 5.5
  22. ↑ Beth, Jungnickel y Lenz 1986 , pág. 40 Ejemplo 5.8
  23. ↑ Stinson 2003 , pág. 203, Corolario 9.6
  24. ↑ Hughes y Piper 1985 , pág. 29
  25. ↑ Cameron y van Lint 1991 , pág. 11, Proposición 1.34
  26. ↑ Hughes y Piper 1985 , pág. 132, Teorema 4.5
  27. ↑ Cameron y van Lint 1991 , pág. 11, Teorema 1.35
  28. ↑ Colbourn y Dinitz 2007 , pág. 114, Observaciones 6.35
  29. ↑ Street & Street 1987 , pág. 237
  30. ↑ Street & Street 1987 , pág. 238
  31. ↑ Street & Street 1987 , pág. 240, Lema 4
  32. ^ Colbourn y Dinitz 2007 , pág. 562, Observación 42.3 (4)
  33. ↑ Street & Street 1987 , pág. 242
  34. ↑ No es una clasificación matemática ya que uno de los tipos es un cajón de sastre "y todo lo demás".
  35. ↑ Raghavarao 1988 , pág. 127
  36. ↑ Noshad, Mohammad; Brandt-Pearce, Maïté (julio de 2012). "PPM depurado mediante diseños de bloques incompletos equilibrados simétricos". IEEE Communications Letters . 16 (7): 968– 971. arXiv : 1203.5378 . Bibcode : 2012arXiv1203.5378N . doi : 10.1109/LCOMM.2012.042512.120457 . S2CID 7586742 . 

Referencias

  • Aschbacher, Michael (1971). "Sobre grupos de colineación de diseños de bloques simétricos" . Journal of Combinatorial Theory . Serie A. 11 (3): 272– 281. doi : 10.1016/0097-3165(71)90054-9 .
  • Assmus, EF; Key, JD (1992), Diseños y sus códigos , Cambridge: Cambridge University Press, ISBN 0-521-41361-3
  • Beth, Thomas; Jungnickel, Dieter ; Lenz, Hanfried (1986), Teoría del diseño , Cambridge University Press2.ª ed. (1999) ISBN 978-0-521-44432-3.
  • Bose, RC (1949), "Una nota sobre la desigualdad de Fisher para diseños de bloques incompletos equilibrados", Annals of Mathematical Statistics , 20 (4): 619– 620, doi : 10.1214/aoms/1177729958
  • Bose, R.  C.; Shimamoto, T. (1952), "Clasificación y análisis de diseños de bloques incompletos parcialmente equilibrados con dos clases asociadas", Journal of the American Statistical Association , 47 (258): 151–184 , doi : 10.1080/01621459.1952.10501161
  • Cameron, PJ; van Lint, JH (1991), Diseños, gráficos, códigos y sus vínculos , Cambridge University Press, ISBN 0-521-42385-6
  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2.ª  ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 978-1-58488-506-1
  • Fisher, RA (1940), "Un examen de las diferentes soluciones posibles de un problema en bloques incompletos", Annals of Eugenics , 10 : 52–75 , doi : 10.1111/j.1469-1809.1940.tb02237.x , hdl : 2440/15239
  • Hall, Marshall Jr. (1986), Teoría combinatoria (2.ª  ed.), Nueva York: Wiley-Interscience, ISBN 0-471-09138-3
  • Hughes, DR; Piper, EC (1985), Teoría del diseño , Cambridge: Cambridge University Press, ISBN 0-521-25754-9
  • Kaski, Petteri; Östergård, Patric (2008). "Hay exactamente cinco biplanos con k = 11". Journal of Combinatorial Designs . 16 (2): 117– 127. doi : 10.1002/jcd.20145 . MR 2384014. S2CID 120721016 .  
  • Lander, ES (1983), Diseños simétricos: un enfoque algebraico , Cambridge University Press, ISBN 978-0-521-28693-0
  • Lindner, CC; Rodger, CA (1997), Teoría del diseño , Boca Raton: CRC Press, ISBN 0-8493-3986-3
  • Raghavarao, Damaraju (1988). Construcciones y problemas combinatorios en el diseño de experimentos . Dover. ISBN 978-0-486-65685-4.
  • Raghavarao, Damaraju ; Padgett, LV (11 de octubre de 2005). Diseños de bloques: análisis, combinatoria y aplicaciones . World Scientific. ISBN 978-981-4480-23-9.
  • Ryser, Herbert John (1963), "8. Diseños combinatorios" , Matemáticas combinatorias , Carus Mathematical Monographs, vol.  14, Mathematical Association of America, pp. 96–130 , ISBN  978-1-61444-014-7{{citation}}: Incompatibilidad de ISBN/Fecha ( ayuda )
  • Salwach, Chester J.; Mezzaroba, Joseph A. (1978). "Los cuatro biplanos con k = 9" . Journal of Combinatorial Theory . Serie A. 24 (2): 141– 145. doi : 10.1016/0097-3165(78)90002-X .
  • Khattree, Ravindra (2019). "A note on the nonexistence of the constant block-sum balanced incomplete block designs". Communications in Statistics - Theory and Methods. 48 (20): 5165–5168. doi:10.1080/03610926.2018.1508715. S2CID 125795689.
  • Khattree, Ravindra (2022). "On construction of equireplicated constant block-sum designs". Communications in Statistics - Theory and Methods. 51 (2): 4434–4450. doi:10.1080/03610926.2020.1814816. S2CID 225335042.
  • Shrikhande, S.S.; Bhat-Nayak, Vasanti N. (1970), "Non-isomorphic solutions of some balanced incomplete block designs I", Journal of Combinatorial Theory, 9 (2): 174–191, doi:10.1016/S0021-9800(70)80024-2
  • Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, Springer, ISBN 0-387-95487-2
  • Street, Anne Penfold & Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. ISBN 0-19-853256-3.
  • van Lint, J.H.; Wilson, R.M. (1992). A Course in Combinatorics. Cambridge University Press. ISBN 978-0-521-41057-1.
  • DesignTheory.Org: Databases of combinatorial, statistical, and experimental block designs. Software and other resources hosted by the School of Mathematical Sciences at Queen Mary College, University of London.
  • Design Theory Resources: Peter Cameron's page of web based design theory resources.
  • Weisstein, Eric W."Block Designs". MathWorld.