Divergent permutations

NEW

Problem: The open question is not a precise invariant question, since “sparse” is undefined. I formalize the natural structural version suggested by the preceding theorem:

Let $G=(\mathbb N,E)$ be a simple undirected graph. An infinite permutation is a bijection $\sigma:\mathbb N\to\mathbb N$. Two permutations $\sigma,\tau$ are completely $G$-different if

Characterize those graphs $G$ for which there are infinitely many pairwise completely $G$-different infinite permutations.

Result: The exact condition is:

Proof.

Necessity. Suppose $(\sigma_m)_{m\in\mathbb N}$ are pairwise completely $G$-different. Fix a vertex $v$. Since $\sigma_0$ is a permutation, $v=\sigma_0(i)$ for some $i$. Then

is an infinite clique: for $m\neq n$, complete $G$-difference gives

Also the entries are distinct, since $G$ is loopless. Thus $v\in C_i$, so every vertex lies in an infinite clique.

Sufficiency. Assume every vertex $v$ lies in an infinite clique $C_v$. Choose a sequence $(D_i)_{i\in\mathbb N}$ of infinite cliques such that every vertex belongs to infinitely many $D_i$; for example, repeat each $C_v$ infinitely often.

Form the bipartite graph $B$ with left side $P=\mathbb N$ of positions and right side $V=\mathbb N$, joining $i\in P$ to $v\in V$ iff $v\in D_i$. Every vertex of $B$ has infinite degree. Hence, by the infinite Hall marriage theorem, $B$ has a perfect matching. After removing finitely many perfect matchings, all degrees remain infinite, so the same argument recursively gives countably many edge-disjoint perfect matchings $M_0,M_1,\dots$.

Define $\sigma_m(i)=v$ iff $(i,v)\in M_m$. Each $M_m$ is perfect, so $\sigma_m$ is a permutation of $\mathbb N$. For $m\neq n$, the matchings are edge-disjoint, so $\sigma_m(i)\neq\sigma_n(i)$, and both vertices lie in the clique $D_i$. Therefore

for every $i$, so the permutations are pairwise completely $G$-different.

Thus the theorem holds exactly for graphs in which every vertex is contained in an infinite clique. In particular, no locally finite graph works, but graphs of zero asymptotic edge density can work, e.g. a countable disjoint union of countably infinite cliques under a sparse enumeration.

Citation: Problem from Fachini–Körner, “Divergent permutations,” arXiv:1904.05113, §3. The proof above uses the standard infinite Hall marriage theorem; no prior resolution of this exact question is cited in the source.