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

Let $S=\lbrace 1,2,3,\ldots, 2^n\rbrace$ for some $n\ge 2$. What is the maximum cardinality of a set $S'$ of $2^{n-1}$-element subsets of $S$ such that every pair of elements of $S'$ has exactly $2^{n-2}$ elements in common?

The answer might be $2^n - 1$. This problem came up a while ago while I was working on something larger. I skirted around it, but it always bugged me.

share|improve this question
3  
Certainly Hadamard designs (related to Hadamard matrices) will give that as a lower bound. If you view it as a combinatorial linear algebra problem, I think that will give you an exact answer. Gerhard "Don't Ask For Linear Algebra" Paseman, 2013.03.27 –  Gerhard Paseman Mar 27 '13 at 17:04
    
Look up Frankl--Wilson, and Ray--Chaudhury--Wilson theorems. –  Boris Bukh Mar 27 '13 at 17:41

1 Answer 1

up vote 4 down vote accepted

To flesh out the Hadamard matrix proof:

  1. Suppose the desired number is $m - 1$.
  2. Fill in the top row of an $m\times 2^n$ matrix with all $1$.
  3. Each subsequent row represents an element of $S'$. If $i$ is in the $j^{th}$ element of $S'$, then the matrix entry $(j+1,i)$ is $1$, and otherwise $-1$.
  4. The rows are orthogonal to each other.
  5. Orthogonal sets are linearly independent.
  6. The largest linearly independent set has cardinality equal to the dimension, which here is $2^n$ since that is the length of our row vectors.
  7. Thus our number is $m-1=2^n -1$.
  8. Not too hard to show that such a matrix exists. For example, see Sylvester's construction http://en.wikipedia.org/wiki/Hadamard_matrix#Sylvester.27s_construction
share|improve this answer

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.