# Number of subsets of size $k$ whose pairwise intersection is of given size j

Let $j<k<n$ be natural number. Is it known what is the maximum size of a set $A$ such that $A\subseteq \mathcal P(\{1,\ldots,n\})$ the power set of $\{1,\ldots,n\}$ and $\forall x,y\in A$ we have $|x|=k$ and $|x\cap y|=j$?

For example, let $n=9, k=3, j=1$. Then $A=\{\{1,2,3\},\{3,4,5\},\{3,6,7\},\{3,8,9\}\}$ is maximal for the given conditions, but does not have maximal size (you can find a set of size $7$ that respects all the hypothesis).

Thanks a lot!

PS: another way to say it: let $j<k<n$. What is the maximal size of a set $A\subseteq M_n(\mathbb C)$ such that $\forall x,y\in A$ we have that $x,y,xy$ are projections, $tr(x)=\frac{k}{n}$ and $tr(xy)=\frac{j}{n}$.

• I think you mean $A$ is a subset of the powerset of $\{1,\dots ,n\}$? – TheNumber23 Sep 27 '13 at 5:57
• Yes, modified! Thanks. – Alessandro Vignati Sep 27 '13 at 6:03
• Determining the exact value of the maximum is a hard (and unsolved) problem in general. For example, if $n=t^2+t+1$, $k=t+1$, and $j=1$, then the question of whether or not a collection of $n$ subsets exists is equivalent to the existence of a projective plane of order $t$. These are known to exist for $t$ that are prime powers, but determining whether they exist or not for other $t$ has been a notorious open problem for decades (even the case $t=12$ is still open). – Kevin P. Costello Sep 27 '13 at 18:28
• I see, I did not know about this problem. My problem is a little more specific, actually, and can be stated as a conjecture: let $n=2^{n_1}3^m$, $k=\frac{n}{3}$ and $j=\frac{k}{3}$. If you fix $m$, it is true that for every $n_1$ we have that this number is the same? Why this conjecture appeared to me? Let $n=9$, $k=3$ and $j=1$. Then this number is $7$. Let $n=18$, $k=6$ and $j=2$. Guess what? It appears to be $7$. Let $n=36$, $k=12$, $j=4$.. well..I'm really not able to find more than $7$ of them.. – Alessandro Vignati Sep 27 '13 at 20:16

This is not a complete answer, but gives you an initial bound.

If $j=0$, then the answer is clearly $\lfloor \frac{n}{k} \rfloor$. Henceforth, let $j\neq 0$. Note also that $j<k<n$, so $n \geq 3$.

If $2k-j > n$, then the maximal size is 1. Otherwise, if $2k-j\leq n$, we can find at least 2 sets easily. Henceforth, assume that the maximal size is at least 2.

Let $A$ be a set which satisfies your conditions. Let $|A| = m \geq 2$. Let $B$ be the $n \times m$ incidence matrix, where the rows correspond to elements $[n]$ and the columns correspond to elements of $A$.

Let $C = B^T B$. This is a $m \times m$ matrix that has $k$ on the diagonal and $j$ everywhere else. We know that it's determinant is $(m-1) k^{m-1} j$, hence is non-zero. Thus,

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

Of course, this bound does not give you the maximum. For example, if $2k-j=n$, then $m=2$, regardless of the size of the other parameters.