Family Of Sets Intersecting once

[Robert1986]

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

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 $|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?

 

[mighty2000]

Hello,

Thank you for sharing this interesting problem. It seems like you have already made some progress in your approach by considering the subset lattice. However, I would suggest trying to approach this problem from a different angle.

One approach could be to use the pigeonhole principle. Since we have n subsets, and each subset can have at most n elements, we can think of each element as a pigeon and each subset as a pigeonhole. If we can show that there are more pigeons than pigeonholes, then we can conclude that at least one pigeonhole must have more than one pigeon. In other words, there must be at least two subsets with a common element.

Another approach could be to use induction. We can start with the base case of n=2, where we have two subsets of {1,2} and the total number of elements is 2. Then, for the inductive step, we can assume that the statement is true for n=k and try to prove it for n=k+1. This would involve showing that if we add one more subset to the collection, the total number of elements cannot exceed (k+1)√(k+1).

I hope these suggestions are helpful. Good luck with solving this problem!