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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
I think answer should be n but i m not sure – kalpeshmpopat Mar 20 '13 at 15:33
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
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
@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
@Thomas I've undeleted it. – Thomas Andrews Mar 20 '13 at 21:10
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|cite|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|cite|improve this answer

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.