most recent 30 from http://mathoverflow.net 2013-05-22T07:29:21Z http://mathoverflow.net/feeds/question/101696 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101696/lower-bound-of-the-size-of-a-collection-of-subsets-with-a-intersecting-property gLre 2012-07-08T19:34:36Z 2012-07-09T10:00:34Z

<p>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}}$.</p> <p>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 ?</p>

http://mathoverflow.net/questions/101696/lower-bound-of-the-size-of-a-collection-of-subsets-with-a-intersecting-property/101760#101760 Boris Bukh 2012-07-09T10:00:34Z 2012-07-09T10:00:34Z

<p>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 <code>$S'=S\setminus\{x\}$</code> where $x$ is any element of $S$. The result is the family <code>$\mathcal{F}'=\mathcal{F}\cup \{S'\}\setminus \{S\}$</code> 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$.</p>