- Thread starter
- #1

- Mar 10, 2012

- 835

Let $N=\{ 1,2,\ldots ,n \}$.

As usual, take $S_n$ as the set of all bijections from $N$ to $N$.

Corresponding to each element $i$ in $N$ we have a set $E_i \subseteq N$ of "enemies" of $i$.

Denote $|E_i|=r_i$.

Its also given that:

1) $r_i \geq 0, \, \forall i \in N$

2) $r_1 + \ldots + r_n \leq n-1$

Show that there is $\sigma \in S_n$ such that $\sigma (i) \notin E_i \, \, \forall i \in N$.

I am pretty sure that such a sigma really exists.

I can solve it in a special case which I do in the next post. Please help.

EDIT: I hope that we find an algebraic proof of this.

As usual, take $S_n$ as the set of all bijections from $N$ to $N$.

Corresponding to each element $i$ in $N$ we have a set $E_i \subseteq N$ of "enemies" of $i$.

Denote $|E_i|=r_i$.

Its also given that:

1) $r_i \geq 0, \, \forall i \in N$

2) $r_1 + \ldots + r_n \leq n-1$

Show that there is $\sigma \in S_n$ such that $\sigma (i) \notin E_i \, \, \forall i \in N$.

I am pretty sure that such a sigma really exists.

I can solve it in a special case which I do in the next post. Please help.

EDIT: I hope that we find an algebraic proof of this.

Last edited: