Divergent permutations

NEW

Problem: Let $K$ be the simple complete graph on vertex set $\mathbb N$. An infinite permutation is a bijection $\pi:\mathbb N\to\mathbb N$. Two infinite permutations $\pi,\sigma$ are completely $K$-different if, for every position $n\in\mathbb N$, the pair $\{\pi(n),\sigma(n)\}$ is an edge of $K$. Since $K$ is simple complete, this is equivalent to

The question is to determine the largest possible cardinality of a family $\mathcal F\subseteq \operatorname{Sym}(\mathbb N)$ whose members are pairwise completely $K$-different.

Result: The largest cardinality is exactly $\aleph_0$.

Proof: First, any such family is at most countable. Fix one coordinate, say $n=1$. If $\pi,\sigma\in\mathcal F$ are distinct, then complete $K$-difference gives

Thus the map

is injective. Hence $|\mathcal F|\leq |\mathbb N|=\aleph_0$.

It remains to show that $\aleph_0$ is attained. Fachini and Körner already construct countably many pairwise completely $K$-different permutations: for each $i\in\mathbb N$, partition $\mathbb N$ into consecutive intervals of length $2^i$, and within each interval exchange the first and second halves. They prove that any two resulting permutations disagree in every coordinate. Therefore $|\mathcal F|\geq\aleph_0$.

Combining the upper and lower bounds,

Verification audit: The reconstruction uses the paper’s definition of “completely $G$-different” and the standard convention that the complete graph has edges exactly between distinct vertices. No additional assumptions are introduced. The upper bound applies to every family of pairwise completely $K$-different infinite permutations, and the cited construction supplies the matching lower bound.

Citation: E. Fachini and J. Körner, “Divergent permutations,” arXiv:1904.05113, Theorem 3.