Mathematics – Combinatorics
Scientific paper
2010-11-10
Mathematics
Combinatorics
10 pages
Scientific paper
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}.
No associations
LandOfFree
Automorphisms of infinite Johnson graph does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Automorphisms of infinite Johnson graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automorphisms of infinite Johnson graph will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-614077