Better bounds for exact-intersection Erdős–Ko–Rado system?

Question

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.

Answer 1

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

Answer 2

The Frankl-Wilson theorem gives you some bounds in this sort of set up:

Let $p$ be a prime. $\mathcal{A} \subset [n]^{(r)}$ such that for all $A,B \in \mathcal{A}$, $|A \cap B| \equiv \lambda_i$ mod $p$ for some $\{\lambda_1 , \ldots \lambda_s\}$ where $\lambda_i \neq r$ mod $p$. Then $|\mathcal{A}| \leq {n \choose s}$.

A quick consequence of this theorem is the Ray-Chaudhury-Wilson theorem, that is let $\mathcal{A} \subset [n]^{(r)}$ such that for all $A,B \in \mathcal{A}$, $|A \cap B| \in L$ for some $L \subset \{0,1,\ldots,r-1\}$, with $|L|=s$. Then $|\mathcal{A}| \leq {n \choose s}$, which can be seem by picking some $p > r$ and applying the previous theorem.

Unfortunately this gives a worse bound than your current upper bound when we take $n=4m$, $r=2m$ and $L=\{m\}$, but possibly it's of more use in the general case.

Answer 3

It seems that for every $n$ there is an upper bound of $N \le 4n-1$. Let $X = \{1,2,\ldots, 4n\}$. One can associate for each subset $A\subseteq X$ a vector $v_A \in \{-1,1\}^{4n}$ as follows: $v_A(i) = 1$ iff $i \in A$. Consider a family of subsets, where each subset is of size $2n$, and the size of the intersection of each two subsets is exactly $n$. This implies that the vectors associated with the subsets are orthogonal over the reals. In addition, these vectors are also orthogonal to the vector $1^{4n}$, hence there are at most $4n-1$ such vectors.

Answer 4

Here is a proof that $|X| \leq 4n-1$. Given your system $X$, let $\chi_1 , \ldots, \chi_N \in \mathbb{R}^{4n}$ be the characteristic vectors of the elements of $X$. Then \begin{equation*} \chi_i \cdot \chi_k = \begin{cases} 2n & i = k \\ n & i \neq k . \end{cases} \end{equation*} Let $j \in \mathbb{R}^{4n}$ denote the all ones vector and consider the vectors $$(2 \chi_1 - j) , \ldots , (2 \chi_N - j), j.$$ These are vectors with $\pm 1$ entries and an easy calculation reveals they are pairwise orthogonal. Thus these are $N+1$ vectors in $\mathbb{R}^{4n}$ that are linearly independent so $N+1 \leq 4n$.

The tensor product of two Hadamard matrices is again a Hadamard matrix. As mentioned before, one can construct a Hadamard matrix for all powers of 2 by taking the tensor product of $$\left(\begin{array}{rr} 1 & 1 \\ 1 & -1 \end{array}\right)$$

Many constuctions of Hadamard matrices are known and they are known to exist if $4n < 668$ and it is an important conjecture in combinatorics that they exist for all values of $4n$. One easy construction I will mention here is take $p \equiv 3 \mod 4$ and define the $p \times p$ matrix, $Q$, as follows $$Q_{ij} = \left(\frac{i-j}{p}\right).$$ Then $$\left(\begin{array}{rr} 1 & j^T \\ j & Q - I \end{array}\right),$$ is a Hadamard matrix.