Número mínimo de subconjuntos de $A$ de un orden determinado que contengan todos los pares posibles de elementos de $A$

Question

Consideremos un conjunto $A$ que contiene $n$ elementos. ¿Cuál es el número mínimo de subconjuntos de $A$ de orden $k\geq 2$ tal que, para cada $(x, y)\in A^2$ al menos uno de esos subconjuntos contiene ambos $x$ y $y$ como sus elementos?

Sabemos que el número de pares desordenados de elementos de $A$ es $$\binom{n}{2},$$ pero el mínimo número de estos subconjuntos es definitivamente menor. En $k = 5$ el subconjunto $\{a,b,c,d,e\}$ ya produce $10$ de estos pares. Y si $n = k$ entonces la respuesta es trivialmente $1$ .

¿Existe alguna forma de calcular el número mínimo de subconjuntos que satisfacen esta condición, dado $n$ y $k$ ?

Answer 1

Se trata de un problema de cobertura de conjuntos un tema muy meditado del que no sé nada. Sin embargo, tengo en mi biblioteca el libro Empaquetamiento y recubrimiento en combinatoria A. Schrijver (ed.), Mathematical Centre Tracts 106, Mathematisch Centrum, Amsterdam, 1979, que contiene en las págs. 89-97 un artículo "Packing and covering of $\binom kt$ -sets" de A. E. Brouwer con una bibliografía de 28 artículos. Por supuesto, se necesita algo más actualizado, pero al menos este estudio de 1979 es un punto de partida.

Brouwer define: $$C(t,k,v)=\min\{|\mathcal B|:\mathcal B\subseteq\mathcal P_k(v)\text{ and each }T\in\mathcal P_t(v)\text{ is contained in some }B\in\mathcal B\}$$ donde $\mathcal P_t(v)$ es el conjunto de todos los $t$ -subconjuntos de elementos del conjunto $\{0,1,\dots,v-1\}.$

Así, en notación de Brouwer, se pide el valor de $C(2,k,n).$ El límite inferior obvio es $$C(2,k,n)\ge\frac{\binom n2}{\binom k2}=\frac{n(n-1)}{k(k-1)}.$$ Las respuestas completas sólo se conocen (o, mejor dicho, se conocían en 1979) para $k=3$ y $k=4.$ El resultado de la cobertura

$$C(2,3,n)=\left\lceil\frac n3\left\lceil\frac{n-1}2\right\rceil\right\rceil$$

se atribuye a M. K. Fort, Jr. y G. A. Hedlund, Cubiertas mínimas de pares por triples Pacific J. Math. 8. (1958) 709-719.

Para $n\notin\{7,9,10,19\}$ el resultado $$C(2,4,n)=\left\lceil\frac n4\left\lceil\frac{n-1}3\right\rceil\right\rceil$$ se atribuye a W. H. Mills, Sobre el recubrimiento de pares por cuádruples , I: J. Combin. Theory (A) 13 (1972) 55-78, II: J. Combin. Theory (A) 15 (1973) 138-166; los valores excepcionales son $C(2,4,7)=5,\ C(2,4,9)=8,\ C(2,4,10)=9,\ C(2,4,19)=31.$

P.D. Brian Scott señala que "existe una segunda edición de MCT 106 de 1982, disponible gratuitamente aquí como PDF (no consultable). Los cambios respecto a la primera edición parecen ser muy pequeños".

Answer 2

Sea A un conjunto que contiene n elementos. Hay $\frac{n!}{k! (n-k)!}$ subconjuntos de A con k elementos, y los elementos $a,b\in A$ se incluyen en $\frac{(n-2)!}{(k-2)! (n-k)!}$ de aquellos subconjuntos con k elementos. Lo que significa que en $ M= \frac{n!}{k! (n-k)!} - \frac{(n-2)!}{(k-2)! (n-k)!}$ de ellos o bien $a$ o $b$ o ambos $a, b$ no están incluidos.

Por lo tanto, es necesario tener al menos M+1 subconjuntos de A con k elementos para garantizar que tanto $a$ y $b$ están incluidos en al menos uno de ellos.