Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are n elements. What is the maximum number of subsets chosen at any one time so that every pair of subsets from collection intersect?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

This problem is classical, and has a surprisingly trivial solution. Let $[n]=\lbrace 1,\ldots, n\rbrace$. Then $\mathcal{P}([n])$ (the set of all subsets of $[n]$) has size $2^n$. Say that $\mathcal{A}\subset\mathcal{P}([n])$ is intersecting if $A,B\in\mathcal{A}$ implies $A\cap B \ne \emptyset$.

Claim: Every maximal intersecting $\mathcal{A}\subset\mathcal{P}([n])$ contains exactly $2^{n-1}$ sets.

Proof: The upper bound is trivial: if $\mathcal{A}$ contains more than $2^{n-1}$ sets then it contains both $A$ and $A^c$ for some $A\subset[n]$. Now suppose that $\mathcal{A}$ is maximal intersecting, so that we can't add any set to $\mathcal{A}$ without destroying the intersecting property. Certainly $\mathcal{A}$ is an upset, i.e., if $A\in\mathcal{A}$ and $A\subset B$ then $B\in\mathcal{A}$. Suppose $A\notin\mathcal{A}$. Then by maximality there exists $B\in\mathcal{A}$ such that $A\cap B = \emptyset$, i.e., $B\subset A^c$, so $A^c\in\mathcal{A}$.

share|improve this answer
    
See, e.g., Bollobas Combinatorics. –  Sean Eberhard Aug 26 '12 at 19:28
    
Actually I think the number should be $2^{\max(n-1,0)}$, which is always integer. Think of it! –  Marc van Leeuwen Aug 27 '12 at 7:26
    
@MarcvanLeeuwen If $n=0$ shouldn't the maximum be $0$ actually? I guess it depends on what you mean by a "pair" of subsets: can you take the same set twice? (Note $\emptyset\cap\emptyset=\emptyset$.) –  Sean Eberhard Sep 3 '12 at 15:13

As Sean Eberhard says, if $\mathcal{A}$ contains more than $2^{n−1}$ subsets of $[n]$ then it contains at least one pair of complementary subsets, so $2^{n−1}$ is an upper bound for $n\ge 1$.

It is easy to construct an example meeting this upper bound: simply let $\mathcal{B}\subset\mathcal{P}([n])$ contain just those subsets of $[n]$ which have $n$ as an element. $\mathcal{B}$ clearly contains $2^{n-1}$ subsets of $[n]$ and the intersection of any positive number of them contains $n$.

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.