Una familia "distintiva" de subconjuntos

Question

Supongamos $A$ es un conjunto finito, $B$ es una colección de subconjuntos de $A$, que satisface la siguiente condición:

$$\forall a, b \in A, a \neq b: \exists C \in B: (a \in C) \land (b \notin C)$$

¿Cuál es el mínimo tamaño posible de $B$.

En la actualidad, sé que el tamaño mínimo de $B$ es de no menos de $\lceil \log_2 |A| \rceil$ (por el principio del palomar), y que no exceda el $2\lceil \log_2 |A| \rceil$ (un ejemplo de que tamaño puede ser trivialmente que se construye). Sin embargo, yo no sé la respuesta exacta a la pregunta.

Answer 1

Una mejora de límite superior está dado por el menor $n$ tales que

$$\binom{n}{\lfloor n/2 \rfloor} \geq |A| \enspace.$$

Para $A = \{a,b,c,d,e\}$, obtenemos $n=4$ y, por ejemplo, la siguiente codificación: $$\begin{array}{c|c} a & 1100 \\ b & 1010 \\ c & 1001 \\ d & 0110 \\ e & 0101 \end{array}$$ La lectura de las columnas de la tabla, $B_1 = \{a,b,c\}, B_2 = \{a,d,e\}, B_3 = \{b,d\}, B_4 = \{c,e\}$. Puesto que cada elemento de $A$ aparece en el mismo número de subconjuntos, y no hay dos elementos aparecen en el mismo subconjuntos, se cumple con la condición.

Answer 2

La respuesta por @FabioSomenzi no es sólo un límite superior - es realmente apretado.

• Definir $S(a) = \{C \in B: a \in C\}$ para todos los $a \in A$. Tenga en cuenta que $S(a) \subset B$.

• La condición principal $\forall a\neq b: \exists C \in B: a \in C \land b \notin C$ hace $\forall a\neq b: S(a) \not\subset S(b)$

• Por lo tanto, los conjuntos de $S(a)_{a\in A}$ formar un Sperner familia de tamaño $|A|$.

• El resultado se sigue ahora de Sperner del teorema, que el máximo tamaño de Sperner familia formada por subconjuntos de $B$ tiene el tamaño de ${|B| \choose |B|/2}$

---

ACTUALIZACIÓN 2019-05-29: vamos a ver si podemos obtener una estimación del coeficiente. Usando la aproximación de Stirling $n! \sim \sqrt{2 \pi n} ({n \over e})^n$, tenemos

$${n \choose n/2} = {n! \over (n/2)! (n/2)!} \sim {\sqrt{2 \pi n} ({n \over e})^n \over \sqrt{\pi n} ({n/2 \over e})^{n/2} \sqrt{\pi n} ({n/2 \over e})^{n/2}} = \sqrt{2 \over \pi n} 2^n > |A|$$

Así asintóticamente tenemos $n \sim \log_2 |A|$, es decir, el coeficiente de es $1$, es decir, el palomar-basado límite inferior es bastante ajustado.