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.

Let $A=\{1, 2,\dots,n\}$ What is the maximum possible number of subsets of $A$ with the property that any two of them have exactly one element in common ?

I strongly suspect the answer is $n$, but can't prove it.

share|improve this question
    
I think answer should be n but i m not sure –  kalpeshmpopat Mar 20 '13 at 15:33
1  
Well, {1}, {1,2}, {1,3}....{1,n} form such a collection of n subsets. The subsets don't have to have the same cardinality. –  Cosmonut Mar 20 '13 at 15:35
2  
I would like to point out that most of the answers are missing the case $\{1, 2\}, \{2, 3\}, \{3, 1\} $, so there is an error in their logic. –  Calvin Lin Mar 20 '13 at 16:14
1  
@Inceptio No, but as Thomas mentioned, you can for $n = 13$. I.e. the projective plane of order 3. –  Calvin Lin Mar 20 '13 at 16:24
1  
@Thomas I've undeleted it. –  Thomas Andrews Mar 20 '13 at 21:10

3 Answers 3

up vote 5 down vote accepted

This is a well known type of problem in combinatorics. (Try googling "exact intersections".) The (slight) generalisation of your claim, in which we require $|A\cap B|=\ell>0$ whenever $A\neq B$, is apparently due to Fisher.

Let $\mathcal{A}$ be a family of subsets of $\{1,2,\dots,n\}$ such that for every two distinct $A,B\in\mathcal{A}$ we have $|A\cap B|=\ell$. We claim $|\mathcal{A}|\leq n$. Certainly we're done if some $A\in\mathcal{A}$ has size $\ell$ (this is where we use $\ell>0$), so assume otherwise.

For each $A\in\mathcal{A}$ consider the "indicator vector" $1_A\in\mathbf{R}^n$ given by $1_A(x)=1$ if $x\in A$ and $0$ otherwise. I claim that $\{1_A : A\in\mathcal{A}\}$ is a linearly independent set, so $|\mathcal{A}|\leq n$.

Suppose $\lambda_A\in\mathbf{R}$ are some coefficients such that

$$\sum_{A\in\mathcal{A}} \lambda_A 1_A = 0.$$

Taking the scalar product with $1_B$, noting $1_A\cdot 1_B = \ell$ when $A\neq B$, we have

$$\lambda_B |B| + \sum_{A\neq B} \lambda_A \ell = 0.$$

Rearranging slightly,

$$\lambda_B (|B| - \ell) = - \ell\sum_{A\in\mathcal{A}} \lambda_A.$$

Conclusion: either $\sum\lambda_A = 0$, in which case every $\lambda_B=0$ (since $|B|>\ell$ for all $B\in\mathcal{A}$), or $\sum\lambda_A\neq 0$, in which case all $\lambda_B$ are nonzero and opposite in sign to $\sum\lambda_A$, impossible.

share|improve this answer
    
Yes, I mean the {scalar,dot,inner,...}-product. –  Sean Eberhard Mar 20 '13 at 21:13
    
Wait, $\lambda_B$ are not all equal, but rather $\lambda_B=\frac{1}{|B|-\ell}C$? If all the $|B|$ are equal, clearly it is true that the $\lambda_B$ are equal, but we can't conclude that here, can we? –  Thomas Andrews Mar 20 '13 at 21:15
    
Ah, thanks, correcting now. –  Sean Eberhard Mar 20 '13 at 21:16
    
What we really know is that they are all the same sign, since $|B|>\ell$, which is enough. –  Thomas Andrews Mar 20 '13 at 21:17
    
nice proof .... –  wece Mar 20 '13 at 21:19

Hint: For a set of length $i > 2$, no other set can have any subset of that set $i \ge 2$ as a subset.

share|improve this answer

[Undeleting to show ideas, not because this is a valid or complete answer.]

Let $S_1,S_2,\dots,S_m$ be a sequence of non-empty sets such that when $i\neq j$, we have $|S_i\cap S_j|=1$. Then we want to prove that:

$$\left|\bigcup S_i\right| \geq m$$

Let $S=\cup S_i$. For any $x\in S$, define $n_x=\left\{i:x\in S_i\}\right|$. Then we can show the following pretty easily:

$$\sum_{x\in S} n_x = \sum_{i=1}^m |S_i|$$ $$\sum_{x\in S} \binom{n_x}{2} =\binom m 2$$ $$\binom{|S|}{2} \geq \sum_{i=1}^{m} \binom{|S_i|}{2}$$

The first counts pairs $(x,i)$ with $x\in S_i$ in two ways. The second counts pairs $i,j\in\{1,\dots,m\}$ in two ways. The last is a result of any pair in $S$ being contained in at most one $S_i$.

We can assert $n_x>1$ for all $x$ because if $n_x=1$ for any $x$ we can remove that one $x$ and the one $S_i$ and get a counter-example with a smaller $m$.

If there is any non-empty $J\subsetneq I=\{1,\dots,m\}$ such that $$|\bigcup_{j\in J} S_j|< |J|$$ we'd also have a smaller counterexample. So we can assume that $\left|\bigcup_{j\in J} S_j\right|\geq |J|$ for all $\emptyset\neq J\subsetneq I$.

In particular, this means that $|S|\geq m-1$. Since we assume we have a counterexample, that means that $|S|=m-1$.

But this also means that for any $J\subsetneq I$ we can find a set of distinct representatives $x_{i}\in S_i$ with when $i\in J$, by the Hall's marriage theorem.

Fixing $k\in I$, we jet $J_k=I\setminus\{k\}$. then we have a set of $m-1$ distinct elements $\{x_i:i\neq k\}$ with $x_i\in S_i$. Since we assume our entire set has no such element, we have that $\{x_i\}=\cup_{j\in I} S_j$.

I'm still not seeing it.

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.