12
$\begingroup$

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?

  • 0
    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.2011-01-11
  • 0
    Thank you, I missed this mistake of mine.2011-01-11

2 Answers 2

9

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.

  • 0
    Good to know... Anyway, it doesn't make a big difference, that's why I deleted it. Your argument is really nice!2011-01-12
  • 0
    @THeo: Yeah, I suppose it is minor. Thanks!2011-01-12
  • 0
    Thank you for this find :-), Great2011-01-12
2

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.

  • 0
    Thank you, now its also clear why the topic is graph theory.2011-01-11
  • 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.2011-01-11
  • 0
    You are right, Moron. I was too hasty answering this.2011-01-12