Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $S=\{S_1,S_2,\ldots,S_n\}$ be a set of $n$ distinct subsets with $S_i \subseteq \{1,\ldots,n\}$ for $i=1,\ldots, n$ then $k \in \{1,\ldots,n\}$ exists with $S_i \cup \{k\}$ is distinct for $i=1,\ldots,n$.

I found this in a old problem sheet of mine about sets and graph theory. Is there a elegant solution to this problem?

share|improve this question
    
Perhaps you mean $S_i \cup \{k\}$ are distinct? Curly brackets need to be escaped in laTex as otherwise they are interpreted as bracketing an arbitrary laTex expression. –  hardmath Jan 11 '11 at 19:03
    
Thank you, I missed this mistake of mine. –  Listing Jan 11 '11 at 19:04

2 Answers 2

up vote 9 down vote accepted

This result follows from Bondy's theorem (in fact, it is equivalent) which states that,

Given $\displaystyle n$ distinct sets $\displaystyle S_1, S_2, \dots, S_n$, each a subset of $\displaystyle \{1,2, \dots, n\}$, there is a set $\displaystyle A \subset \{1,2, \dots, n\}$, with $\displaystyle |A| \leq n-1$ such that the sets $\displaystyle S_i \cap A$ are all distinct.

Pick a $\displaystyle k \notin A$. Then we have that if $\displaystyle S_i \cup \{k\} = S_j \cup \{k\}$, then $\displaystyle (S_i \cup \{k\}) \cap A = (S_j \cup \{k\}) \cap A$. Since $\displaystyle k \notin A$, it follows that $\displaystyle S_i \cap A = S_j \cap A$ contradicting the result of Bondy's theorem.

You can find a short proof and a sketch of an elegant linear algebra proof (originally due to Babai and Frankl) of Bondy's theorem, in the excellent book, Extremal Combinatorics by Stasys Jukna.

share|improve this answer
    
Good to know... Anyway, it doesn't make a big difference, that's why I deleted it. Your argument is really nice! –  t.b. Jan 12 '11 at 5:30
    
@THeo: Yeah, I suppose it is minor. Thanks! –  Aryabhata Jan 12 '11 at 5:36
    
Thank you for this find :-), Great –  Listing Jan 12 '11 at 7:47

THIS IS INCORRECT

Suppose that this wasn't the case. Then for each $k \in \{1, \dots, n\}$ you can find $S_a \subset S_b$ such that $S_b \setminus S_a = \{k\}$.

Consider a directed graph where the $n$ vertices correspond to the sets and there is an edge from $S_a$ to $S_b$ if and only if $S_b \setminus S_a$ consists of exactly one element. Clearly there won't be any loops so it is a forest with at most $n-1$ edges. Now by pigeonhole principle one of the edges must get two $k$s which is impossible.

share|improve this answer
    
Thank you, now its also clear why the topic is graph theory. –  Listing Jan 11 '11 at 19:55
6  
This does not look right. $S = \{ \{1\}, \{1,2\}, \{1,3\}, \{1,2,3\} \}$. There are 4 edges here. Also, you are constructing a directed graph and then claiming no cycles implying $n-1$ edges, which is not true for directed acyclic graphs. If you are constructing an undirected graph, the description seems wrong and the example in this comment shows there can be loops. –  Aryabhata Jan 11 '11 at 20:40
    
You are right, Moron. I was too hasty answering this. –  J. J. Jan 12 '11 at 5:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.