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}$.

  • $\begingroup$ I think you mean $A$ is a subset of the powerset of $\{1,\dots ,n\}$? $\endgroup$ – TheNumber23 Sep 27 '13 at 5:57
  • $\begingroup$ Yes, modified! Thanks. $\endgroup$ – Alessandro Vignati Sep 27 '13 at 6:03
  • $\begingroup$ 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). $\endgroup$ – Kevin P. Costello Sep 27 '13 at 18:28
  • $\begingroup$ 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.. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.