MHB Prove that such a permutation exists.

[caffeinemachine]

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. (Nod)

 

[caffeinemachine]

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

Consider the special case where we have an additional constraint which reads:
$r_i \leq 1 \, \, \forall i \in N$

Let $k$ be the number of elements in $N$ which have exactly $1$ enemies. (In our present situation this is equal to the number of elements in $N$ having more than 0 enemies.) Thus $k \leq n-1$.

Assume on the contrary that no such $\sigma$ exists.

So each $\sigma \in S_n$ sends at least one entry in $N$ to its enemy.

Since there are $n!$ elements in $S_n$, By PHP, there is at least one element $i_0 \in N$ which is mapped to its enemy by at least $n!/k$ elements in $S_n$.

BUt its easy to see that there are at least $(n-1)(n-1)!$ elements in $S_n$ which don't send $i_0$ to its enemy.

So there are at most $n!-(n-1)(n-1)!=(n-1)!$ elements in $S_n$ which send $i_0$ to its enemy.

Since $(n-1)! < n!/k$ as $k \leq n-1$ we have a contradiction and the result in the first post holds for this case.

 

[Opalg]

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. (Nod)

I think you can do this by induction, though I struggled to get the details right. The inductive step goes like this. Suppose that the result has been proved for sets containing $n-1$ elements. Given $N$ as in the statement of the problem, the result is trivially true if $r_i=0$ for all $i$. So choose $p\in N$ such that $r_p>0$. Choose $q\in N$ such that $q\notin E_p,$ and choose $\tau \in S_n$ with $\tau(p)=q.$ Now define a new collection of "enemies" $F_i$ on the set $N\setminus\{p\}$ by $j\in F_i\;\Leftrightarrow\; \tau(j) \in E_i.$ Check that $\sum_{i\in N\setminus\{p\}}|F_i| \leqslant n-2$. By the inductive hypothesis there exists a permutation $\rho$ of $N\setminus\{p\}$ such that $\rho(i)\notin F(i)$ for each $i$.

Now define $\sigma:N\to N$ by $\sigma(p) = q$, $\sigma(i) = \tau\rho(i)\ (i\in N\setminus\{p\})$. Then $\sigma (i) \notin E_i \ \forall i \in N$, as required.

I have been a bit sloppy by assuming the inductive hypothesis for an arbitrary set of a given size, but only proving the result for the particular set $N$ consisting of the integers 1 to $n$. But that is just a question of giving names to the elements of the set, and does not affect the proof in any material way. I also neglected to prove the base case for the inductive proof (which is easy but critically important).

 

[caffeinemachine]

I think you can do this by induction, though I struggled to get the details right. The inductive step goes like this. Suppose that the result has been proved for sets containing $n-1$ elements. Given $N$ as in the statement of the problem, the result is trivially true if $r_i=0$ for all $i$. So choose $p\in N$ such that $r_p>0$. Choose $q\in N$ such that $q\notin E_p,$ and choose $\tau \in S_n$ with $\tau(p)=q.$ Now define a new collection of "enemies" $F_i$ on the set $N\setminus\{p\}$ by $j\in F_i\;\Leftrightarrow\; \tau(j) \in E_i.$ Check that $\sum_{i\in N\setminus\{p\}}|F_i| \leqslant n-2$. By the inductive hypothesis there exists a permutation $\rho$ of $N\setminus\{p\}$ such that $\rho(i)\notin F(i)$ for each $i$.

Now define $\sigma:N\to N$ by $\sigma(p) = q$, $\sigma(i) = \tau\rho(i)\ (i\in N\setminus\{p\})$. Then $\sigma (i) \notin E_i \ \forall i \in N$, as required.

I have been a bit sloppy by assuming the inductive hypothesis for an arbitrary set of a given size, but only proving the result for the particular set $N$ consisting of the integers 1 to $n$. But that is just a question of giving names to the elements of the set, and does not affect the proof in any material way. I also neglected to prove the base case for the inductive proof (which is easy but critically important).

That's exactly the kind of solution I was looking for. Thank you.
Here's another solution. One can form a bipartite graph $G$ whose partite sets are $X=N$ and $Y=N$. $x \in X$ and $y \in Y$ have an edge between them if $y \notin E_x$. Then $G$ has at least $n^2-n+1$ edges and has no isolated vertex. Its easy to show that, using Konig-Egervary theorem, that $G$ has a perfect matching. Now its easy to find the required permutation.