Esquema combinatorio

La teoría de esquemas combinatorios es una parte de la combinatoria (una rama de las matemáticas ) que considera la existencia, construcción y propiedades de familias de conjuntos finitos cuya estructura satisface conceptos generalizados de equilibrio y/o simetría . Estos conceptos no están definidos con precisión, por lo que una amplia gama de objetos pueden entenderse como esquemas combinatorios. Entonces, en un caso, los esquemas combinatorios pueden representar intersecciones de conjuntos de números, como en los diagramas de flujo , y en otro caso, pueden reflejar la disposición de los elementos en Sudoku .

La teoría de esquemas combinatorios se puede utilizar en el diseño de experimentos . Algunos de los esquemas combinatorios básicos se dan en el trabajo de Ronald Fisher sobre la teoría de los experimentos biológicos. Los esquemas combinatorios ahora se pueden encontrar en una amplia gama de campos, que incluyen geometría finita , programación de torneos , loterías , biología matemática , diseño y análisis de algoritmos , redes informáticas , pruebas grupales y criptografía [1] .

Definición

Denotar - el conjunto de elementos . Considere subconjuntos de este conjunto . Cada subconjunto se denomina bloque, y el número de elementos del conjunto que contiene se denomina volumen del bloque y se denota como . Sea el número de subconjuntos que contienen este elemento. El número de repeticiones (pares no ordenados) se denota como . Luego, el conjunto de bloques forma un esquema combinatorio (o diagrama de bloques) con parámetros [2] . $v$ ${\displaystyle m_{1},m_{2},...,m_{v))$ ${\displaystyle M_{1},M_{2},...,M_{b))$ $M_{j}$ $M_{j}$ ${\ Displaystyle k_ {j}}$ ${\ Displaystyle r_ {i}}$ $METRO$ ${\ estilo de visualización \ lambda _ {p}}$ ${\displaystyle M_{1},M_{2},...,M_{b))$ ${\displaystyle v,b,r_{i},k_{j},\lambda _{p))$

Ejemplo

Si hay n personas, ¿es posible formar conjuntos a partir de ellas de tal manera que cada persona pertenezca al menos a un conjunto, cada par pertenezca exactamente a un conjunto, cada dos conjuntos tengan solo una persona en la intersección y ninguno de los conjuntos consista en de todas las personas, todas las personas menos una o exactamente una persona? La respuesta depende de n .

La respuesta es sí solo si n es de la forma q 2 + q + 1. Es más difícil probar que la solución existe si q es una potencia prima . Existe la conjetura de que no hay otras soluciones. Se ha demostrado que si existe una solución para q que sean congruentes con 1 o 2 módulo 4, entonces q es la suma de dos cuadrados perfectos . Este resultado, el teorema de Brook-Reiser-Chowl , fue probado por una combinación de métodos de construcción basados en campos finitos y formas cuadráticas .

Cuando tal estructura existe, se le llama plano proyectivo finito . Esto muestra cómo se cruzan la teoría de las geometrías finitas y la combinatoria. En el caso q = 2, el plano proyectivo se llama plano de Fano .

Historia

Los esquemas combinatorios se conocen desde la antigüedad en la forma del cuadrado de Lo Shu , que fue una versión temprana del cuadrado mágico . Los esquemas combinatorios han evolucionado con el desarrollo de la combinatoria desde el siglo XVIII, por ejemplo, en forma de cuadrados latinos en el siglo XVIII y sistemas de Steiner en el siglo XIX. Los esquemas combinatorios también son populares en las matemáticas entretenidas , como el problema de la colegiala de Kirkman (1850) y 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 esquemas combinatorios se aplicaron al diseño de experimentos , geometrías finitas y esquemas de relación, y condujeron al surgimiento de la estadística algebraica .

Esquemas combinatorios fundamentales

El núcleo clásico de la asignatura de esquemas combinatorios se construye alrededor del diseño de bloques incompletos balanceados (en: Balanced Incomplete Block Design, BIBD), matrices y esquemas de Hadamard , BIBD simétricos , cuadrados latinos , BIBD resolubles , conjuntos de diferencias y esquemas balanceados por pares (en: Diseño equilibrado por pares, PBD) [3] . Otros esquemas combinatorios están relacionados o basados en los esquemas enumerados.

Un diagrama de bloques incompleto balanceado (BIBD), llamado diagrama de bloques para abreviar , es un conjunto B de b subconjuntos (llamados bloques ) de un conjunto finito X de v elementos, tal que cualquier elemento del conjunto X está contenido en algún número r bloques, cada bloque tiene el mismo número de elementos (= k ) y cada par de elementos distintos aparecen en el mismo número ( ) de bloques [2] . Los circuitos BIBD también se conocen como 2 circuitos y, a menudo, se denominan circuitos. Como ejemplo, para el caso y b = v obtenemos un plano proyectivo - X en este caso es el conjunto de puntos en el plano, y los bloques son líneas rectas. ${\ estilo de visualización = \ lambda}$ ${\ estilo de visualización 2-(v, k, \ lambda)}$ $\lambda=1$
Symmetric Balanced Incomplete Block Design o SBIBD (en: Symmetric Balanced Incomplete Block Design) es un BIBD en el que v = b (el número de puntos es igual al número de bloques). Esta es la subclase más importante y mejor estudiada de BIBD. Los planos proyectivos, los biplanos y los 2 esquemas de Hadamard son esquemas SBIBD. Estos esquemas son de interés como ejemplos extremos de la desigualdad de Fisher ( ). $b\geqslant v$
Un diagrama de bloques incompletos equilibrados que se puede resolver es un BIBD cuyos bloques se pueden dividir en conjuntos (llamados clases paralelas ), cada uno de los cuales forma una división de puntos BIBD [2] . El conjunto de clases paralelas se llama resolución de esquemaLa solución al famoso problema de los 15 estudiantes es la resolución BIBD con v = 15, k = 3 y [4] . $\lambda=1$
El rectángulo latino es unamatrizr × n( r ≤ n)tiene como elementos los números 1, 2, 3, ..., n(o cualquier otro conjunto dencaracteres diferentes) en la que ningún número aparece dos veces en cualquier fila o columna. Un rectángulolatinocon dimensionesn × nse llamacuadrado latino. Sir < n, entonces se pueden agregarn − rfilas a unr × npara formar un cuadrado latino usandoel teorema del teorema de la boda de Hall [5] .

Decimos que dos cuadrados latinos de orden n son ortogonales si el conjunto de todos los pares ordenados formado por los elementos correspondientes de dos cuadrados está formado por n 2 pares diferentes (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 (en: Mutually Orthogonal Latin Squares, MOLS) si cualquier par de cuadrados latinos en el conjunto es ortogonal. Puede haber como máximo n − 1 cuadrados en tal conjunto de cuadrados de orden n . El conjunto de n − 1 MOLS cuadrados de orden n se puede utilizar para construir un plano proyectivo de orden n (y viceversa).

El conjunto de diferencias es unsubconjuntoDdel grupoGde ordenv,tamañokGno sea igual a unose puede representar como un producto ded1d2−1elementos deDexactamente de la mismamanera (siGestá representada por la operación de multiplicación) [6] . ${\ estilo de visualización (v, k, \ lambda)}$ $\lambda$

Si D es un conjunto diferencia y g pertenece a G , entonces también es un conjunto diferencia y se llama traslación del conjunto D . El conjunto de transferencias del conjunto de diferencias D forma un diagrama de bloques simétrico . Tal esquema tiene v elementos y v bloques. Cada bloque del esquema consta de k puntos, cada punto está contenido en k bloques. Dos bloques cualesquiera tienen exactamente los mismos elementos, y dos puntos cualesquiera aparecen juntos en bloques. Este esquema SBIBD se denomina desarrollo del conjunto D [7] .

g\mathbf {D} ={gd\dos puntos d\in \mathbf {D} }

\lambda

\lambda

En particular, si , el conjunto de diferencias forma un plano proyectivo . Por ejemplo, un conjunto de diferencias (7,3,1) sobre un grupo ( un grupo abeliano con notación aditiva) es un subconjunto de {1,2,4}. El desarrollo de este conjunto de diferencias da el plano de Fano .

\lambda=1

\mathbb {Z} /7\mathbb {Z}

Dado que cualquier conjunto de diferencias produce SBIBD, el conjunto de parámetros debe satisfacer el teorema de Brook-Reiser-Chowl , pero no todos los esquemas SBIBD producen un conjunto de diferencias.

Una matriz de Hadamard de orden m es unamatriz H m × m con elementos ±1 tal que HH ⊤ = m E m , donde H ⊤ es la traspuesta de H y E m es la matriz identidad m × m . La matriz de Hadamard se puede reducir a una forma estandarizada (es decir, convertida a la matriz de Hadamard equivalente) en la que las entradas en la primera fila y la primera columna son +1. Si el orden m > 2, entonces m debe ser divisible por 4.

Dada una matriz de Hadamard de orden 4a en forma estandarizada, elimine la primera fila y la primera columna, y luego reemplace todos los −1 con 0. La matriz M 0–1 resultante es la matriz de incidencia de un circuito simétrico , llamado Hadamard 2-circuit [8] . Esta construcción es reversible, por lo que la matriz de incidencia de un circuito simétrico de 2 circuitos con estos parámetros se puede utilizar para obtener una matriz de Hadamard de orden 4a . En el caso de a = 2, obtenemos el ya conocido plano de Fano (como un esquema 2 de Hadamard).

{\ estilo de visualización 2-(4a-1,2a-1,a-1)}

Un diseño equilibrado por pares (en: Pairwise Balanced Design, PBD) es un conjunto X junto con una familia de subconjuntos de X (no necesariamente del mismo tamaño y los subconjuntos pueden ser iguales), tal que cualquier par de elementos distintos de X está contenido en exactamente (un número positivo) de subconjuntos. Se permite que un conjunto X sea parte de una familia, y si todos los subconjuntos son copias de un conjunto X , se dice que el esquema PBD es trivial . El tamaño del conjunto X es v , y el número de subconjuntos en la familia (los subconjuntos idénticos se cuentan por separado) es b . $\lambda$

La desigualdad de Fisher para esquemas PBD se cumple [9] — para cualquier esquema PBD no trivial, .

v\leqslant b

Este resultado generaliza el famoso teorema de Bruijn-Erdős : para cualquier esquema PBD con , que no tenga bloques de tamaño 1 o v , es verdadero , y la igualdad se cumple si y solo si el esquema es un plano proyectivo o casi un haz. [10] .

\lambda=1

v\leqslant b

Otros esquemas combinatorios

El Handbook of Combinatorial Designs de Colbourne y Dinitz [11] contiene, entre otros, 65 capítulos sobre diseños combinatorios distintos de los mencionados anteriormente. A continuación se proporciona una lista parcial.

Esquemas de relación
El diseño ternario equilibrado (en: Balanced Ternary Design) es una disposición de V elementos en B multiconjuntos (bloques, la cardinalidad de cada conjunto es K ( K ≤ V )), que cumple las condiciones: ${\ Displaystyle BTD (V, B; \ rho _ {1}, \ rho _ {2}, R; K, \ Lambda)}$

Cada elemento aparece una vez con una multiplicidad de 1 (1 instancia en el conjunto múltiple) exactamente en bloques, y con una multiplicidad de 2 exactamente en bloques. ${\ estilo de visualización R = \ rho _ {1} + 2 \ rho _ {2}}$ $\rho_{1}$ $\rho _{2}$
Cada par de elementos diferentes aparece una vez (teniendo en cuenta la multiplicidad). Es decir, si m vb es la multiplicidad del elemento v en el bloque b , entonces para cualquier par de elementos diferentes v y w . $\lambda$ $\sum_{b=1}^{B}m_{vb}m_{wb}=\Lambda$

Por ejemplo, uno de los dos esquemas no isomorfos BTD(4,8;2,3,8;4,6) (las columnas sirven como bloques) es [12]

una	una	una	2	2	3	una	una
una	una	una	2	2	3	2	2
2	3	cuatro	3	cuatro	cuatro	3	3
2	3	cuatro	3	cuatro	cuatro	cuatro	cuatro

La matriz de incidencia de un esquema BTD (cuyos elementos son multiplicidades de elementos en bloques) se puede utilizar para formar códigos correctores de errores ternarios de manera similar a la construcción de códigos binarios a partir de las matrices de incidencia de los esquemas BIBD [13] .

Un circuito de torneo balanceado de ordenn(BTD(n)) es la colocación de todos los pares no ordenados distintos de unconjuntoV2nmatriz n × (2n tal que

cada elemento de V aparece exactamente una vez en cada columna
cada elemento del conjunto V aparece como máximo dos veces en cada fila.

Ejemplo de esquema BTD(3)

dieciséis	3 5	2 3	4 5	24
25	4 6	catorce	13	3 6
3 4	12	5 6	26	quince

Las columnas del esquema BTD( n ) dan una factorización en 1 del gráfico completo con 2 n vértices, K 2n [14] . Los esquemas BTD( n ) se pueden usar para programar torneos de todos contra todos : las filas representan lugares, las columnas representan recorridos (rondas, círculos) y las entradas de la tabla definen jugadores o equipos.

Funciones dobladas
Arreglos de Costas
Experimentos factoriales completos
El cuadrado de frecuencia ( F -cuadrado ) es una generalización del cuadrado latino . Sea S = { s 1 , s 2 , ..., s m } un conjunto de símbolos diferentes y un vector de frecuencia de números positivos. Un cuadrado de frecuencia de orden n es una matriz de n × n en la que cada carácter s i aparece veces ( i = 1,2,...,m) en cada fila y cada columna. El cuadrado de frecuencia tiene una forma estándar si los elementos s i preceden a s j en la primera fila y primera columna para i < j . ${\ estilo de visualización (\ lambda _ {1}, \ lambda _ {2},..., \ lambda _ {m})}$ $(n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})$ $\lambda _{i}$

Un cuadrado de frecuencia F 1 de orden n sobre un conjunto { s 1 , s 2 , ..., s m } con un vector de frecuencia y un cuadrado de frecuencia F 2 también de orden n sobre un conjunto con un vector de frecuencia son ortogonales si los hay par ordenado ( s i , t j ) aparece exactamente una vez cuando F 1 y F 2 se superponen.

{\ estilo de visualización (\ lambda _ {1}, \ lambda _ {2},..., \ lambda _ {m})}

{\ estilo de visualización \{t_{1},t_{2},...,t_{k}\))

{\ estilo de visualización (\ mu _ {1}, \ mu _ {2},..., \ mu _ {k})}

{\ estilo de visualización \ lambda _ {i} \ mu _ {j}}

Los Sistemas Triples de Hall (HTS) son Sistemas Triples de Steiner (STS) (donde los bloques se denominan líneas ) con la propiedad de que la subestructura formada por la intersección de dos líneas es isomorfa al plano afín finito AG(2,3).

Cualquier espacio afín AG( n ,3) da un ejemplo de un esquema HTS, dichos esquemas se denominan HTS afines . También existen esquemas HTS no afines. El número de puntos en el esquema HTS es de 3 m para algún número entero . Los esquemas HTS no afines existen para cualquiera y no existen para o 3 [15] .

{\ estilo de visualización m \ geqslant 2}

{\ estilo de visualización m \ geqslant 4}

{\ estilo de visualización m = 2}

Cualquier sistema triple de Steiner es equivalente a un cuasigrupo de Steiner ( idempotente , conmutativo y válido para todo x e y ). El sistema de triples de Hall es equivalente a un cuasigrupo de Steiner con la propiedad distributiva , es decir, se cumple para todo a,x,y en el cuasigrupo [16] .

{\ estilo de visualización (xy) y = x}

a(xy)=(ax)(ay)

Sea S un conjunto de 2n elementos. El esquema de Howell , H( s ,2 n ) (en el conjunto de caracteres S ) es una matriz s × s tal que:

Cada celda de la matriz está vacía o contiene un par desordenado de S ,
Cada carácter aparece exactamente una vez en cada fila y cada columna de la matriz,
Cada par desordenado aparece como máximo en una celda de matriz.

Ejemplo de esquema H(4,6)

0 4		13	25
2 3	catorce	0 5
	3 5	24	0 1
quince	0 2		3 4

H(2 n − 1, 2 n ) es el cuadrado de Rum con lado 2 n − 1, por lo que los esquemas de Howell generalizan el concepto de cuadrados de Rum. Los pares de símbolos en las celdas del diagrama de Howell se pueden considerar como aristas s de un gráfico regular con 2n vértices, que se denomina el gráfico principal del diagrama de Howell. Los esquemas cíclicos de Howell se utilizan como movimientos de Howell (esquema de finalización del juego) en torneos de doble puente . Las filas del diagrama representan las rondas (círculos), las columnas representan las casillas (con ofertas preparadas de antemano, consulte "Puente: preparación para el juego" ) y las diagonales representan las mesas [17] .

Espacios lineales
Un esquema de lotería ( n , k , p , t ) es un conjunto V de n elementos junto con un conjunto de subconjuntos (bloques) de k elementos, de modo que para cualquier subconjunto P que consta de p elementos del conjunto V , existe un bloque B en , para lo cual . L( n , k , p , t ) significa el menor número de bloques en cualquier esquema de lotería ( n , k , p , t ). Esquema de lotería (7,5,4,3) con el menor número posible de bloques [18] : $\beta$ $\beta$ $|P\cap B|\geqslant t$

{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}. El esquema de lotería modela cualquier lotería con las siguientes reglas: Un jugador compra boletos que contienen k números, elegidos de un conjunto que contiene n números. En algún momento, la venta de boletos se detiene y se selecciona un conjunto aleatorio de p números contenidos en el conjunto original de n números. Estos son los números ganadores . Si el boleto vendido contiene t o más números ganadores, el premio se entrega al poseedor del boleto. Cuantos más partidos, mayor será la victoria. El número L( n , k , p , t ) es de interés tanto para jugadores como para investigadores porque representa el menor número de boletos que se deben comprar para garantizar una victoria. La lotería húngara es un esquema 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 ) son populares en todo el mundo. el mundo y son conocidos, que L(49,6,6,2) = 19. En general, estos números son difíciles de calcular y permanecen desconocidos [19] . La construcción geométrica de uno de estos esquemas se da en el artículo " Lotería de Transilvania ".

cuadrados magicos
Un esquema de Mendelssohn ( ) es un conjunto V de v elementos y un conjunto de k - tuplas ordenadas de elementos distintos del conjunto V (llamados bloques ) tales que cada par ordenado ( x , y ) de elementos de V ( x ≠ y ) es cíclicamente adyacente en bloques ( un par ordenado ( x , y ) de elementos distintos es cíclicamente adyacente en un bloque si los elementos aparecen uno al lado del otro en el bloque, ya sea (..., x , y ,...) o ( y ,..., x )). El esquema es un sistema de ternas de Mendelssohn , denominado MTS . Ejemplo de MTS(4,1) sobre V = {0,1,2,3}: $(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $MD(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda )))$ $\beta$ $\lambda$ $MD(\mathbf {v} ,\mathbf {3} ,{\boldsymbol {\lambda )))$ $(\mathbf {v} ,{\boldsymbol {\lambda )))$

(0.1.2) (1.0.3) (2.1.3) (0.2.3) Cualquier sistema de ternas se puede convertir en un sistema de ternas de Mendelssohn reemplazando la terna desordenada { a , b , c } con un par de ternas ordenadas ( a , b , c ) y ( a , c , b ), pero lo contrario es no es cierto, como muestra el ejemplo. Sea ( Q ,∗) un cuasigrupo semisimétrico idempotente , es decir, x ∗ x = x (idempotente) y x ∗ ( y ∗ x ) = y (semisimétrico) se cumple para todo x , y de Q . deja _ Entonces es un sistema de tripletas de Mendelssohn MTS(| Q |,1). Esta construcción es reversible [20] .

{\displaystyle \beta =\{(x,y,x\ast y)\colon x,y\in Q\))

{\ estilo de visualización (Q, \ beta)}

Mesas ortogonales
Un circuito cuasi-3 es un circuito simétrico (SBIBD) en el que cada bloque triple se cruza en los puntos x o y para números x e y fijos , llamados números de intersección triple ( x < y ). Cualquier circuito simétrico con es un circuito cuasi-3 con y . El esquema punto-hiperplano de la geometría PG ( n , q ) es un esquema cuasi-3 con y . Si para un circuito cuasi-3, el circuito es isomorfo a PG ( n , q ) o al plano proyectivo [21] . ${\ estilo de visualización \ lambda \ leqslant 2}$ $x=0$ ${\ estilo de visualización y = 1}$ ${\ estilo de visualización x = (q^{n-2}-1)/(q-1)}$ $y=\lambda =(q^{n-1}-1)/(q-1)$ ${\ estilo de visualización y = \ lambda}$
Un circuito es casi simétrico con números de intersección x e y ( x < y ) si dos bloques distintos tienen puntos x o y en su intersección. Estos esquemas surgen naturalmente en el estudio de esquemas duales con . Un circuito no simétrico ( b > v ) 2-( v , k ,1) es casi simétrico con x = 0 y y = 1. Múltiples (los bloques se repiten cierto número de veces) simétricos 2 -los circuitos son cuasi- simétrico con y = k . Los 3 esquemas de Hadamard (una extensión de los 2 esquemas de Hadamard ) son casi simétricos [22] . $Dt-(v,k,\lambda)$ $\lambda=1$ ${\ estilo de visualización (v, k, \ lambda)}$ ${\ estilo de visualización x = \ lambda}$

Cualquier diagrama de bloques cuasi simétrico genera un gráfico fuertemente regular (como su gráfico de bloques ), pero no todos los circuitos SRG se generan de esta manera [23] . La matriz de incidencia de un circuito cuasi-simétrico 2- con k ≡ x ≡ y (mod 2) forma un código binario autoortogonal [24] .

{\ estilo de visualización (v, k, \ lambda)}

Cuadritos de Ron
Un diseño esférico es un conjunto finitoXde puntos en unaesferad − 1)tal que, para algún número enterot, la media delpolinomioX

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

con un grado no superior a t es igual al valor medio de f sobre toda la esfera (es decir, la integral de la función f dividida por el área de la esfera).

Sistemas Turan
El rectángulo toscano r × n k sobre n caracteres tiene r filas y n columnas, mientras que

cada línea es una permutación de n caracteres
para dos caracteres distintos cualesquiera a y b , y para cada número m de 1 a k , hay como máximo una línea en la que b es m pasos a la derecha de a .

Si r = n y k = 1, los esquemas se denominan cuadrados toscanos , mientras que en el caso de r = n y k = n - 1 se denominan cuadrados florentinos . Un cuadrado romano es un cuadrado toscano que también es un cuadrado latino (estos cuadrados también se conocen como cuadrados latinos de fila completa ). La plaza del Vaticano es una plaza florentina, que también es una plaza latina. Un ejemplo de un cuadrado toscano de 1 en 7 caracteres que no es un cuadrado de 2 [25] :

6	una	5	2	cuatro	3	7
2	6	3	5	cuatro	7	una
5	7	2	3	una	cuatro	6
cuatro	2	5	una	6	7	3
3	6	2	una	7	cuatro	5
una	3	2	7	5	6	cuatro
7	6	5	3	cuatro	una	2

Un cuadrado toscano en n símbolos es equivalente a una descomposición de gráficos completos con n vértices en n caminos orientados hamiltonianos [26] .

Un circuito balanceado de t veces (o t BD) de tipo t - es un conjunto X de v elementos junto con una familia de subconjuntos de X (llamados bloques ) cuyos tamaños están contenidos en un conjunto K tal que cualquier t -subconjunto de elementos distintos elementos de X está contenido exactamente en bloques. Si K es un conjunto de enteros positivos estrictamente entre t y v , entonces el esquema t BD se llama propio . Si todos los k -subconjuntos de X para algunos k son bloques, entonces el esquema t BD se llama trivial [27] . ${\ estilo de visualización (v, K, \ lambda)}$ $\lambda$

Note que en el ejemplo 3-{12,{4,6},1) esquemas en el conjunto X = {1,2,...,12}, algunos pares aparecen cuatro veces (por ejemplo, el par {1, 2}), mientras que otros aparecen cinco veces (por ejemplo, el par {6,12}) [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

Un cuadrado latino incompleto es una matriz rectangular k × v ( k < v ) v de caracteres tal que cada carácter aparece exactamente una vez en cada fila y los caracteres que aparecen en cualquier columna forman bloques de un circuito simétrico , todos los cuales aparecen exactamente una vez . Un cuadrado latino incompleto es un rectángulo latino. El término "cuadrado" en el título proviene de una definición anterior que usaba una matriz cuadrada [29] . Un ejemplo de un cuadrado latino 4×7 incompleto: ${\ estilo de visualización (v, k, \ lambda)}$

una	2	3	cuatro	5	6	7
2	3	cuatro	5	6	7	una
3	cuatro	5	6	7	una	2
5	6	7	una	2	3	cuatro

Siete bloques (columnas) forman un biplano de orden 2 (esquema simétrico (7,4,2)).

Notas

↑ Stinson, 2003 , pág. una.
↑ 1 2 3 Rybnikov, 1972 , pág. 130.
↑ Stinson, 2003 , pág. IX.
↑ Beth, Jungnickel, Lenz, 1999 , pág. 40 Ejemplo 5.8.
↑ Ryser, 1963 , pág. 52 Teorema 3.1.
↑ Si G es un grupo abeliano (o se escribe con una operación de suma), la definición toma la forma d 1 –d 2 , de donde surge el término conjunto diferencia .
↑ Beth, Jungnickel, Lenz, 1999 , 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, Dinitz, 2007 .
↑ Colbourn, Dinitz, 2007 , pág. 331 Ejemplo 2.2.
↑ Colbourn, Dinitz, 2007 , pág. 331 Observación 2.8.
↑ Colbourn, Dinitz, 2007 , pág. 333, Observación 3.3.
↑ Colbourn, Dinitz, 2007 , pág. 496 Teorema 28.5.
↑ Colbourn, Dinitz, 2007 , pág. 497 Teorema 28.15.
↑ Colbourn, Dinitz, 2007 , pág. 503 Observación 29.38.
↑ Colbourn, Dinitz, 2007 , pág. 512 Ejemplo 32.4.
↑ Colbourn, Dinitz, 2007 , pág. 512, Observación 32.3.
↑ Colbourn, Dinitz, 2007 , pág. 530 Teorema 35.15.
↑ Colbourn, Dinitz, 2007 , pág. 577 Teorema 47.15.
↑ Colbourn, Dinitz, 2007 , pág. 578-579.
↑ Colbourn, Dinitz, 2007 , pág. 579 Teorema 48.10.
↑ Colbourn, Dinitz, 2007 , pág. 580 Lema 48.22.
↑ Colbourn, Dinitz, 2007 , pág. 652 Ejemplos 62.4.
↑ Colbourn, Dinitz, 2007 , pág. 655 Teorema 62.24.
↑ Colbourn, Dinitz, 2007 , pág. 657.
↑ Colbourn, Dinitz, 2007 , pág. 658 Ejemplo 63.5.
↑ Colbourn, Dinitz, 2007 , pág. 669 Observación 65.3.

Literatura

Rybnikov K. A. Introducción al análisis combinatorio. - Universidad Estatal de Moscú, 1972.
Tarannikov Yu. V. Propiedades combinatorias de estructuras discretas y aplicaciones a la criptología. - MTSNMO, 2011. - ISBN 978-5-94057-812-3 .
Hall M. Combinatoria. - MIR, 1966.
Assmus EF, Diseños clave de JD y sus códigos. - Cambridge: Cambridge University Press, 1992. - ISBN 0-521-41361-3 .
Beth T., Jungnickel D., Lenz H. Teoría del diseño. - Cambridge: Cambridge University Press , 1999. - ISBN 978-0-521-44432-3 .
Bose RC Una nota sobre la desigualdad de Fisher para diseños de bloques incompletos equilibrados // Annals of Mathematical Statistics . - 1949. - S. 619-620 .
Caliński T., Kageyama S. Diseños de bloques: un enfoque de aleatorización, Volumen II : Diseño. - Nueva York: Springer-Verlag, 2003. - Vol. 170. - (Lecture Notes in Statistics). — ISBN 0-387-95470-8 .
Colbourn Charles J., Dinitz Jeffrey H. Manual de diseños combinatorios. — 2do. — Boca Ratón: Chapman & Hall/CRC, 2007. — ISBN 1-58488-506-8 .
Fisher RA Un examen de las diferentes soluciones posibles de un problema en bloques incompletos // Annals of Eugenics . - 1940. - T. 10 . — S. 52–75 .
hall marshall jr. teoría combinatoria. — 2do. - Nueva York: Wiley-Interscience, 1986. - ISBN 0-471-09138-3 .
Hughes DR, Piper EC Teoría del diseño . - Cambridge: Cambridge University Press, 1985. - ISBN 0-521-25754-9 .
Lander ES Diseños simétricos: un enfoque algebraico. —Cambridge: Prensa de la Universidad de Cambridge, 1983.
Lindner CC, Rodger CA Teoría del diseño . - Boca Ratón: CRC Press, 1997. - ISBN 0-8493-3986-3 .
Raghavarao D. Construcciones y problemas combinatorios en el diseño de experimentos. —reimpresión corregida del Wiley de 1971. — Nueva York: Dover, 1988.
Raghavarao D., Padgett Diseños de bloques LV: análisis, combinatoria y aplicaciones. — Mundo científico, 2005.
Ryser Herbert John. Capítulo 8: Diseños Combinatorios // Matemáticas Combinatorias (Monografía de Carus #14). — Asociación Matemática de América, 1963.
Shrikhande SS, Vasanti NB-N. Soluciones no isomórficas de algunos diseños de bloques incompletos balanceados I – // Journal of Combinatorial Theory . — 1970.
Stinson Douglas R. Diseños combinatorios: construcciones y análisis. - Nueva York: Springer, 2003. - ISBN 0-387-95487-2 .
Street Anne Penfold, Street Deborah J. Combinatoria de Diseño Experimental. - Oxford UP [Clarendon], 1987. - P. 400+xiv. — ISBN 0-19-853256-3 .
van Lint, JH y R. M. Wilson. Un curso de combinatoria. — Cambridge, Ing.: Cambridge University Press, 1992.