1
$\begingroup$

Consider $n$ distinct sets , $A_1,A_2,A_3...A_n$ on $[n]$. Prove that there is an $x\in[n]$ such that $A_i - \{x\}$ are all distinct.

Construct a graph with nodes as the sets $A_i$ and edges between those sets, which differs by one element only.Edge labels are the separating elements. Now, to satisfy our requirement we must not have $n$ distinct labels. If the graph does not contain a cycle, then we are ok and statement holds. But if the graph contains a cycle then we have to manipulate the graph a bit.

Now if we somehow prove that in every cycle, each edge label occurs even number of times then we can do the manipulation as follows: keep one copy of each edge and delete other copies of that edge. In this way, we construct a new graph which can not have any cycle. So, we can have at max n - 1 distinct edge labels in this new graph and these are the original distinct labels in the original graph also.

But how to prove the assumed property of the cycle?

Thanks !

$\endgroup$
1
$\begingroup$

Let me write $A\triangle B$ for the symmetric difference $(A\setminus B)\cup(B\setminus A).$

Consider a graph $G$ which has $n$ nodes $A_1,A_2,\dots,A_n$ and at most $n$ edges chosen in the following way: For each $x\in[n],$ if there exist sets $A_i,A_j$ with $A_i\triangle A_j=\{x\},$ we choose one such pair of sets and draw the edge $e_x=A_iA_j.$

Note that, if there is a trail (no repeated edges) of length $k$ from $A_i$ to $A_j,$ then, since each $x\in[n]$ is added or subtracted at most once, we must have $|A_i\triangle A_j|=k.$ Therefore, the graph $G$ is acyclic. Therefore, it has at most $n-1$ edges. Therefore, there is at least one $x\in[n]$ such that $A_i\triangle A_j\ne\{x\}$ for all $i,j.$ Since the sets $A_1,A_2,\dots,A_n$ are distinct, it follows that the sets $A_1\setminus\{x\},A_2\setminus\{x\},\dots A_n\setminus\{x\}$ are also distinct.

$\endgroup$
  • $\begingroup$ Note that, if there is a trail (no repeated edges) of length $k$ from $A_i$ to $A_j$, then, since each $x \in [n]$ is added or subtracted at most once, we must have $|A_i\triangle A_j|=k.$. Therefore, the graph $G$ is acyclic. I did not get that ? Please explain a bit more. Thanks ! $\endgroup$ – Debashish Mar 24 '18 at 21:47
  • 1
    $\begingroup$ @Debashish Each time you traverse an edge, the set changes at one point. And the change is at a different point every time: that's because each $x\in[n]$ corresponds to just one edge of the graph, and the trail does not use any edge more than once. So the changes can't be canceled out, they just accumulate. $\endgroup$ – bof Mar 24 '18 at 22:13
  • 1
    $\begingroup$ @Debashish In other words, suppose each edge $e_x$ is labelled $x.$ Then, if there is a path $P$ from $A_i$ to $A_j,$ the symmetric difference $A_i\triangle A_j$ is just the set of labels occurring on the edges of $P.$ This is because each label is applied to at most one edge. $\endgroup$ – bof Mar 24 '18 at 22:24
  • 1
    $\begingroup$ @Debashish Suppose, e.g., that there is a cycle $A_1A_2A_3A_4A_5A_1.$ Then there is an element $x\in A_1\triangle A_2.$ Let's say that $x\in A_1$ but $x\notin A_2.$ Then $x\notin A_3$ because $A_2\triangle A_3=\{y\}$ for some $y\ne x.$ For the same reason, $x\notin A_4,$ and $x\notin A_5,$ and $x\notin A_1.$ But now we have arrived at a contradiction, $x\in A_1$ and $x\notin A_1.$ $\endgroup$ – bof Mar 24 '18 at 22:49
  • 1
    $\begingroup$ @Debashish In other words, if we follow a trail $v_0,v_1,v_2,\dots,$ then $$1=|v_0\triangle v_1|\lt|v_0\triangle v_2|\lt|v_0\triangle v_3|\lt|v_0\triangle v_4|\lt\cdots.$$ If we had $v_n=v_0$ (making a cycle), then we would have $|v_0\triangle v_0|=|v_0\triangle v_n|\gt0$ which is absurd. $\endgroup$ – bof Mar 24 '18 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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