Número de subconjuntos de tamaño$k$ cuya intersección por pares es de un tamaño dado j

Question

Deje $j<k<n$ número natural. Se sabe cuál es el tamaño máximo de un conjunto $A$ tal que $A\subseteq \mathcal P(\{1,\ldots,n\})$ el juego de poder de $\{1,\ldots,n\}$ $\forall x,y\in A$ tenemos $|x|=k$$|x\cap y|=j$?

Por ejemplo, supongamos $n=9, k=3, j=1$. A continuación, $A=\{\{1,2,3\},\{3,4,5\},\{3,6,7\},\{3,8,9\}\}$ es máxima para las condiciones dadas, pero no tiene la talla máxima (usted puede encontrar un conjunto de tamaño $7$ que cumple con todas las hipótesis).

Muchas gracias!

PS: otra manera de decirlo: vamos a $j<k<n$. ¿Cuál es el tamaño máximo de un conjunto $A\subseteq M_n(\mathbb C)$ tal que $\forall x,y\in A$ tenemos que $x,y,xy$ son proyecciones, $tr(x)=\frac{k}{n}$$tr(xy)=\frac{j}{n}$.

Answer 1

Esto no es una respuesta completa, pero le da un consolidado inicial.

Si $j=0$, entonces la respuesta es claramente $ \lfloor \frac{n}{k} \rfloor$. De ahora en adelante, vamos a $j\neq 0$. Tenga en cuenta también que $j<k<n$, lo $n \geq 3$.

Si $2k-j > n$, entonces el tamaño máximo es de 1. De lo contrario, si $2k-j\leq n$, podemos encontrar al menos 2 juegos fácilmente. De ahora en adelante, se supone que el tamaño máximo es de al menos 2.

Deje $A$ ser un conjunto que satisface sus condiciones. Deje $|A| = m \geq 2$. Deje $B$ $n \times m$ incidencia de la matriz, donde las filas corresponden a los elementos de $[n]$ y las columnas corresponden a los elementos de $A$.

Deje $C = B^T B$. Esta es una $m \times m$ matriz que ha $k$ en la diagonal y $j$ en todas las demás. Sabemos que es determinante es $(m-1) k^{m-1} j$, por lo tanto no es cero. Por lo tanto,

$$m = rank (C) \leq \min( rank(B^T), rank (B) ) \leq n$$

---

Por supuesto, esta obligado no dar el máximo. Por ejemplo, si $2k-j=n$,$m=2$, independientemente del tamaño de los otros parámetros.