stringtranslate.com

Diseño combinatorio

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 pensar que una amplia gama de objetos están bajo el mismo paraguas. A veces, esto puede implicar los tamaños numéricos de las intersecciones de conjuntos, como en los diseños de bloques , mientras que en otras ocasiones puede 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 se puede aplicar al área de diseño de experimentos . Algunas de las teorías básicas de los diseños combinatorios se originaron 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]

Ejemplo

El avión de Fano

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é en exactamente un conjunto, cada dos conjuntos tengan exactamente una persona en común y ningún conjunto contenga a todos, a todas las personas menos una o exactamente a una persona? La respuesta depende de n .

Esto tiene una solución sólo si n tiene la forma q 2 + q + 1. Es menos simple probar 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 módulo 4, entonces q es una suma de dos números cuadrados . Este último resultado, el teorema de Bruck-Ryser , se prueba mediante una combinación de métodos constructivos basados ​​en cuerpos finitos y una aplicación de formas cuadráticas .

Cuando existe una estructura de este tipo, se denomina plano proyectivo finito , lo que demuestra cómo se intersecan 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 año 587 d. C., con el propósito de elaborar perfumes utilizando 4 sustancias seleccionadas de 16 sustancias diferentes mediante un cuadrado mágico. [2]

Los diseños combinatorios se desarrollaron junto con el crecimiento general de la combinatoria a partir del 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 las 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 , lo que dio lugar al campo de la estadística algebraica .

Diseños combinatorios fundamentales

El núcleo clásico de la materia de diseños combinatorios se construye alrededor de diseños de bloques incompletos balanceados (BIBDs) , matrices de Hadamard y diseños de Hadamard , BIBD simétricos , cuadrados latinos , BIBD resolubles , conjuntos de diferencias y diseños balanceados por pares (PBDs). [3] Otros diseños combinatorios están relacionados con o se han desarrollado a partir del estudio de estos diseños fundamentales.

Se dice que dos cuadrados latinos de orden n son ortogonales si el conjunto de todos los pares ordenados que consisten en las entradas correspondientes en los dos cuadrados tiene n 2 miembros distintos (todos los pares ordenados posibles ocurren). Un conjunto de cuadrados latinos del mismo orden forma un conjunto de cuadrados latinos mutuamente ortogonales (MOLS) si cada par de cuadrados latinos en el conjunto es ortogonal. Puede haber como máximo n  − 1 cuadrados en un conjunto de MOLS de orden n . Un conjunto de n  − 1 MOLS de orden n se puede utilizar para construir un plano proyectivo de orden n (y viceversa).
Si D es un conjunto de diferencias y g en G , entonces g D  = { gd : d en 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 un diseño de este tipo 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 denomina desarrollo de D . [7]
En particular, si λ = 1, entonces el conjunto de diferencias 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 de diferencias da lugar al plano de 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 cada SBIBD da un conjunto de diferencias.
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 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 un 2-diseño de Hadamard . [8] Esta construcción es reversible, y la matriz de incidencia de un 2-diseño simétrico con estos parámetros se puede utilizar para formar una matriz de Hadamard de orden 4 a . Cuando a  = 2 obtenemos el, por ahora familiar, plano de Fano como un 2-diseño de Hadamard.
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 lápiz cercano. [10]

Otros diseños combinatorios

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

  1. Cada elemento aparece R = ρ 1 + 2 ρ 2 veces en total, con multiplicidad uno en exactamente ρ 1 bloques y multiplicidad dos en exactamente ρ 2 bloques.
  2. 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 los BIBD. [12]
  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) lo da
Las columnas de un BTD( n ) proporcionan una factorización 1 del gráfico completo en 2n vértices , K 2 n . [13]
Los BTD( n ) se pueden usar para programar torneos 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 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 , basado 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 F 1 y F 2 se superponen.
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 entero m  ≥ 2. Existen HTS no afines 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 todos los 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 todos los a , x , y en el cuasigrupo. [15]
  1. Cada celda de la matriz está vacía o contiene un par desordenado 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 desordenados aparece como máximo en una celda de la matriz.
Un ejemplo de un H (4,6) es
Un H(2 n  − 1, 2 n ) es un cuadrado de habitación de lado 2 n  − 1 y, por lo 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 Howell pueden considerarse como los bordes de un gráfico regular en 2n vértices , llamado el gráfico subyacente del diseño 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]
{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}.
Los diseños de lotería modelan cualquier lotería que se lleve a cabo de la siguiente manera: las personas compran boletos que consisten en k números elegidos de un conjunto de n números. En un momento determinado, la venta de boletos se detiene y se selecciona aleatoriamente un conjunto de p números de los n números. Estos son los números ganadores . Si cualquier boleto vendido contiene t o más de los números ganadores, se le otorga un premio al poseedor del boleto. Los premios más grandes se otorgan a los boletos con más coincidencias. El valor de L( n , k , p , t ) es de interés tanto para los jugadores como para los investigadores, ya que este es el número más pequeño de boletos 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]
En la lotería de Transilvania se da una construcción geométrica de uno de estos diseños .
(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 desordenado { a , b , c } por el par de triples ordenados ( a , b , c ) y ( a , c , b ), pero como muestra el ejemplo, el recíproco de esta afirmación no es verdadero.
Si ( Q ,∗) es un cuasigrupo semisimétrico idempotente , es decir, xx = x (idempotente) y x ∗ ( yx ) = y (semisimétrico) para todo x , y en Q , sea β = {( x , y , xy ): x , y en Q }. Entonces ( Q , β) es un sistema triple de Mendelsohn MTS(| Q |,1). Esta construcción es reversible. [19]
Todo diseño de bloque cuasisimétrico da lugar a un gráfico fuertemente regular (como su gráfico de bloque), pero no todos los SRG surgen de esta manera. [22]
La matriz de incidencia de un diseño cuasisimétrico 2-( v , k , λ ) con kxy (mod 2) genera un código binario autoortogonal (cuando está bordeado si k es impar). [23]
de grado total como máximo t es igual al valor medio de f en toda la esfera, es decir, la integral de f dividida por el área de la esfera.
  1. Cada fila es una permutación de los n símbolos y
  2. para dos símbolos distintos a y b y para cada m desde 1 hasta 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, se denominan cuadrados florentinos . Un cuadrado romano es un cuadrado toscano que también es un cuadrado latino (también se conocen como cuadrados latinos de fila completa ). Un cuadrado vaticano es un cuadrado florentino que también es un cuadrado latino.
El siguiente ejemplo es un cuadrado toscano-1 sobre 7 símbolos que no es toscano-2: [24]
Un cuadrado toscano sobre n símbolos es equivalente a una descomposición del gráfico 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 da la siguiente. Este sesgo se puede cancelar utilizando n secuencias correspondientes a las filas de un cuadrado toscano-1 de n × n . [26]
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]
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
Los siete bloques (columnas) forman el biplano de orden 2 (un diseño simétrico (7,4,2)).

Véase también

Notas

  1. ^ Stinson 2003, pág. 1
  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.). Springer. págs. 1252-1259. doi :10.1007/978-1-4020-4425-0_9778. ISBN 978-1-4020-4559-2.
  3. ^ Stinson 2003, pág. IX
  4. ^ Beth, Jungnickel y Lenz 1986, pág. 40 Ejemplo 5.8
  5. ^ Ryser 1963, pág. 52, Teorema 3.1
  6. ^ Cuando el grupo G es un grupo abeliano (o escrito de forma aditiva) la propiedad definitoria se ve así: d 1 –d 2, de donde proviene el término conjunto de diferencias .
  7. ^ Beth, Jungnickel y Lenz 1986, pág. 262, Teorema 1.6
  8. ^ Stinson 2003, pág. 74, Teorema 4.5
  9. ^ Stinson 2003, pág. 193, Teorema 8.20
  10. ^ Stinson 2003, pág. 183, Teorema 8.5
  11. ^ Colbourn y Dinitz 2007, pág. 331, Ejemplo 2.2
  12. ^ Colbourn y Dinitz 2007, pág. 331, Observación 2.8
  13. ^ Colbourn y Dinitz 2007, pág. 333, Observación 3.3
  14. ^ Colbourn y Dinitz 2007, pág. 496, Teorema 28.5
  15. ^ Colbourn y Dinitz 2007, pág. 497, Teorema 28.15
  16. ^ Colbourn y Dinitz 2007, pág. 503, Observación 29.38
  17. ^ Colbourn y Dinitz 2007, pág. 512, Ejemplo 32.4
  18. ^ Colbourn y Dinitz 2007, pág. 512, Observación 32.3
  19. ^ Colbourn y Dinitz 2007, pág. 530, Teorema 35.15
  20. ^ Colbourn y Dinitz 2007, pág. 577, Teorema 47.15
  21. ^ Colbourn y Dinitz 2007, págs. 578-579
  22. ^ Colbourn y Dinitz 2007, pág. 579, Teorema 48.10
  23. ^ Colbourn y Dinitz 2007, pág. 580, Lema 48.22
  24. ^ Colbourn y Dinitz 2007, pág. 652, Ejemplos 62.4
  25. ^ Colbourn y Dinitz 2007, pág. 655, Teorema 62.24
  26. ^ Colbourn y Dinitz 2007, pág. 657, Observación 62.29
  27. ^ Colbourn y Dinitz 2007, pág. 657
  28. ^ Colbourn y Dinitz 2007, pág. 658, Ejemplo 63.5
  29. ^ Raghavarao y Padgett 1988, pág. 305-308
  30. ^ Colbourn y Dinitz 2007, pág. 669, Observación 65.3

Referencias