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.

 

[blue_raver22]

I would approach this problem by first understanding the given conditions and what they imply. From the given information, we know that for each element $i$ in $N$, there exists a set $E_i$ of "enemies" of $i$, and the size of this set is denoted by $r_i$. We also know that the sum of all $r_i$ values is less than or equal to $n-1$. This means that the total number of enemies for all elements in $N$ is less than or equal to $n-1$.

Now, in order to prove that a permutation exists, we need to find a specific bijection in $S_n$ that satisfies the given conditions. To do this, we can use a constructive proof approach.

First, let's consider the special case where all $r_i$ values are equal to 0. In this case, there are no enemies for any element in $N$, and therefore, any bijection in $S_n$ would satisfy the condition that $\sigma(i) \notin E_i \, \, \forall i \in N$.

Now, let's consider the general case where at least one $r_i$ value is greater than 0. In this case, we can start by choosing a bijection $\sigma_0$ in $S_n$ such that $\sigma_0(i) \in E_i \, \, \forall i \in N$. This means that for each element $i$ in $N$, we have mapped it to one of its enemies.

However, since the total number of enemies is less than or equal to $n-1$, there must be at least one element $j \in N$ that is not mapped to any of its enemies. In other words, there exists at least one element $j$ such that $\sigma_0(j) \notin E_j$.

Now, we can construct a new bijection $\sigma_1$ by swapping the positions of $j$ and $\sigma_0(j)$ in $\sigma_0$. This means that $\sigma_1(j) = \sigma_0(\sigma_0(j))$, and $\sigma_1(\sigma_0(j)) = \sigma_0(j)$.

Since $\sigma_0(j) \notin E_j$, this also means that $\sigma_1(j) \notin E_j$