- #1

- 828

- 2

## Homework Statement

This isn't exactly a homework question, but I saw it in a book, and I think it is interesting:

Let [itex] S_1,\ldots,S_n[/itex] be a collection of subsets of [tex]\{1,\ldots,n\}[/itex] such that [itex]|S_i \cap S_j| \leq 1[/itex] whenever [itex]i\neq j[/itex]. Then the total number of elements in all of the lists is less than or equal to [itex] n\sqrt{n}[/itex].

## Homework Equations

## 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 [itex]|S_i \cap S_j| > 1[/itex]. 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: