Diseño combinatorio

La teoría del diseño combinatorio es la rama de las matemáticas combinatorias que se ocupa de la existencia, construcción y propiedades de sistemas de conjuntos finitos cuyas disposiciones satisfacen conceptos generalizados de equilibrio y/o simetría . Estos conceptos no se definen con precisión, de modo que una amplia gama de objetos puede considerarse bajo el mismo paraguas. En ocasiones, esto puede implicar el tamaño numérico de las intersecciones de conjuntos, como en los diseños de bloques , mientras que en otras ocasiones podría implicar la disposición espacial de las entradas en una matriz, como en las cuadrículas de sudoku .

La teoría del diseño combinatorio puede aplicarse al área del diseño de experimentos . Parte de la teoría básica de los diseños combinatorios se originó en el trabajo del estadístico Ronald Fisher sobre el diseño de experimentos biológicos. También se encuentran aplicaciones modernas en una amplia gama de áreas, que incluyen geometría finita , programación de torneos , loterías , química matemática , biología matemática , diseño y análisis de algoritmos , redes , pruebas grupales y criptografía . ^{[ 1 ]}

Dado un número n de personas, ¿es posible asignarlas a conjuntos de manera que cada persona esté en al menos un conjunto, cada par de personas esté en exactamente un conjunto, cada dos conjuntos tengan exactamente una persona en común, y ningún conjunto contenga a todas las personas, a todas menos a una, o a exactamente una persona? La respuesta depende de n .

Esto solo tiene solución si n tiene la forma q² ⁺ q + 1. Es menos sencillo demostrar que existe una solución si q es una potencia prima . Se conjetura que estas son las únicas soluciones. Se ha demostrado además que si existe una solución para q congruente con 1 o 2 mod 4, entonces q es una suma de dos números cuadrados . Este último resultado, el teorema de Bruck-Ryser , se demuestra mediante una combinación de métodos constructivos basados ​​en cuerpos finitos y una aplicación de formas cuadráticas .

Cuando existe tal estructura, se la denomina plano proyectivo finito ; mostrando así la intersección entre la geometría finita y la combinatoria. Cuando q  =  2, el plano proyectivo se denomina plano de Fano .

Los diseños combinatorios se remontan a la antigüedad, siendo el cuadrado Lo Shu un ejemplo temprano de cuadrado mágico . Una de las primeras aplicaciones datables del diseño combinatorio se encuentra en la India, en el libro Brhat Samhita de Varahamihira, escrito alrededor del año 587 d. C., con el propósito de elaborar perfumes utilizando 4 sustancias seleccionadas de entre 16 sustancias diferentes mediante un cuadrado mágico. ^{[ 2 ]}

Los diseños combinatorios se desarrollaron paralelamente al crecimiento general de la combinatoria desde el siglo XVIII, por ejemplo, con los cuadrados latinos en el siglo XVIII y los sistemas de Steiner en el siglo XIX. Los diseños también han sido populares en matemáticas recreativas , como el problema de la colegiala de Kirkman (1850), y en problemas prácticos, como la programación de torneos de todos contra todos (solución publicada en la década de 1880). En el siglo XX, los diseños se aplicaron al diseño de experimentos , en particular los cuadrados latinos, la geometría finita y los esquemas de asociación , dando lugar al campo de la estadística algebraica .

El núcleo clásico del tema de los diseños combinatorios se basa en los diseños de bloques incompletos equilibrados (BIBD) , las matrices y diseños de Hadamard , los BIBD simétricos , los cuadrados latinos , los BIBD resolubles , los conjuntos de diferencias y los diseños equilibrados por pares (PBD). ^{[ 3 ]} Otros diseños combinatorios están relacionados con estos fundamentales o se han desarrollado a partir de su estudio.

• Un diseño de bloques incompleto equilibrado o BIBD (generalmente llamado simplemente diseño de bloques ) es una colección B de b subconjuntos (llamados bloques ) de un conjunto finito X de v elementos, de tal manera que cualquier elemento de X está contenido en el mismo número r de bloques, cada bloque tiene el mismo número k de elementos, y cada par de elementos distintos aparece junto en el mismo número λ de bloques. Los BIBD también se conocen como 2-diseños y a menudo se denotan como diseños 2-( v , k , λ). Como ejemplo, cuando λ = 1 y b = v , tenemos un plano proyectivo : X es el conjunto de puntos del plano y los bloques son las líneas.
• Un diseño de bloques incompletos simétricos y equilibrados ( SBIBD) es un BIBD en el que v  = b (el número de puntos es igual al número de bloques). Son la subclase de BIBD más importante y estudiada. Los planos proyectivos, los biplanos y los diseños de Hadamard de orden 2 son todos SBIBD. Son de particular interés, ya que son los ejemplos extremos de la desigualdad de Fisher ( b ≥ v ). 
• Un BIBD 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. Una solución del famoso problema de las 15 colegialas es una resolución de un BIBD con v  =  15, k  =  3 y λ  =  1. ^{[ 4 ]}
• Un rectángulo latino es una matriz r  × n que tiene como entradas los números 1, 2, 3, ..., n (o cualquier otro conjunto de n símbolos distintos), sin que ningún número aparezca más de una vez en ninguna fila o columna donde r ≤ n . Un rectángulo latino n × n se denomina cuadrado latino . Si r < n , entonces es posible añadir n − r filas a un rectángulo latino r × n para formar un cuadrado latino, utilizando el teorema de matrimonio de Hall . ^{[ 5 ]}                

Dos cuadrados latinos de orden n se consideran ortogonales si el conjunto de todos los pares ordenados formados por las entradas correspondientes de ambos cuadrados tiene n² elementos distintos ( ^es decir, se dan todos los pares ordenados posibles). Un conjunto de cuadrados latinos del mismo orden forma un conjunto de cuadrados latinos mutuamente ortogonales (MOLS) si cada par de cuadrados latinos del conjunto es ortogonal. Un conjunto de MOLS de orden n puede contener como máximo n  − 1 cuadrados . Un conjunto de n − 1 MOLS de orden n puede utilizarse para construir un plano proyectivo de orden n (y viceversa).   

• Un conjunto de diferencias ₍ v , k , λ ) es un subconjunto D de un grupo G tal que el _orden de G es v , el tamaño de D es k , y cada elemento distinto de la identidad de G puede expresarse como un producto ^{d₁d₂⁻¹} de elementos de D de exactamente λ maneras (cuando G se escribe con una operación multiplicativa). ^{[ 6 ]}

Si D es un conjunto de diferencias y g pertenece a G , entonces g D  =  { gd : d pertenece a D } también es un conjunto de diferencias y se denomina traslación de D. El conjunto de todas las traslaciones de un conjunto de diferencias D forma un BIBD simétrico . En dicho diseño hay v elementos y v bloques. Cada bloque del diseño consta de k puntos, ^y cada punto está contenido en k bloques. Dos bloques cualesquiera tienen exactamente λ elementos en común y dos puntos cualesquiera aparecen juntos en λ bloques. Este SBIBD se denomina desarrollo de D. [ ^{7 ]}

En particular, si λ = 1, entonces el conjunto diferencia da lugar a un plano proyectivo . Un ejemplo de un conjunto diferencia (7,3,1) en el grupo${\displaystyle \mathbb {Z} /7\mathbb {Z} }$(un grupo abeliano escrito aditivamente) es el subconjunto {1,2,4}. El desarrollo de este conjunto de diferencias da el plano de Fano .

Dado que cada conjunto de diferencias produce un SBIBD, el conjunto de parámetros debe satisfacer el teorema de Bruck-Ryser-Chowla , pero no todos los SBIBD producen un conjunto de diferencias.

• Una matriz de Hadamard de orden 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 orden m > 2, entonces m debe ser un múltiplo de 4.        

Dada una matriz de Hadamard de orden 4a en forma estandarizada, se eliminan la primera fila y la primera columna, y se convierte cada -1 en un 0. La matriz resultante de 0-1, M, es la matriz de incidencia de un diseño simétrico 2-(4a -  1  , 2a -  1  , a  -  1) llamado diseño de Hadamard 2. ^{[ 8} ] Esta construcción es reversible, y la matriz de incidencia de un diseño simétrico 2 con estos parámetros puede usarse para formar una matriz de Hadamard de orden 4a ^. Cuando a =  2  , obtenemos el plano de Fano , ya conocido, como un diseño de Hadamard 2.

• Un diseño equilibrado por pares (o PBD) es un conjunto X junto con una familia de subconjuntos de X (que no necesariamente tienen el mismo tamaño y pueden contener repeticiones) de tal manera que cada par de elementos distintos de X está contenido en exactamente λ (un entero positivo) subconjuntos. El conjunto X puede ser uno de los subconjuntos, y si todos los subconjuntos son copias de X , el PBD se denomina trivial . El tamaño de X es v y el número de subconjuntos en la familia (contado con multiplicidad) es b . 

La desigualdad de Fisher se cumple para los PBD: ^{[ 9 ]} Para cualquier PBD no trivial, v  ≤ b . 

Este resultado también generaliza el famoso teorema de Erdős-De Bruijn : Para un PBD con λ  =  1 que no tiene bloques de tamaño 1 o tamaño v , v ≤ b , con igualdad si y solo si el PBD es un plano proyectivo o un casi lápiz. ^{[ 10 ]}   

El Manual de Diseños Combinatorios ( Colbourn y Dinitz, 2007 ) contiene, entre otros, 65 capítulos, cada uno dedicado a un diseño combinatorio distinto de los mencionados anteriormente. A continuación se presenta una lista parcial:

• Planes de asociación
• Un diseño ternario equilibrado BTD( V , B ; ρ ₁ , ρ ₂ , R ; K , Λ) es una disposición de V elementos en B multiconjuntos (bloques), cada uno de cardinalidad K ( K ≤ V ), que satisface:

1. Cada elemento aparece R = ρ ₁ + 2 ρ ₂ veces en total, con multiplicidad uno en exactamente ρ ₁ bloques y multiplicidad dos en exactamente ρ ₂ bloques.
2. Cada par de elementos distintos aparece Λ veces (contado con multiplicidad); es decir, si m _vb es la multiplicidad del elemento v en el bloque b , entonces para cada par de elementos distintos v y w ,${\displaystyle \sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda }$.

Por ejemplo, uno de los dos únicos BTD(4,8;2,3,8;4,6) no isomorfos (los bloques son columnas) es: ^{[ 11 ]}

La matriz de incidencia de un BTD (donde las entradas son las multiplicidades de los elementos en los bloques) se puede utilizar para formar un código corrector de errores ternario análogo a la forma en que se forman los códigos binarios a partir de las matrices de incidencia de los BIBD. ^{[ 12 ]}

• AEl diseño de torneo equilibrado de ordenn(un BTD(n)) es una disposición de todos los pares no ordenados distintos de unconjuntoVelementosen unade n×(2n−1) tal que    

1. cada elemento de V aparece exactamente una vez en cada columna, y
2. Cada elemento de V aparece como máximo dos veces en cada fila.

Un ejemplo de BTD(3) se da por

Las columnas de un BTD( n ) proporcionan una 1-factorización del ^grafo completo en 2n _vértices , K2n . ^[ ₁₃ ^]

Los BTD( n ) se pueden utilizar para programar torneos de todos contra todos : las filas representan las ubicaciones, las columnas las rondas de juego y las entradas son los jugadores o equipos que compiten.

• Funciones dobladas
• arreglos de Costas
• Diseños de cobertura
• Diseños factoriales
• Un cuadrado de frecuencias ₍ cuadrado F ) es una generalización de orden superior de un cuadrado latino . Sea S = { s₁ , s₂ _, ... , sₙ _} un conjunto de símbolos distintos y ( λ₁ _, λ₂ _, ..., λₙ ₎ un vector de frecuencias de enteros positivos. Un cuadrado de frecuencias de orden n es una matriz n × n en la que cada símbolo sᵢ _aparece λᵢ veces, i = _{1 ,} 2, ..., m , en cada fila y columna. El orden n = λ₁ ₊ λ₂ + ... + λₙ . Un cuadrado F está en forma estándar si en la primera fila y columna, todas las ocurrencias de sᵢ preceden a las de _sⱼ siempre _que i < _j .        

Un cuadrado de frecuencia F ₁ de orden n basado en el conjunto { s ₁ , s ₂ , ..., s _m } con vector de frecuencia ( λ ₁ , λ ₂ , ..., λ _m ) y un cuadrado de frecuencia F ₂ , también de orden n , basado en el conjunto { t ₁ , t ₂ , ..., t _k } con vector de frecuencia ( μ ₁ , μ ₂ , ..., μ _k ) son ortogonales si cada par ordenado ( s _i , t _j ) aparece precisamente λ _i μ _j veces cuando F ₁ y F ₂ se superponen.

• Los sistemas triples de Hall (HTS) son sistemas triples de Steiner (STS) (pero los bloques se llaman líneas ) con la propiedad de que la subestructura generada por dos líneas que se intersecan es isomorfa al plano afín finito AG(2,3).

Cualquier espacio afín AG( n ,3) constituye un ejemplo de HTS. Dicho HTS es un HTS afín . También existen HTS no afines.

El número de puntos de un HTS es 3 ^m para algún entero m  ≥  2. Los HTS no afines existen para cualquier m  ≥  4 y no existen para m  =  2 o 3. ^{[ 14 ]}

Todo sistema triple de Steiner es equivalente a un cuasigrupo de Steiner ( idempotente , conmutativo y que satisface ( xy ) y  = x para todo x e y ). Un sistema triple de Hall es equivalente a un cuasigrupo de Steiner que es distributivo , es decir, satisface a ( xy ) = ( ax )( ay ) para todo a , x , y en el cuasigrupo. ^{[ 15 ]} 

• Sea S un conjunto de 2n elementos . Un diseño de Howell , H( s , 2n ) (sobre el conjunto de símbolos S ), es una matriz de s × s tal que:

1. Cada celda de la matriz está vacía o contiene un par no ordenado de S ,
2. Cada símbolo aparece exactamente una vez en cada fila y columna de la matriz, y
3. Cada par de símbolos no ordenados aparece como máximo en una celda de la matriz.

Un ejemplo de H (4,6) es

Un H(2 n  −  1, 2 n ) es un cuadrado de Room de lado 2 n  −  1, y por lo tanto los diseños de Howell generalizan el concepto de cuadrados de Room.

Los pares de símbolos en las celdas de un diseño de Howell pueden considerarse como las aristas de un grafo regular s con 2 n vértices, llamado grafo subyacente del diseño de Howell.

Los diseños cíclicos de Howell se utilizan como movimientos de Howell en torneos de bridge duplicado. Las filas del diseño representan las rondas, las columnas representan los tableros y las diagonales representan las mesas. ^{[ 16 ]}

• Espacios lineales
• Un diseño de lotería ( n , k , p , t ) es un conjunto V de n elementos junto con un conjunto β de subconjuntos de V de k elementos (bloques), de modo que para cualquier subconjunto P de V de p elementos , existe un bloque B en β tal que |P ∩ B| ≥ t . L( n , k , p , t ) denota el número más pequeño de bloques en cualquier diseño de lotería ( n , k , p , t ). El siguiente es un diseño de lotería (7,5,4,3) con el número más pequeño posible de bloques: ^{[ 17 ]}

{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}.      

Los modelos de diseño de lotería simulan cualquier lotería que se ejecute de la siguiente manera: Los participantes compran boletos que constan de k números elegidos de un conjunto de n números. En un momento dado, se detiene la venta de boletos y se selecciona aleatoriamente un conjunto de p números de los n números. Estos son los números ganadores . Si algún boleto vendido contiene t o más números ganadores, se otorga un premio al poseedor del boleto. Los premios mayores se otorgan a los boletos con mayor número de aciertos. El valor de L( n , k , p , t ) es de interés tanto para los jugadores como para los investigadores, ya que representa la cantidad mínima de boletos que se deben comprar para garantizar un premio.

La lotería húngara es un diseño de lotería (90,5,5, t ) y se sabe que L(90,5,5,2) = 100. Las loterías con parámetros (49,6,6, t ) también son populares en todo el mundo y se sabe que L(49,6,6,2) = 19. Sin embargo, en general, estos números son difíciles de calcular y permanecen desconocidos. ^{[ 18 ]}

En la lotería de Transilvania se ofrece una construcción geométrica de uno de esos diseños .

• cuadrados mágicos
• Un diseño de Mendelsohn ( v , k , λ ) , o MD( v , k , λ ), es un conjunto V de v elementos y una colección β de k- tuplas ordenadas de elementos distintos de V (llamadas bloques ), de tal manera que cada par ordenado ( x , y ) con x ≠ y de elementos de V es cíclicamente adyacente en λ bloques. El par ordenado ( x , y ) de elementos distintos es cíclicamente adyacente en un bloque si los elementos aparecen en el bloque como (..., x , y , ...) o ( y , ..., x ). Un MD( v , 3, λ ) es un sistema triple de Mendelsohn , MTS( v , λ ). Un ejemplo de un MTS(4,1) en V = {0, 1, 2, 3} es:

(0,1,2) (1,0,3) (2,1,3) (0,2,3)      

Cualquier sistema triple puede convertirse en un sistema triple de Mendelson reemplazando el triple no ordenado { a , b , c } con el par de triples ordenados ( a , b , c ) y ( a , c , b ), pero como muestra el ejemplo, lo contrario de esta afirmación no es cierto.

Si ( Q ,∗) es un cuasigrupo semisimétrico idempotente , es decir, x ∗ x = x (idempotente) y x ∗ ( y ∗ x ) = y (semisimétrico) para todo x , y en Q , sea β = {( x , y , x ∗ y ): x , y en Q }. Entonces ( Q , β) es un sistema triple de Mendelsohn MTS(| Q |,1). Esta construcción es reversible. ^{[ 19 ]}

• matrices ortogonales
• Diseños de embalaje
• Un diseño cuasi-3 es un diseño simétrico (SBIBD) en el que cada triplete de bloques se interseca en los puntos x o y , para valores fijos de x e y, denominados números de intersección triple ( x < y ). Cualquier diseño simétrico con λ ≤ 2 es un diseño cuasi-3 con x  =  0 e y  =  1. El diseño punto-hiperplano de PG ( n , q ) es un diseño cuasi-3 con x  =  ( q ^{n −2}  −  1)/( q  −  1) e y  = λ = ( q ^{n −1} − 1)/( q − 1). Si y = λ para un diseño cuasi-3, el diseño es isomorfo a PG ( n , q ) o a un plano proyectivo . ^{[ 20 ]}         
• Un diseño t- ( v , k , λ ) D es cuasi-simétrico con números de intersección x e y ( x < y ) si cada dos bloques distintos se intersecan en los puntos x o y . Estos diseños surgen naturalmente en la investigación de los duales de diseños con λ = 1. Un diseño 2-( v , k , 1) no simétrico ( b > v ) es cuasi-simétrico con x = 0 e y = 1. Un múltiplo (repite todos los bloques un cierto número de veces) de un diseño 2-( v , k , λ ) simétrico es cuasi-simétrico con x = λ e y = k . Los 3-diseños de Hadamard (extensiones de los 2-diseños de Hadamard ) son cuasi-simétricos. ^{[ 21 ]}

Todo diseño de bloques cuasi-simétrico da lugar a un grafo fuertemente regular (como su grafo de bloques), pero no todos los SRG surgen de esta manera. ^{[ 22 ]}

La matriz de incidencia de un diseño cuasisimétrico 2-( v , k , λ ) con k ≡ x ≡ y (mod 2) genera un código binario autoortogonal (cuando está bordeado si k es impar). ^{[ 23 ]}

• Cuadrados de habitación
• Un diseño esférico es un conjunto finito X de puntos en una esfera ( d  −  1)-dimensional tal que, para algún entero t , el valor promedio en X de cada polinomio

${\displaystyle f(x_{1},\ldots ,x_{d})\ }$

de grado total como máximo t es igual al valor promedio de f en toda la esfera, es decir, la integral de f dividida por el área de la esfera.

• Sistemas de Turán
• Un rectángulo toscano -k de r × n sobre n símbolos tiene r filas y n columnas tales que:

1. cada fila es una permutación de los n símbolos y
2. para cualesquiera dos símbolos distintos a y b y para cada m de 1 a k , hay como máximo una fila en la que b está m pasos a la derecha de a .

Si r = n y k = 1, se denominan cuadrados toscanos , mientras que si r = n y k = n − 1, son cuadrados florentinos . Un cuadrado romano es un cuadrado toscano que también es un cuadrado latino (también conocidos como cuadrados latinos completos por filas ). Un cuadrado vaticano es un cuadrado florentino que también es un cuadrado latino.

El siguiente ejemplo es un cuadrado toscano-1 en 7 símbolos que no es toscano-2: ^{[ 24 ]}

Un cuadrado toscano sobre n símbolos es equivalente a una descomposición del grafo completo con n vértices en n caminos dirigidos hamiltonianos. ^{[ 25 ]}

En una secuencia de impresiones visuales, una tarjeta puede tener algún efecto sobre la impresión que produce la siguiente. Este sesgo se puede anular utilizando n secuencias que correspondan a las filas de un cuadrado toscano-1 de n × n . ^{[ 26 ]}

• Un diseño equilibrado t-dimensional (o t BD) de tipo t  −  ( v ,K, λ ) es un v -conjunto X junto con una familia de subconjuntos de X (llamados bloques ) cuyos tamaños están en el conjunto K, de tal manera que cada t -subconjunto de elementos distintos de X está contenido en exactamente λ bloques. Si K es un conjunto de enteros positivos estrictamente entre t y v , entonces el t BD es propio . Si todos los k -subconjuntos de X para algún k son bloques, el t BD es un diseño trivial . ^{[ 27 ]}

Observe que en el siguiente ejemplo de un 3-{12,{4,6},1) diseño basado en el conjunto X = {1,2,...,12}, algunos pares aparecen cuatro veces (como 1,2) mientras que otros aparecen cinco veces (6,12 por ejemplo). ^{[ 28 ]}

1 2 3 4 5 6 1 2 7 8 1 2 9 11 1 2 10 12 3 5 7 8 3 5 9 11 3 5 10 12 4 6 7 8 4 6 9 11 4 6 10 12                                         

7 8 9 10 11 12 2 3 8 9 2 3 10 7 2 3 11 12 4 1 8 9 4 1 10 7 4 1 11 12 5 6 8 9 5 6 10 7 5 6 11 12                                    

                         3 4 9 10 3 4 11 8 3 4 7 12 5 2 9 10 5 2 11 8 5 2 7 12 1 6 9 10 1 6 11 8 1 6 7 12                                

                         4 5 10 11 4 5 7 9 4 5 8 12 1 3 10 11 1 3 7 9 1 3 8 12 2 6 10 11 2 6 7 9 2 6 8 12                                

                         5 1 11 7 5 1 8 10 5 1 9 12 2 4 11 7 2 4 8 10 2 4 9 12 3 6 11 7 3 6 8 10 3 6 9 12                                

• Las matrices de ponderación , una generalización de las matrices de Hadamard que permite entradas cero, se utilizan en algunos diseños combinatorios. En particular, en el diseño de experimentos para estimar los pesos individuales de múltiples objetos en pocos ensayos. ^{[ 29 ]}
• Un cuadrado de Youden es una matriz rectangular de k × v ( k < v ) de v símbolos, de modo que cada símbolo aparece exactamente una vez en cada fila y los símbolos que aparecen en cualquier columna forman un bloque de un diseño simétrico ( v , k , λ ), cuyos bloques se presentan de esta manera. Un cuadrado de Youden es un rectángulo latino. El término "cuadrado" en el nombre proviene de una definición anterior que sí utilizaba una matriz cuadrada. ^{[ 30 ]} Un ejemplo de un cuadrado de Youden de 4 × 7 se da a continuación:

Los siete bloques (columnas) forman el biplano de orden 2 (un diseño simétrico (7,4,2)).

• estadística algebraica
• Hipergrafo
• Conjetura de Williamson