Respecto a un resultado sobre el grado de un elemento en una familia de conjuntos finitos.

Question

Tenemos una familia $F = \{S_1, S_2... S_m\} $ de $m$ subconjuntos de $\{1,2...n\} $, todos con la misma cardinalidad. Se nos da que $ \forall a,b \in \cup S_i $, el número de subconjuntos $S_i$ que contienen tanto a $a$ como a $b$ es el mismo, es decir, $|\{S_i : S_i \in F, a \in S_i, b \in S_i\}| = l $, para algún entero fijo $l$.

Necesitamos probar que $ \forall a,b \in \cup S_i $, el número de conjuntos que contienen $a$ es igual al número de conjuntos que contienen $b$. (o $grado(a) = grado(b)$.)

Intenté probarlo por contradicción, asumiendo lo contrario, que existe $a,b \in \cup S_i $ tal que $deg(a) \neq deg(b)$. Sea la familia de conjuntos que contienen $a$ dada por $F_a$. Sabemos que para otro $c \in \cup S_i $, $|F_a| + |F_c| = |F_{a \cup c}| + |F_{a \cap c}| $. Escribiendo esta ecuación para $b$ también y restando, obtenemos

$$ |F_a| - |F_b| = |F_{a \cup c}| - |F_{b \cup c}| $$

Necesitamos probar que el lado derecho de la expresión es cero, pero no sé cómo proceder. ¿Alguna pista?

Answer 1

Decimos que el número $1$ está en $d$ conjuntos, sin perder generalidad, podemos asumir en $S_1, S_2, ... S_d$. Además, supongamos que $|S_i|=k$ para cada $i$ y que cada par $\{x,y\}$ aparece en $l$ conjuntos entre $S_1, ... S_m$.

Luego si contamos las conexiones entre el conjunto $\{2,3,...,n\}$ y los conjuntos $\{S_1,...S_d\}$ obtenemos $$(n-1)l = d(k-1)\implies d = l\cdot{n-1\over k-1}$$ y hemos terminado. Solo tenemos que pensar en la posibilidad de $k=1$.

Claramente podemos decir lo mismo para cada vértice $\ne 1$, por lo que $d$ es el mismo para todos los vértices.