La teoría del diseño combinatorio es la parte 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 precisan de modo que se pueda considerar que una amplia gama de objetos están bajo el mismo paraguas. En ocasiones, esto podría implicar los tamaños numéricos de intersecciones establecidas, 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 .
Dado un cierto número n de personas, ¿es posible asignarlas a conjuntos de modo que cada persona esté en al menos un conjunto, cada par de personas esté exactamente en un conjunto, cada dos conjuntos tengan exactamente una persona en común y no ¿El conjunto contiene a todos, a todos menos a uno o exactamente a uno? La respuesta depende de n .
Esto tiene solución sólo si n tiene la forma q 2 + q + 1. Es menos sencillo demostrar que existe una solución si q es una potencia prima . Se conjetura que éstas 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 tal estructura existe, se le llama plano proyectivo finito ; mostrando así cómo se cruzan la geometría finita y la combinatoria. Cuando q = 2, el plano proyectivo se denomina plano de Fano .
Historia
Los diseños combinatorios datan de la antigüedad, siendo el cuadrado Lo Shu uno de los primeros cuadrados mágicos . 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 587 d.C., con el propósito de elaborar perfumes utilizando 4 sustancias seleccionadas entre 16 sustancias diferentes utilizando un cuadrado mágico. [2]
Un diseño de bloques incompletos balanceados o BIBD (generalmente llamado para abreviar diseño de bloques ) es una colección B de b subconjuntos (llamados bloques ) de un conjunto finito X de v elementos, tal 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 aparecen juntos en el mismo número λ de bloques. Los BIBD también se conocen como diseños 2 y, a menudo, se denominan 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 rectas.
Un diseño de bloques incompletos equilibrados simétricos o 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 mejor estudiada. Los aviones proyectivos, los biplanos y los diseños de Hadamard 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 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. Una solución del famoso problema de las 15 colegialas es la resolución de un BIBD con v = 15, k = 3 y λ = 1. [4]
Un rectángulo latino es una matriz r × n que tiene los números 1, 2, 3, ..., n como entradas (o cualquier otro conjunto de n símbolos distintos) sin que ningún número aparezca más de una vez en cualquier fila o columna donde r ≤ norte . Un rectángulo latino de n × n se llama cuadrado latino . Si r < n , entonces es posible agregar n − r filas a un rectángulo latino r × n para formar un cuadrado latino, usando el teorema de matrimonio de Hall . [5]
Se dice que dos cuadrados latinos de orden n son ortogonales si el conjunto de todos los pares ordenados que consta de las entradas correspondientes en los dos cuadrados tiene n 2 miembros distintos (se producen 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 son ortogonales. Puede haber como máximo n − 1 cuadrados en un conjunto de MOLS de orden n . Se puede utilizar un conjunto de n − 1 MOLS de orden n 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 no idéntico de G se puede expresar como un producto d 1 d 2 −1 de elementos de D exactamente en λ formas (cuando G se escribe con una operación multiplicativa). [6]
Si D es un conjunto de diferencias y g en G , entonces g D = { gd : d in D } también es un conjunto de diferencias y se denomina traducción de D. El conjunto de todas las traslaciones de un conjunto de diferencias D forma un diseño de bloque simétrico . En tal diseño hay v elementos y v bloques. Cada bloque del diseño consta de k puntos, 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 llama desarrollo de D. [7]
En particular, si λ = 1, entonces el conjunto diferencia da lugar a un plano proyectivo . Un ejemplo de un conjunto de diferencias (7,3,1) en el grupo (un grupo abeliano escrito de forma aditiva) es el subconjunto {1,2,4}. El desarrollo de este conjunto diferencial lo da el avión Fano .
Dado que cada conjunto de diferencias da un SBIBD, el conjunto de parámetros debe satisfacer el teorema de Bruck-Ryser-Chowla , pero no todo SBIBD da un conjunto de diferencias.
Una matriz de Hadamard de orden 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 orden m > 2 entonces m debe ser múltiplo de 4.
Dada una matriz de Hadamard de orden 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 un simétrico 2 − (4 a − 1, 2 a − 1, a − 1) diseño llamado diseño Hadamard 2 . [8] 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 orden 4 a . Cuando a = 2 obtenemos el ya conocido plano de Fano como diseño de Hadamard 2.
Un diseño balanceado por pares (o PBD) es un conjunto X junto con una familia de subconjuntos de X (que no necesitan tener el mismo tamaño y pueden contener repeticiones) tal que cada par de elementos distintos de X está contenido exactamente en λ (un diseño positivo). entero) subconjuntos. Se permite que el conjunto X sea uno de los subconjuntos, y si todos los subconjuntos son copias de X , el PBD se llama trivial . El tamaño de X es v y el número de subconjuntos de la familia (contados con multiplicidad) es 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 lápiz cercano. . [10]
Otros diseños combinatorios
El Handbook of Combinatorial Designs (Colbourn & Dinitz 2007) tiene, entre otros, 65 capítulos, cada uno de ellos dedicado a un diseño combinatorio distinto de los mencionados anteriormente. A continuación se proporciona una lista parcial:
Un diseño ternario equilibrado BTD ( V , B ; ρ 1 , ρ 2 , R ; K , Λ) es una disposición de V elementos en B multiconjuntos (bloques), cada uno de cardinalidad K ( K ≤ V ), que satisface:
Cada elemento aparece R = ρ 1 + 2 ρ 2 veces en total, con multiplicidad uno en exactamente ρ 1 bloques y multiplicidad dos en exactamente ρ 2 bloques.
Cada par de elementos distintos aparece Λ veces (contadas 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 , .
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 ternario de corrección de errores análogo a la forma en que se forman los códigos binarios a partir de las matrices de incidencia de BIBD. [12]
AEl diseño de torneo equilibrado de ordenn(un BTD (n)) es una disposición de todos los pares desordenados distintos de unconjuntoVnen unan × (2n − 1) tal que
cada elemento de V aparece precisamente una vez en cada columna, y
cada elemento de V aparece como máximo dos veces en cada fila.
Un ejemplo de BTD(3) viene dado por
Las columnas de un BTD( n ) proporcionan una factorización 1 del gráfico completo en 2 n vértices, K 2 n . [13]
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.
Un cuadrado de frecuencia ( F -cuadrado) es una generalización de orden superior de un cuadrado latino . Sea S = { s 1 , s 2 , ..., s m } un conjunto de símbolos distintos y ( λ 1 , λ 2 , ..., λ m ) un vector de frecuencia de enteros positivos. Un cuadrado de frecuencia de orden n es una matriz n × n en la que cada símbolo s i aparece λ i veces, i = 1,2,..., m , en cada fila y columna. El orden n = λ 1 + λ 2 + ... + λ m . Un cuadrado F está en forma estándar si en la primera fila y columna, todas las apariciones de s i preceden a las de s j siempre que i < j .
Un cuadrado de frecuencia F 1 de orden n basado en el conjunto { s 1 , s 2 , ..., s m } con vector de frecuencia ( λ 1 , λ 2 , ..., λ m ) y un cuadrado de frecuencia F 2 , también de orden n , basados en el conjunto { t 1 , t 2 , ..., t k } con vector de frecuencia ( μ 1 , μ 2 , ..., μ k ) son ortogonales si cada par ordenado ( s i , t j ) aparece precisamente λ i μ j veces cuando se superponen F 1 y F 2 .
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 cruzan es isomorfa al plano afín finito AG (2,3).
Cualquier espacio afín AG( n ,3) da un ejemplo de un HTS. Un HTS de este tipo 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 número entero m ≥ 2. Los HTS no afines existen para cualquier m ≥ 4 y no existen para m = 2 o 3. [14]
Cada sistema triple de Steiner es equivalente a un cuasigrupo de Steiner ( idempotente , conmutativo y satisfactorio ( 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 2 n elementos. Un diseño de Howell , H( s ,2n ) (en el conjunto de símbolos S ) es una matriz s × s tal que:
Cada celda de la matriz está vacía o contiene un par desordenado de S ,
Cada símbolo aparece exactamente una vez en cada fila y columna de la matriz, y
Cada par de símbolos desordenados 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 habitación de lado 2 n − 1 y, por tanto, los diseños de Howell generalizan el concepto de cuadrados de habitación.
Los pares de símbolos en las celdas de un diseño de Howell se pueden considerar como los bordes de un gráfico regular s en 2 n vértices, llamado gráfico subyacente del diseño de Howell.
Los diseños cíclicos de Howell se utilizan como movimientos de Howell en torneos de bridge duplicados. Las filas del diseño representan las rondas, las columnas representan los tableros y las diagonales representan las mesas. [dieciséis]
Un diseño de lotería ( n , k , p , t ) es un n conjunto V de elementos junto con un conjunto β de k subconjuntos de elementos de V (bloques), de modo que para cualquier p subconjunto P de V , hay un bloque B en β para el cual |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 menor número posible de bloques: [17]
{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}.
Los diseños de Lotto modelan cualquier lotería que se ejecuta de la siguiente manera: los individuos compran boletos que consisten en k números elegidos de un conjunto de n números. En cierto punto se detiene la venta de entradas y se selecciona aleatoriamente un conjunto de p números de entre n números. Estos son los números ganadores . Si un boleto vendido contiene t o más de los números ganadores, se otorga un premio al poseedor del boleto. Los premios más grandes se otorgan a las entradas con más partidos. El valor de L( n , k , p , t ) es de interés tanto para los jugadores como para los investigadores, ya que es el número más pequeño de billetes que se necesitan comprar para garantizar un premio.
La lotería húngara tiene 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 siguen siendo desconocidos. [18]
Un diseño ( v , k , λ )-Mendelsohn , o MD( v , k , λ ), es un conjunto v V y una colección β de k -tuplas ordenadas de distintos elementos de V (llamados bloques ), tales que cada El 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 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 se puede convertir en un sistema triple de Mendelson reemplazando el triple desordenado { 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]
Un diseño cuasi-3 es un diseño simétrico (SBIBD) en el que cada triple de bloques se cruza en puntos x o y , para x e y fijos llamados 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) y 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 un plano proyectivo . [20]
Un diseño D t -( v , k , λ ) es cuasisimétrico con números de intersección x e y ( x < y ) si cada dos bloques distintos se cruzan en puntos x o y . Estos diseños surgen naturalmente en la investigación de los duales de diseños con λ = 1. Un diseño no simétrico ( b > v ) 2-( v , k ,1) es cuasisimétrico con x = 0 e y = 1. Un múltiplo ( repetir todos los bloques un cierto número de veces) de un diseño simétrico 2-( v , k , λ ) es cuasisimétrico con x = λ e y = k . Los diseños Hadamard 3 (extensiones de los diseños Hadamard 2 ) son cuasisimétricos. [21]
Todo diseño de bloques cuasisimétrico da lugar a un gráfico fuertemente regular (como su gráfico 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]
Un diseño esférico es un conjunto finito X de puntos en una esfera ( d − 1)-dimensional tal que, para algún número entero t , el valor promedio en X de cada polinomio
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.
Un rectángulo toscano- k r × n sobre n símbolos tiene r filas y n columnas tales que:
cada fila es una permutación de los n símbolos y
para dos símbolos distintos cualesquiera 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 . Una plaza romana es una plaza toscana que también es una plaza latina (también se conocen como plazas latinas completas en fila ). Una plaza del Vaticano es una plaza florentina que también es una plaza latina.
El siguiente ejemplo es un cuadrado toscano-1 con 7 símbolos que no es toscano-2: [24]
Un cuadrado toscano sobre n símbolos equivale 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 flash puede tener algún efecto en la impresión dada por la siguiente. Este sesgo se puede cancelar utilizando n secuencias correspondientes a las filas de un cuadrado toscano-1 de n × n . [26]
Un diseño equilibrado en t (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, tal que cada t -subconjunto de elementos distintos de X está contenido exactamente en λ bloques. Si K es un conjunto de enteros positivos estrictamente entre t y v , entonces el BD t es propio . Si todos los k -subconjuntos de X para algunos k son bloques, el t BD es un diseño trivial . [27]
Observe que en el siguiente ejemplo de un diseño 3-{12,{4,6},1) 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]
Un cuadrado de Youden es una matriz rectangular k × v ( k < v ) de v símbolos tal 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 , λ ). todos cuyos bloques ocurren 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 usaba una matriz cuadrada. [30] Un ejemplo de un cuadrado de Youden de 4 × 7 viene dado por:
Los siete bloques (columnas) forman el biplano de orden 2 (un diseño simétrico (7,4,2)).
^ Hayashi, Takao (2008). "Cuadrados mágicos en las matemáticas indias". Enciclopedia de la historia de la ciencia, la tecnología y la medicina en culturas no occidentales (2 ed.). Saltador. págs. 1252-1259. doi :10.1007/978-1-4020-4425-0_9778. ISBN 978-1-4020-4559-2.
^ Stinson 2003, pág. IX
^ Beth, Jungnickel y Lenz 1986, pág. 40 Ejemplo 5.8
^ Ryser 1963, pág. 52, Teorema 3.1
^ Cuando el grupo G es un grupo abeliano (o se escribe de forma aditiva), la propiedad definitoria se parece a d 1 –d 2 de donde proviene el término conjunto de diferencias .
^ Beth, Jungnickel y Lenz 1986, pág. 262, Teorema 1.6
^ Stinson 2003, pág. 74, Teorema 4.5
^ Stinson 2003, pág. 193, Teorema 8.20
^ Stinson 2003, pág. 183, Teorema 8.5
^ Colbourn y Dinitz 2007, pág. 331, Ejemplo 2.2
^ Colbourn y Dinitz 2007, pág. 331, Observación 2.8
^ Colbourn y Dinitz 2007, pág. 333, Observación 3.3
^ Colbourn y Dinitz 2007, pág. 496, Teorema 28.5
^ Colbourn y Dinitz 2007, pág. 497, Teorema 28.15
^ Colbourn y Dinitz 2007, pág. 503, Observación 29.38
^ Colbourn y Dinitz 2007, pág. 512, Ejemplo 32.4
^ Colbourn y Dinitz 2007, pág. 512, Observación 32.3
^ Colbourn y Dinitz 2007, pág. 530, Teorema 35.15
^ Colbourn y Dinitz 2007, pág. 577, Teorema 47.15
^ Colbourn y Dinitz 2007, págs. 578-579
^ Colbourn y Dinitz 2007, pág. 579, Teorema 48.10
^ Colbourn y Dinitz 2007, pág. 580, Lema 48.22
^ Colbourn y Dinitz 2007, pág. 652, Ejemplos 62.4
^ Colbourn y Dinitz 2007, pág. 655, Teorema 62.24
^ Colbourn y Dinitz 2007, pág. 657, Observación 62.29
^ Colbourn y Dinitz 2007, pág. 657
^ Colbourn y Dinitz 2007, pág. 658, Ejemplo 63.5
^ Raghavarao y Padgett 1988, pág. 305-308
^ Colbourn y Dinitz 2007, pág. 669, Observación 65.3
Referencias
Asmus, EF; Key, JD (1992), Diseños y sus códigos , Cambridge University Press, ISBN 0-521-41361-3
Bosé, RC (1949). "Una nota sobre la desigualdad de Fisher para diseños de bloques incompletos equilibrados". Anales de estadística matemática . 20 (4): 619–620. doi : 10.1214/aoms/1177729958 .
Caliński, Tadeusz; Kageyama, Sanpei (2003). Diseños de bloques: un enfoque de aleatorización, Volumen II: Diseño . Apuntes de conferencias sobre estadística. vol. 170. Saltador. ISBN 0-387-95470-8.
Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Manual de diseños combinatorios (2ª ed.), Boca Ratón: Chapman & Hall/CRC, ISBN 978-1-58488-506-1
Pescador, RA (1940). "Un examen de las diferentes posibles soluciones de un problema en bloques incompletos". Anales de la eugenesia . 10 : 52–75. doi :10.1111/j.1469-1809.1940.tb02237.x. hdl : 2440/15239 .
Hall, Jr., Marshall (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 University Press, ISBN 0-521-25754-9
Lander, ES (1983), Diseños simétricos: un enfoque algebraico , Cambridge: Cambridge University Press
Lindner, CC; Rodger, CA (1997), Teoría del diseño , Boca Ratón: CRC Press, ISBN 0-8493-3986-3
Raghavarao, Damaraju ; Padgett, Lakshmi V. (1988). Construcciones y Problemas Combinatorios en Diseño de Experimentos . Dover. ISBN 978-0-486-65685-4.
Raghavarao, Damaraju ; Padgett, Lakshmi V. (2005). Diseños de bloques: análisis, combinatoria y aplicaciones . Científico mundial. ISBN 978-981-4480-23-9.
Ryser, Herbert John (1963), "8. Diseños combinatorios", Matemáticas combinatorias , Carus Monograph, vol. 14, Asociación Matemática de América, ISBN 978-0-88385-000-8
