Subconjuntos con poca interacción.

Question

Para un conjunto $X$ de cardinalidad $N$ Cómo podemos encontrar un conjunto de subconjuntos de $X$ de cardinalidad $C$ tal que no hay dos subconjuntos que tengan una intersección de más de $n$ elementos? ¿Cuál es la mayor cardinalidad del conjunto mencionado?

Answer 1

Cada subconjunto puede ponerse en correspondencia con un vector binario de longitud $N$ con peso (número de unos) $C$ . Por ejemplo, digamos $N=5$ y $C=3$ el vector $v=[1, 0 , 0 , 1 , 1]$ (longitud=5, peso=3), corresponde a la selección de los elementos 1, 4 y 5. Evidentemente, hay ${5 \choose 3}$ tales vectores.

Pero tenemos el requisito adicional de una intersección de como máximo $n$ elementos para cada par. Esto equivale a tener como máximo $n$ en común, o al menos $2(C-n)$ diferentes elementos. Entonces, en el lenguaje de códigos binarios, estamos tras un código de peso constante (Peso $C$ , longitud $N$ ) con una distancia Hamming mínima de $d = 2(C-n)$ . Se trata de un sistema bien conocido y problema difícil ; hay algunos límites , tablas y más .

Answer 2

Aquí hay dos observaciones que he hecho:

Podemos sumar todos los subconjuntos de tamaño $n-1$ sin ningún problema. Una vez que hayamos hecho esto, debemos añadir todo el tamaño $n$ como sea posible y nunca añadir conjuntos más grandes. Así que el problema es equivalente a encontrar el máximo número de subconjuntos todos de cardinalidad $n+1$ que podemos encajar.