We consider the { \it infinite Johnson graph} $J_{ \infty}$ whose vertex set consists of all subsets $X\subset { \mathbb N}$ satisfying $|X|=|{ \mathbb N}\setminus X|=\infty$ and whose edges are pairs of such subsets $X,Y$ satisfying $|X\setminus Y|=|Y\setminus X|=1$. An automorphism of $J_{ \infty}$ is said to be { \it regular} if it is induced by a permutation on $\mathbb{ N}$ or it is the composition of the automorphism induced by a permutation on $\mathbb{ N}$ and the automorphism $X\to { \mathbb N}\setminus X$. The graph $J_{ \infty}$ admits non-regular automorphisms. Our first result states that the restriction of every automorphism of $J_{ \infty}$ to any connected component ($J_{ \infty}$ is not connected) coincides with the restriction of a regular automorphism. The second result is a characterization of regular automorphisms of $J_{ \infty}$ as order preserving and order reversing bijective transformations of the vertex set of $J_{ \infty}$ (the vertex set is partially ordered by the inclusion relation). As an application, we describe automorphisms of the associated { \it infinite Kneser graph}.
Categories: math.CO