About an intersection of permutations Two permutations $\phi_1$ and $\phi_2$ of a finite set $X$ are said to intersect if there exists $x \in X $ such that $\phi_1(x) = \phi_2(x)$ . Let $n$ be a positive integer and given $n$ permutations of the set $X=\{1,2,...,2n\}$. Prove that there exists a permutation of $X$ such that it does not intersect the given $n$ permutations.
My idea is to bring it back to graph theory, so I would treat each permutation as a vertex of the graph, $2$ adjacent vertices if the $2$ permutations intersect. But I still can't handle it, I hope to get help from everyone. Thanks very much!
 A: So, if we are talking about the following problem.

If $\sigma_1,\ldots,\sigma_n\in S_{2n}$,  then there exists a
permutation $\sigma\in S_{2n}$ that does not intersect every
permutation $\sigma_i$.

We will use Hall's theorem in the following formulation
(see e.g. Bondy and Murty, Graph theory with applications, page 75, Exercise 5.2.4; or M. Hall, Combinatorial Theory, page 49, Theorem 5.1.1):

Let $A_1,A_2,\ldots,A_m$ be subset of a set $S$.  If
$$ 
|\cup_{i\in J}A_i|\geq|J| \tag1 
$$
for all subsets $J$ of $\{1,2,\ldots,m\}$, then
there exist pairwise distinct elements $a_1,a_2,\ldots,a_m\in S$
that $a_i\in A_i$ for all $i=1,2,\ldots,m$.

In our case $S=\{1,2,\ldots,2n\}$, $m=2n$.
Let us construct the sets $A_i$
Let $M_i=\{\sigma_1(i),\ldots,\sigma_n(i)\}$ and $A_i=\overline{M_i}=S\setminus M_i$ for all $i=1,2,\ldots,2n$.
It is clear that $|M_i|\leq n$ and $|A_i|\geq n$.
Now let us check the Hall condition $(1)$.
Let $J\subset\{1,2,\ldots,2n\}$. If $|J|\leq n$, then inequality $(1)$ is obviously true ($|A_i|\geq n$).
If $|J|>n$, then
$$
\cup_{i\in J}A_i=\cup_{i\in J}\overline{M_i}=\overline{\cap_{i\in J}M_i}.
$$
Note that in this case $\cap_{i\in J}M_i=\varnothing$.
Indeed, if $j\in\cap_{i\in J}M_i$, then $j\in M_i$ and there exists $t_i\in\{1,2,\ldots,n\}$ that $j=\sigma_{t_i}(i)$ for all $i\in J$.
Since $|\{t_i\mid i\in J\}|=|J|>n$ and $1\leq t_i\leq n$, it follows that $t_\alpha=t_\beta=p$
for some $\alpha\neq\beta$ of $J$.
We get $\sigma_p(\alpha)=\sigma_p(\beta)=j$. Contradiction.
So $|\cap_{i\in J}M_i|=0$ and $|\overline{\cap_{i\in J}M_i}|=2n\geq|J|$.
We have checked the Hall condition $(1)$.
Let  $a_1,a_2,\ldots,a_{2n}$ be pairwise different elements of $S$ that $a_i\in\overline{M_i}$ or $a_i\notin M_i$.
Let us take the permutation $\sigma$ defined by the rule $\sigma(i)=a_i$.
The permutation $\sigma$ does not intersect every permutation $\sigma_i$.
