# Family Of Sets Intersecting once

## Homework Statement

This isn't exactly a homework question, but I saw it in a book, and I think it is interesting:
Let $S_1,\ldots,S_n$ be a collection of subsets of [tex]\{1,\ldots,n\}[/itex] such that $|S_i \cap S_j| \leq 1$ whenever $i\neq j$. Then the total number of elements in all of the lists is less than or equal to $n\sqrt{n}$.

## The Attempt at a Solution

So, I thought about looking at the subset lattice, particularly the \sqrt{n} +1 level. I want to show that every collection of n-sets from this level has at least two such that $|S_i \cap S_j| > 1$. Like I said, this isn't a homework problem, but it looks interesting. Also, the book says that it should be "easy" but I just can't seem to get it. Any ideas?

Last edited:

## Answers and Replies

Related Calculus and Beyond Homework Help News on Phys.org