Tamaño máximo de la familia intersecante$F$ tal que$|A∪B| < n$ para todos$A,B ∈ F.$

Question

¿Podría alguien ayudarme por favor con este problema?

Supongamos que$F \subset 2^{[n]}$ es una familia de intersección tal que$|A∪B| < n$ para todo$A,B ∈ F.$ Demuestre que$|F| ≤ 2^{n−2}.$

Veo que$|F| \leq 2^{n-1},$ ya que de otro modo por principio de casilla tenemos un conjunto$A$ y es complemento, lo cual es una contradicción con la suposición de la familia que se intersecta. Pero no sé cómo utilizar la suposición$|A∪B| < n$ para obtener el límite deseado. Cualquier ayuda sería apreciada.

Answer 1

Podemos demostrar por contradicción, se sigue directamente de este lema: (si existiera una familia $F$ con más de $2^{n-2}$ elementos entonces el conjunto $F'$ de todos los conjuntos que son un subconjunto de al menos un elemento de a $F$ tiene al menos $2^{n-1}+2$ elementos y no hay dos de sus elementos, de dar a todos los de $[n]$ como su unión). Tenga en cuenta que la prueba de los vinculados resultado es un poco similar a lo que yo estaba tratando de hacer a continuación.

---

Imperfecto intento ( de hecho, el lema es falso, considerar la adopción de $n=2k$, y dejando $A$ sólo tiene el subconjunto $\{1,2,\dots\,k\}$ y dejando $B$ contienen el $2^n-2^{k+1}+1$ adecuado subconjuntos).

Lema: vamos a $n\geq 2$ y deje $A$ $B$ no vacía de subconjuntos de a $2^{[n]}$ que si $a\in A, b\in B$, luego tenemos a$a\cup b \neq [n]$$a\cap b\neq \varnothing$,$|A|+|B|\leq 2^{n-1}$.

Prueba: vamos a proceder por inducción, el caso base es $n=2$, cleary $A$$B$, ambos deben ser iguales y sólo contienen un singleton. Así que debemos tener $|A|+|B|=2=2^{n-1}$.

Inductivo paso: Supongamos que es cierto para $n$ y ahora vamos a probarlo para $n+1$. Tome $A$ $B$ como en el teorema, ahora vamos a $A_0=\{a | n\not\in a, a\in A\}$$A_1=\{a\setminus \{n\} | n\in a, a\in A\}$. Definir $B_0$ $B_1$ de forma análoga. Observe que $A_0$ $B_1$ satisface las condiciones del teorema, porque si tenemos $a\in A_0$ $b\in B_1$ tal que $a\cup b=[n-1]$ esto obligaría a la existencia de dos elementos en $A,B$ tales que su unión es $[n]$, también debemos tener $a\cap b \neq \varnothing$. De ello se desprende que $|A_0|+|B_1|\leq 2^{n-1-1}$ por la hipótesis de inducción. De forma análoga $|A_1|+|B_0|\leq 2^{n-1-1}$. De ello se desprende que $|A|+|B|\leq 2^{n-1}$.

La brecha es cuando uno de los auxiliares de conjuntos es vacía.

Para concluir aviso de que lo que quiere es el resultado particular de este teorema en el que $A=B$.