# Distinctness is maintained after adding some element to all sets

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?

-
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

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.

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

-
Thank you, now its also clear why the topic is graph theory. –  Listing Jan 11 '11 at 19:55
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