Family Of Sets Intersecting once

  • Thread starter Robert1986
  • Start date
  • #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:

Answers and Replies

Related Threads on Family Of Sets Intersecting once

  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
7
Views
6K
  • Last Post
Replies
1
Views
2K
Replies
6
Views
2K
Replies
4
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
10
Views
9K
  • Last Post
Replies
1
Views
847
  • Last Post
Replies
1
Views
490
Top