Welcome to MathOverflow

Question

1

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 ?

edited Jul 9 at 8:42

asked Jul 8 at 19:34

gLre
105●4

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 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 at 1:33

I guess $C_n^{n/2}$ denotes $\binom{n}{n/2}$. – Dima Pasechnik Jul 9 at 3:15

1

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 at 8:41

2

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 at 9:28

show 2 more comments

Boris Bukh · Accepted Answer · 2012-07-09 10:00:34Z UTC

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

Lower bound of the size of a collection of subsets with a intersecting property

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.