Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
Actually, Frankl-Wilson with $p > n$ and $s=1$ gives an upper bound of $n$. –  András Salamon Jul 2 '13 at 12:21
    
Possibly there was a confusion of notation. We do get an upper bound of $n=4m$, however this was worse than the claimed upper bound of $2m$ (but I see this has now changed). –  Joshua Erde Jul 3 '13 at 0:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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