MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following question is a open question related to coding theory : What is the maximal size of a collection of $(\frac{n}{2} + 1)$-elements subsets of an n-element set such that each pair of subsets has at most $\frac{n}{2}-1$ elements in common ? We just have lower bound which is : $(\frac{1}{n} + O(\frac{1}{n^2})){n \choose {n/2}}$.

Now, instead of uniform subset, if we consider a collection of subsets with at least $\frac{n}{2} + 1$ elements such that each pair of subsets has at most $\frac{n}{2}-1$ elements in common, do we have a better lower bound for the size of the collection ?

share|cite|improve this question
I think an argument similar to that for Sperner's Lemma on antichains may be useful. However, I do not understand the lower bound. I would think n choose n/2 to be an upper bound, and that seems less than your lower bound. Gerhard "Ask Me About System Design" Paseman, 2012.07.08 – Gerhard Paseman Jul 9 '12 at 0:29
Does $C_n^{n/2}$ denote the Catalan number $\frac{1}{1+n/2}{n\choose n/2}$? – Patricia Hersh Jul 9 '12 at 1:33
I guess $C_n^{n/2}$ denotes $\binom{n}{n/2}$. – Dima Pasechnik Jul 9 '12 at 3:15
Oh, I am really sorry, I wanted to say : the maximal size of such a collection if lower bounded by $(\frac{1}{n} + O(\frac{1}{n^2}))C_n^{n/2}$ instead of $(1+ \frac{1}{n} + O(\frac{1}{n^2}))C_n^{n/2}$... And yes, $C_n^k$ actually denotes ${n \choose k}$. – user22579 Jul 9 '12 at 8:41
There is an easy lower bound by partitioning subsets of $\lbrace 0, ..., n-1 \rbrace$ of size $\frac n 2 + 1$ by their sums mod $n$. At least one collection has ${n \choose 1 + n/2}/n$ elements. There is an easy upper bound by considering the $\frac n 2 + 1$ subsets of size $\frac n 2$ within each subset. This upper bound of ${n \choose n/2}/(\frac n 2 + 1)$ only differs by about a factor of $2$ from the lower bound. – Douglas Zare Jul 9 '12 at 9:28
up vote 1 down vote accepted

The two problems are equivalent. Indeed, let $\mathcal{F}$ be the family of sets of size at least $n/2+1$ such that no two sets have $n/2$ elements in common. Clearly, such an $\mathcal{F}$ cannot contain two sets $S,T$ such that $S\subset T$. If there is a set $S\in \mathcal{F}$ of size greater than $n/2+1$, then replace it by a set $S'=S\setminus\{x\}$ where $x$ is any element of $S$. The result is the family $\mathcal{F}'=\mathcal{F}\cup \{S'\}\setminus \{S\}$ which has the same size as $\mathcal{F}$, and satisfies the same condition. Repeat as long as there are sets of size greater than $n/2+1$.

share|cite|improve this answer
You are right, thank you for the response. Now, if we allow that for each pair $(S,T)$ in the family : either their intersection has at most $\frac{n}{2} -1$ elements, either ($S \subset T $ or $T \subset S$) ? With such property, we can't shift like previously, but do you think we can have much more subsets (in asymptotic way ?) in the family ? – user22579 Jul 9 '12 at 16:13

Your Answer


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