Diseño de la cubierta

Considerar${\displaystyle v=5}$,${\displaystyle k=3}$,${\displaystyle t=2}$Los cuatro bloques

${\displaystyle \{1,2,3\},\;\{1,4,5\},\;\{2,4,5\},\;\{3,4,5\}}$

formar un diseño de cobertura (5,  3,  2) sobre${\displaystyle \{1,2,3,4,5\}}$Dado que cada par de elementos aparece en al menos un bloque, esto es óptimo: cada bloque cubre tres de los diez pares posibles, pero dos subconjuntos distintos de 3 elementos de un conjunto de 5 elementos comparten como máximo un par, por lo que tres bloques pueden cubrir como máximo nueve pares. Por lo tanto,${\displaystyle C(5,3,2)=4}$.

La cota inferior general más utilizada es la cota de Schönheim , basada en una desigualdad recursiva debida a Schönheim (1964): ^{[ 3 ]}

${\displaystyle C(v,k,t)\geq \left\lceil {\frac {v}{k}}\,C(v-1,\,k-1,\,t-1)\right\rceil .}$

Esta desigualdad tiene una interpretación intuitiva: el elemento de una cubierta que aparece en la menor cantidad de bloques aparece en la mayor cantidad de bloques.${\displaystyle \lfloor (k/v)\,C(v,k,t)\rfloor }$bloques, y al eliminar ese elemento y todos los demás bloques se obtiene un${\displaystyle (v-1,k-1,t-1)}$-recubrimiento. ^{[ 1 ]} Aplicando la desigualdad recursivamente se obtiene la cota de Schönheim en forma cerrada :

${\displaystyle C(v,k,t)\geq L(v,k,t)=\left\lceil {\frac {v}{k}}\left\lceil {\frac {v-1}{k-1}}\cdots \left\lceil {\frac {v-t+1}{k-t+1}}\right\rceil \cdots \right\rceil \right\rceil .}$

Un límite debido a de Caen es a veces más ajustado, particularmente cuando${\displaystyle k}$y${\displaystyle t}$no son demasiado pequeños: ^{[ 4 ]}

${\displaystyle C(v,k,t)\geq {\frac {(t+1)(vt)}{(k+1)(vk)}}\cdot {\frac {\binom {v}{t}}{\binom {k}{t}}}.}$

Rödl (1985) demostró que para fijo${\displaystyle k}$y${\displaystyle t}$, existen recubrimientos cuya densidad se aproxima a 1 como${\displaystyle v\to \infty }$Esto implica que el número de cobertura es asintóticamente igual a${\displaystyle {\tbinom {v}{t}}/{\tbinom {k}{t}}}$, coincidiendo con el límite inferior trivial. ^{[ 5 ]}

Erdős y Spencer (1974) dieron una cota más débil pero totalmente explícita, válida para todos los valores de los parámetros, utilizando el método probabilístico : ^{[ 6 ]}

${\displaystyle C(v,k,t)\leq {\frac {\binom {v}{t}}{\binom {k}{t}}}\left(1+\ln {\tbinom {k}{t}}\right).}$

Este límite puede mejorarse como máximo por un factor constante (como máximo${\displaystyle 4\ln 2\approx 2.77}$) asintóticamente, como lo demuestra el caso${\displaystyle (v,v-1,\lfloor v/2\rfloor )}$, donde la cota inferior de Schönheim da densidad asintótica a${\displaystyle v/4}$mientras que la cota superior de Erdős-Spencer da densidad asintótica a${\displaystyle v\ln 2}$. ^{[ 1 ]}

Una cobertura voraz se construye mediante el siguiente procedimiento:

1. Organizar todo${\displaystyle k}$-subconjuntos de elementos del${\displaystyle v}$-establecido en una lista.
2. Seleccione el${\displaystyle k}$-subconjunto que cubre el mayor número de actualmente no cubiertos${\displaystyle t}$-subconjuntos (resuelviendo empates por posición en la lista).
3. Repita hasta que todo esté${\displaystyle t}$-Los subconjuntos están cubiertos.

Este enfoque es análogo al algoritmo voraz de Conway y Sloane para construir códigos lexicográficos . ^{[ 7 ]} La lista de${\displaystyle k}$Los subconjuntos pueden ordenarse lexicográficamente , colexicográficamente, según el código Gray o aleatoriamente; diferentes ordenaciones pueden generar coberturas de distintos tamaños. El método voraz es completamente general (se aplica a todos los parámetros válidos) y, en la práctica, produce resultados bastante buenos: aproximadamente el 42% de las entradas de la tabla calculadas por Gordon, Kuperberg y Patashnik provenían de coberturas voraces. Cabe destacar el sistema Steiner.${\displaystyle S(24,8,5)}$surge como una cobertura codiciosa bajo el orden lexicográfico. ^{[ 1 ]}

La principal desventaja es el costo computacional. Para fijo${\displaystyle k}$y${\displaystyle t}$El algoritmo requiere tiempo y espacio.${\displaystyle O(v^{k})}$. ^{[ 1 ]}

Las geometrías finitas producen recubrimientos muy buenos y a menudo óptimos para ciertas familias de parámetros. ^{[ 8 ] [ 9 ]}

En la geometría proyectiva${\displaystyle PG(m,q)}$sobre el campo${\displaystyle GF(q)}$, el${\displaystyle k}$subespacios -dimensionales (${\displaystyle k}$-planos) cubren cada conjunto de${\displaystyle k+1}$puntos independientes. Tomando el${\displaystyle (q^{m+1}-1)/(q-1)}$puntos como elementos y el${\displaystyle k}$-los pisos como bloques dan el límite:

${\displaystyle C\!\left({\frac {q^{m+1}-1}{q-1}},\;{\frac {q^{k+1}-1}{q-1}},\;k+1\right)\leq {\binom {m+1}{k+1}}_{q}}$

dónde${\displaystyle {\tbinom {n}{k}}_{q}}$denota el coeficiente binomial gaussiano . De manera similar, la geometría afín${\displaystyle AG(m,q)}$da:

${\displaystyle C\!\left(q^{m},\;q^{k},\;k+1\right)\leq q^{mk}{\tbinom {m}{k}}_{q}.}$

En ambos casos, la igualdad se cumple cuando${\displaystyle k=m-1}$o${\displaystyle k=1}$. Las cubiertas por líneas (${\displaystyle k=1}$) son sistemas Steiner . ^{[ 1 ]}

Una cubierta inducida construye una estructura más pequeña${\displaystyle (v',k',t)}$-cubriendo de uno más grande${\displaystyle (v,k,t)}$-cubriendo, donde${\displaystyle v'<v}$y${\displaystyle k'<k}$El procedimiento consiste en elegir aleatoriamente${\displaystyle v'}$elementos de la${\displaystyle v}$-establecer, restringir cada bloque a los elementos elegidos y luego ajustar los tamaños de los bloques: bloques más pequeños que${\displaystyle k'}$están rellenos con elementos arbitrarios, mientras que los bloques más grandes que${\displaystyle k'}$son reemplazados por una cubierta de sus elementos. La familia resultante forma una válida${\displaystyle (v',k',t)}$-cubriendo. ^{[ 1 ]}

Este método suele funcionar mejor cuando${\displaystyle k'/k\aprox v'/v}$y cuando se utiliza como punto de partida un buen recubrimiento, como uno de geometría finita. ^{[ 1 ]}

A${\displaystyle (v_{1}+v_{2},k,t)}$-La cubierta se puede ensamblar a partir de cubiertas de conjuntos de tamaños disjuntos.${\displaystyle v_{1}}$y${\displaystyle v_{2}}$. Para cada partición de${\displaystyle t}$elementos en${\displaystyle s}$elementos del primer conjunto y${\displaystyle t-s}$a partir del segundo, se utiliza un${\displaystyle (v_{1},\ell ,s)}$-cubriendo y un${\displaystyle (v_{2},k-\ell ,t-s)}$-cubriendo. Optimización sobre${\displaystyle \ell }$para cada valor de${\displaystyle s}$produce la cota: ^{[ 1 ]}

${\displaystyle C(v_{1}+v_{2},\,k,\,t)\leq \sum _{s=0}^{t}\min _{\ell }\,C(v_{1},\ell ,s)\cdot C(v_{2},k-\ell ,t-s).}$

Los productos de esta suma pueden presentar redundancia, la cual puede reducirse mediante programación dinámica para combinar términos adyacentes y obtener límites más precisos. Este método representa aproximadamente el 30% de las entradas de la tabla calculadas por Gordon, Kuperberg y Patashnik. ^{[ 1 ]} Incluye como casos especiales una serie de construcciones elementales, tales como:

• ${\displaystyle C(v,k+1,t)\leq C(v,k,t)}$(añadiendo un elemento aleatorio a cada bloque),
• ${\displaystyle C(v+1,k+1,t)\leq C(v,k,t)}$(añadiendo un nuevo elemento a cada bloque),
• ${\displaystyle C(v+1,k,t)\leq C(v,k,t)+C(v,k-1,t-1)}$(añadiendo un nuevo elemento solo a los bloques de la segunda cubierta).

• Recubrimientos cíclicos : Si el tamaño objetivo de un recubrimiento es${\displaystyle v}$, uno puede elegir uno solo${\displaystyle k}$-subconjunto y tomar todo${\displaystyle v-1}$cambios cíclicos. Para algunos parámetros, esto produce coberturas óptimas. ^{[ 1 ]}
• Ascenso de colina y recocido simulado : Partiendo de una colección aleatoria de bloques y mejorándolos iterativamente mediante la sustitución de bloques débiles. Nurmela y Östergård utilizaron el recocido simulado para encontrar muchos recubrimientos buenos. ^{[ 10 ]}
• Replicación : Reemplazar cada elemento por${\displaystyle m}$copias rinde${\displaystyle C(mv,mk,t)\leq C(v,k,t)}$. ^{[ 1 ]}

Un sistema Steiner${\displaystyle S(t,k,v)}$es un diseño de cubierta en el que cada${\displaystyle t}$El subconjunto de elementos está contenido en exactamente un bloque (equivalentemente, un diseño de recubrimiento de densidad 1). Cuando existe un sistema de Steiner, es simultáneamente un recubrimiento óptimo y un empaquetamiento óptimo, y${\displaystyle C(v,k,t)=L(v,k,t)}$Los sistemas de Steiner existen solo para ciertos conjuntos de parámetros; deben cumplirse las condiciones necesarias de divisibilidad , y la existencia no está garantizada incluso cuando se cumplen. Las geometrías proyectivas y afines sobre cuerpos finitos proporcionan familias infinitas de sistemas de Steiner con${\displaystyle t=2}$. ^{[ 1 ]}

El número de Turán${\displaystyle T(n,\ell ,r)}$es el número mínimo de${\displaystyle r}$subconjuntos de elementos de un${\displaystyle n}$-establecer de tal manera que cada${\displaystyle \ell }$El subconjunto de elementos contiene al menos uno de los elegidos.${\displaystyle r}$-subconjuntos. Al pasar a subconjuntos complementarios, se obtiene la identidad ^{[ 1 ].}

${\displaystyle C(v,k,t)=T(v,\,v-t,\,v-k).}$

Aunque los números de recubrimiento y los números de Turán son equivalentes, históricamente se han estudiado en diferentes rangos de parámetros: los problemas de recubrimiento suelen tener${\displaystyle v}$grande en relación con${\displaystyle k}$y${\displaystyle t}$, mientras que los problemas de Turán suelen tener${\displaystyle n}$grande en relación con${\displaystyle \ell }$y${\displaystyle r}$(correspondiente a${\displaystyle k}$y${\displaystyle t}$cerca de${\displaystyle v}$). ^{[ 1 ]}

Turán (1941) determinó${\displaystyle T(n,\ell ,2)}$exactamente para todos${\displaystyle n}$y${\displaystyle \ell }$, lo que implica que${\displaystyle C(v,v-2,t)=L(v,v-2,t)}$a pesar de${\displaystyle v}$y${\displaystyle t}$. ^{[ 11 ] [ 12 ]}

Dado un conjunto finito${\displaystyle X}$, una colección${\displaystyle C}$de subconjuntos de${\displaystyle X}$Tiene la propiedad B si podemos particionarla${\displaystyle X}$en dos subconjuntos disjuntos${\displaystyle Y}$y${\displaystyle Z}$de tal manera que cada conjunto en${\displaystyle C}$cumple ambos${\displaystyle Y}$y${\displaystyle Z}$. El número más pequeño de conjuntos en una colección de conjuntos de tamaño${\displaystyle n}$de tal manera que${\displaystyle C}$no tiene La propiedad B se denota por${\displaystyle m(n)}$.

La búsqueda de dicha colección puede restringirse a cubrir diseños: para cualquier diseño sin la Propiedad B, la fusión de cualquier par de puntos que no aparezcan en ningún bloque común produce otro diseño sin la Propiedad B, por lo que cualquier contraejemplo mínimo debe cubrir todos los pares de puntos. ^{[ 13 ]}