# Problem about subsets of $\{1, 2,\dots,n\}$

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.

-
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

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.

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

-

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

-