Elegir subconjuntos para conjuntos más grandes

Question

Creo que esto es probablemente conocido/fácil, pero no puedo resolverlo.

Consideremos el conjunto a $S=\{1,2,\ldots, n\}$, y deje $a<b<n$. ¿Cuál es el mínimo número de $f(a,b)$ tal de que no existe $f(a,b)$ subconjuntos de a $S$ del tamaño de la $a$ para que cualquier subconjunto de a $S$ del tamaño de la $b$ contiene al menos uno de los elegidos, de los subconjuntos.

Claramente $f(a,b)\leq \dbinom{n}{a}$, el número de subconjuntos de a $S$ del tamaño de la $a$. (La elección de todos los subconjuntos sin duda satisface la condición.)

Edit: por Favor, consulte aquí para más discusión.

Answer 1

Revisado: al menos podemos conseguir algo mejor cota superior.

Supongamos que $B\subseteq S$$|B|=b$. Para $k=0,\ldots,a-1$ hay $\binom{b}k\binom{n-b}{a-k}$ subconjuntos $A$ $S$ tal que $|A|=a$$A\nsubseteq B$, por lo que hay una familia de

$$\sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}$$

los subconjuntos de a $S$ de cardinalidad $a$, ninguno de los cuales es un subconjunto de a $B$. Todos los otros $a$-subconjunto de $S$ es un subconjunto de a $B$. Por lo tanto,

$$f(a,b)\le 1+\sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}\;.$$

Tenga en cuenta que $\binom{b}k\binom{n-b}{a-k}=0$ si $k<0$ o $k>a$, por lo que

$$\begin{align*} \sum_{k=0}^{a-1}\binom{b}k\binom{n-b}{a-k}&=\sum_k\binom{n}k\binom{n-b}{a-k}-\binom{b}a\binom{n-b}0\\ &=\binom{n}a-\binom{b}a \end{align*}$$

por Vandermonde de la identidad. Finalmente, entonces,

$$f(a,b)\le\binom{n}a-\binom{b}a+1\;.$$

Agrega₁: por supuesto, yo lo hice de la manera difícil: $S$ $\binom{n}a$ subconjuntos de cardinalidad $a$, $\binom{b}a$ de que son subconjuntos de a $B$, por lo que ha $\binom{n}a-\binom{b}a$ que no son subconjuntos de a $B$.

Añadido₂: Este límite superior es, sin duda no $f$, sin embargo. Tome $n=5,a=2$, e $b=3$, y de considerar a la familia

$$\left\{\{1,2\},\{3,4\},\{1,5\},\{2,5\}\right\}$$

de dos elementos, subconjuntos de a $S=\{1,2,3,4,5\}$. Si $B$ es un tres elementos subconjunto de $S$ que no contiene ni $\{1,2\}$ ni $\{3,4\}$,$5\in B$, y desde $\{3,4\}\nsubseteq B$, es claro que $B\cap\{1,2\}\ne\varnothing$ y que, por ende, $B$ contiene $\{1,5\}$ o $\{2,5\}$. Así, por $n=5$ tenemos $f(2,3)\le 4$. De hecho,$f(2,3)=4$. Si le $\mathscr{A}$ es una colección de dos elementos, subconjuntos tales que cada tres-elemento subconjunto de $S$ contiene un miembro de $\mathscr{A}$, podemos suponer que la $\{1,2\}\in\mathscr{A}$. Ahora vamos a $B$ ser un tres elementos subconjunto de $S$ tal que $B\cap\{1,2\}=\{1\}$; si $B$ es para contener un miembro de $\mathscr{A}$, debemos tener $B\setminus\{1\}\in\mathscr{A}$. Pero hay $\binom32=3$ posibilidades de $B\setminus\{1\}$, lo $|\mathscr{A}|\ge 4$.

Answer 2

Deje $B$ ser nuestro subconjunto de tamaño $b$, y deje $A$ tienen un tamaño $a$. Por el contrario, podemos encontrar el máximo número de subconjuntos de a $A$ que no estén incluidos en $B$, y, a continuación, para encontrar el número indicado en el problema, sólo tiene que añadir $1$.

Hay $n-b$ elementos fuera de $B$. (Digamos que WLOG que $\{1,2,\dots,n-b \}$ son de fuera de $B$). Requerimos $A$ contienen al menos uno de ellos. El resto de los $a-1$ elementos en $A$ puede ser cualquier cosa.

Mirando los conjuntos de $A$ contiene $1$, $\dbinom{n-1}{a-1}$ de ellos.

Mirando los conjuntos que contengan $2$, y excluyendo las que contienen $1$ debido a que ya hemos contado, hay $\dbinom{n-2}{a-1}$ de ellos.

Así que podemos escribir el total como:

$$\sum_{i=1}^{n-b} \dbinom{n-i}{a-1}$$

Y probablemente hay algunas buenas fórmula que hay para simplificar esto.