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

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|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}$. –  gLre 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
show 2 more comments

1 Answer

up vote 2 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|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 ? –  gLre Jul 9 '12 at 16:13
add comment

Your Answer


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.