
> 
> 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](http://en.wikipedia.org/wiki/Plotkin_bound) applied to the Hamming distances between these vectors. Are better bounds known?


The usual [Erdős–Ko–Rado](http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Ko%E2%80%93Rado_theorem) 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$](https://math.stackexchange.com/questions/433584/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](http://dx.doi.org/10.1016/0021-8693%2868%2990099-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](http://en.wikipedia.org/wiki/Hadamard_matrix#Sylvester.27s_constructiona), 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.



Better bounds for exact-intersection Erdős–Ko–Rado system?
Your upper bound seems wrong to me.


Let first $n=1$, $X=\{1,2,3,4\}$ and $A\_i=\{1,i\}$ for $i=2,3,4$. Then we have $3>2\cdot 1-1$ subsets of size $2$ intersecting each other in $1$ point.


More generally, for any integer $k>1$ Sylvester constructed a Hadamard matrix of order $2^k$, that is a matrix with $1$ and $-1$ as coefficient, such that all rows are pairwise orthogonal. One can take the first row to be all $1$ and let $n=2^{k-2}$, so that all subsequent rows have $2n$ positive coefficients, and two of them must share exactly $n$ coefficient. Letting you subset be defined by positive coefficients of the rows of such a matrix gives you an example of size $4n-1$.


Moreover, it is conjectured that Hadamard matrices exist in all dimension multiple of $4$, which would mean that $N\geq 4n-1$. Sylvester construction already shows that this holds for powers of $2$.


