Number of combinations with small intersection

Question

I have set $S$ of $n$ elements. I want to understand, in how many ways can I choose $n/2$ elements - let each such choice be set $S_i$ - such that no two choices have more than $n/4$ elements in common i.e $|S_i\cap S_j|\leq n/4$. I have been thinking about it and I think that it should be (polynomial) function in $n$ - for $n=4$, it is $6$, for $n=8$, I could write $10$ ways, but I don't have an expression for general growth. Any approach on how to proceed would appreciated.

Answer 1

What you are looing for is known in the literature as a constant weight binary bode with length $n$, weight $n/2$ and distance $n/2$, if you interpret your subsets as binary vectors of length $n$.

One type of such code is constructed by taking a Hadamard matrix of order $n$, ignoring the row of all ones, and for each of the remaining $n-1$ rows, including two subsets: one corresponding to the locations of the $+1$'s, and the other for the locations of the $-1$'s. This shows that as long as a Hadamard matrix of order $n$ exists, then you can get $2n-2$ subsets. This confirms what you found for $n=4$. When $n=8$, you can get $14$ subsets: take the list of seven subset below, together with their complements.

(1, 2, 3, 4), 
(1, 2, 5, 6), (1, 3, 5, 7), (1, 4, 5, 8)
(1, 2, 7, 8), (1, 3, 6, 8), (1, 4, 6, 7)

It is conjectured that there exists a Hadamard matrix of order $n$ whenever $n$ is a multiple of $4$. This conjecture has been confirmed for all but $13$ possible orders up to $2000$. Furthermore, I do not know if these Hadamard matrix based codes are optimal. According to this table of optimal constant weight binary codes, the optimal constant weight codes with parameters $(n,n/2,n/2)$ are indeed achieved by the Hadamard construction for $n\le 32$.