What is the largest possible number of subsets of a $4n$-element set $X$, such that each subset contains precisely $2n$ elements, and such that each of the pairwise intersections of the subsets has precisely $n$ elements?
The best bounds I have for the maximal size $N$ of such a set system are $\lfloor \log_2 n \rfloor \le N \le 8n-1$ (corrected: was $2n-1$). The lower bound is by a tree-like construction based on the characteristic vectors of the subsets relative to $X$, while the upper bound comes from the Plotkin bound applied to the Hamming distances between these vectors. Are better bounds known?
The usual Erdős–Ko–Rado setup involves the size of the intersections being of at least some size, whereas here they are precisely $n$. The EKR upper bounds are exponential in $n$ as they allow many possible set systems where the intersections have different sizes, while a linear upper bound appears to be available for this case. So this seems like it should be a well known example, and I would appreciate a pointer if this is the case.
This is a reformulation of a question from Math.SE, Number of binary strings of length $n$ with Hamming distance $n/2$, based on my answer to that question. I am interested in such set systems for general values; the $4n/2n/n$ case avoids some of the distracting details.
Edit: upon investigation of the history of the Frankl-Wilson theorem, it seems that a better upper bound is due to Ryser: $N \le 4n$. This applies as long as the common size of intersections is at least 2 and less than the size of the subsets. Thanks go to Joshua Erde, Gerry Myerson and Ben Millwood for suggesting Frankl-Wilson for the upper bound.
- H. J. Ryser, An Extension of a Theorem of de Bruijn and Erdös on Combinatorial Designs, Journal of Algebra 10 246–261, 1968. doi:10.1016/0021-8693(68)90099-9
Thanks also to Benoît Kloeckner for pointing out a rescaling error. Benoît also pointed out that a better lower bound of $4n-1$ exists if $n$ is a power of 2, by Sylvester's construction of Hadamard matrices, and that the existence of Hadamard matrices of every multiple of 4 (which is the Hadamard conjecture) would imply a general lower bound of $4n-1$.
So, assuming the Hadamard conjecture, $4n-1 \le N \le 4n$. If the conjecture is false, the maximum number of rows of a Hadamard-like matrix with $4n$ columns provides a lower bound for $N$.
It is interesting that there remains a gap between lower and upper bounds, even assuming the Hadamard conjecture. A set system with $N=4n$ would correspond to a Hadamard-like matrix with $4n$ columns and $4n+1$ rows.