The automorphism group of the bipartite Kneser graph

Abstract

Let n and k be integers with $n>2k$, $k\ge 1$. We denote by H(n, k) the bipartite Kneser graph, that is, a graph with the family of k-subsets and ($n-k$)-subsets of $[n] = \{1, 2,\ldots , n\}$ as vertices, in which any two vertices are adjacent if and only if one of them is a subset of the other. In this paper, we determine the automorphism group of H(n, k). We show that $\mathrm{Aut}(H(n, k))\cong \mathrm{Sym}([n]) \times {\mathbb {Z}}_2$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2. Then, as an application of the obtained result, we give a new proof for determining the automorphism group of the Kneser graph K(n, k). In fact, we show how to determine the automorphism group of the Kneser graph K(n, k) given the automorphism group of the Johnson graph J(n, k). Note that the known proofs for determining the automorphism groups of Johnson graph J(n, k) and Kneser graph K(n, k) are independent of each other.

1 Introduction

For a positive integer $n > 1$, let $[n] = \{1, 2, \ldots , n\}$ and V be the set of all k-subsets and $(n-k)$-subsets of [n]. The bipartite Kneser graph H(n, k) has V as its vertex set, and two vertices A, B are adjacent if and only if $A \subset B$ or $B\subset A$. If $n = 2k$, it is obvious that we do not have any edges, and in such a case, H(n, k) is a null graph, and hence we assume that $n \ge 2k + 1$. It follows from the definition of the graph H(n, k) that it has 2${n}\atopwithdelims (){k}$ vertices and the degree of each of its vertices is ${n-k}\atopwithdelims (){k}$= ${n-k}\atopwithdelims (){n-2k}$, hence it is a regular graph. It is clear that H(n, k) is a bipartite graph. In fact, if $V_1=\{ v\in V(H(n ,k)) | \ |v| =k \}$ and $V_2=\{ v\in V(H(n ,k)) | \ |v| =n-k \}$, then $\{ V_1, V_2\}$ is a partition of V(H(n, k)) and every edge of H(n, k) has a vertex in $V_1$ and a vertex in $V_2$ and $| V_1 |=| V_2 |$. It is an easy task to show that the graph H(n, k) is a connected graph. The bipartite Kneser graph $H(2n+1, n)$ is known as the middle cube $MQ_{2n+1} = {Q_{2n+1}}(n,n+1)$ [3] or regular hyperstar graph $HS(2(n+1),n+1)$ [11, 13].

The regular hyperstar graph ${Q_{2n+1}}(n,n+1)$ has been investigated from various aspects, by various authors and some of the recent works about this class of graphs are [3, 6, 11, 13, 16, 17]. Figure 1 shows the graph H(5, 2) ($Q_{5}(2,3)$) in a plane. Note that in this figure the set $\{i,j,k\}$ ($\{ i,j \}$) is denoted by ijk (ij).

Fig. 1

The bipartite graph H(5, 2).

It was conjectured by Dejter et al. [6] among others, that the middle cube ${Q_{2n+1}}(n,n+1)$ is Hamiltonian. Recently, Mütze and Su [17] showed that the bipartite Kneser graph H(n, k) has a Hamilton cycle for all values of k. Among various interesting properties of the bipartite Kneser graph H(n, k), we are interested in its automorphism group and we want to know how this group acts on the vertex set of H(n, k). Mirafzal [13] determined the automorphism group of $HS(2n,n)= H(2n-1, n-1)$ and showed that HS(2n, n) is a vertex-transitive non-Cayley graph. Also, he showed that HS(2n, n) is arc-transitive. Some of the symmetry properties of the bipartite Kneser graph H(n, k) are as follows.

PROPOSITION 1.1

 [16, Lemma 3.1]

The graph H(n, k) is a vertex-transitive graph.

PROPOSITION 1.2

 [16, Theorem 3.2]

The graph H(n, k) is a symmetric (or arc-transitive) graph.

COROLLARY 1.3

 [16, Corollary 3.3]

The connectivity of the bipartite Kneser graph H(n, k) is maximum, namely, ${n-k}\atopwithdelims (){k}$.

PROPOSITION 1.4

 [16, Proposition 3.5]

The bipartite Kneser graph H(n, 1) is a Cayley graph.

Theorem 1.5

 [16, Theorem 3.6]. Let H(n, 1) be a bipartite Kneser graph. Then, $\mathrm{Aut}(H(n,1)) \cong \mathrm{Sym}([n] ) \times {\mathbb {Z}}_2$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2.

In [16] the authors proved the following theorem.

Theorem 1.6

  [16, Theorem 3.8]. Let $n=2k-1$. Then, for the bipartite Kneser graph $H(n,k-1)$, we have $\mathrm{Aut}(H(n,k)) \cong \mathrm{Sym}([n]) \times {\mathbb {Z}}_2$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2.

In [16], the authors asked the following question.

Question. Is the above theorem true for all possible values of n, k ($2k < n$)?

In the sequel, we want to answer the above question. We show that the above theorem is true for all possible values of n, k ( $2k < n$).

In fact, to the best of our knowledge, the present work is the first answer to this problem. We determine the automorphism group of the graph H(n, k) and show that $\mathrm{Aut}(H(n, k)) \cong \mathrm{Sym}([n] ) \times {\mathbb {Z}}_2$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2. In the final step of our work, we offer a new proof for determining the automorphism group of the Kneser graph K(n, k) which we believe that this proof is more elementary than other known proofs of this result. Note that the known proofs for determining the automorphism groups of the Johnson graph J(n, k) and the Kneser graph K(n, k) are independent of each other. We show how we can have the automorphism group of the Kneser graph K(n, k) on the one hand, if we have the automorphism group of the Johnson graph J(n, k) on the other hand.

There are various important families of graphs $\Gamma$, in which we know that for a particular group G, we have $G \le \mathrm{Aut}(\Gamma )$, but to show that we have $G = \mathrm{Aut}(\Gamma )$, is a difficult task. For example, note the following cases:

(1) The Boolean lattice $BL_n$, $n \ge 1$, is the graph whose vertex set is the set of all subsets of $[n]= \{ 1,2,\ldots , n \}$, where two subsets x and y are adjacent if their symmetric difference has precisely one element. The hypercube $Q_n$ is the graph whose vertex set is $\{0,1 \}^n$, where two n-tuples are adjacent if they differ in precisely one coordinate. It is an easy task to show that $Q_n \cong BL_n$ and $Q_n \cong \mathrm{Cay}({\mathbb {Z}}_{2}^n, S )$, where ${\mathbb {Z}}_{2}$ is the cyclic group of order 2, and $S=\{ e_i \ | \ 1\le i \le n \},$ where $e_i = (0, \ldots , 0, 1, 0, \ldots , 0)$, with 1 at the i-th position. It is an easy task to show that the set $H= \{ f_\theta |\ \theta \in \mathrm{Sym}([n]) \}$, $f_\theta (\{x_1, \ldots , x_n \}) = \{ \theta (x_1), \ldots , \theta (x_n) \}$ is a subgroup of $\mathrm{Aut}(BL_n)$, and hence H is a subgroup of the group $\mathrm{Aut}(Q_n)$. We know that in every Cayley graph $\Gamma = \mathrm{Cay}(G,S)$, the group $\mathrm{Aut}(\Gamma )$ contains a subgroup isomorphic with the group G. Therefore, ${\mathbb {Z}}_{2}^n$ is a subgroup of $\mathrm{Aut}(Q_n)$. Now, to show that $\mathrm{Aut}(Q_n) = \langle {\mathbb {Z}}_{2}^n, \mathrm{Sym}([n])\rangle ( \cong {\mathbb {Z}}_{2}^n \rtimes \mathrm{Sym}([n]))$ is not an easy task [14].

(2) Let $n,k \in {\mathbb {N}}$ with $k < \frac{n}{2}$ and let $[n]=\{1,\ldots ,n\}$. The Kneser graph K(n, k) is defined as the graph whose vertex set is $V=\{v\mid v\subseteq [n], |v|=k\}$ and two vertices v, w are adjacent if and only if $|v\cap w|$=0. The Kneser graph K(n, k) is a vertex-transitive graph [5]. It is an easy task to show that the set $H= \{ f_\theta \ |\ \theta \in \mathrm{Sym}([n]) \}$, $f_\theta (\{x_1, \ldots , x_k \}) = \{ \theta (x_1), \ldots , \theta (x_k) \}$ is a subgroup of $\mathrm{Aut} ( K(n,k) )$ [5]. But, showing that

$$\begin{aligned} H= \big \{ f_\theta \ |\ \theta \in \mathrm{Sym}([n])\big \}= \mathrm{Aut} ( K(n,k) ) \end{aligned}$$

is a rather difficult work [5, Chapter 7].

(3) Let n and k be integers with $n> k\ge 1$ and let $[n] = \{1, 2, \ldots , n\}$. We now consider the bipartite Kneser graph $\Gamma = H(n,k)$. Let A, B be m-subsets of [n] and let $| A \cap B |=t$. Let $\theta$ be a permutation in $\mathrm{Sym}([n])$. It is an easy task to show that $| f_\theta (A) \cap f_\theta (B) |=t$, where $f_\theta (\{x_1, \ldots , x_m \}) = \{ \theta (x_1), \ldots , \theta (x_m) \}$. Moreover, if $A\subset B$, then $f_\theta (A) \subset f_\theta (B)$. Therefore, if $\theta \in \mathrm{Sym}([n])$, then

$$\begin{aligned} f_\theta : V(H(n,k) )\longrightarrow V(H(n,k)), f_\theta (\{x_1, \ldots , x_k \}) = \{ \theta (x_1), \ldots , \theta (x_k) \} \end{aligned}$$

is an automorphism of H(n, k) and the mapping, $\psi : \mathrm{Sym} ([n]) \rightarrow \mathrm{Aut} (H(n,k) )$, defined by the rule $\psi ( \theta ) = f_\theta$ is an injection. Therefore, the set $H= \{ f_\theta \ |\ \theta \in \mathrm{Sym}([n]) \}$ is a subgroup of $\mathrm{Aut} ( H(n,k) )$ which is isomorphic with $\mathrm{Sym}([n])$. Also, the mapping $\alpha : V(\Gamma )\rightarrow V(\Gamma )$, defined by the rule, $\alpha (v) = v^c$, where $v^c$ is the complement of the subset v in [n], is an automorphism of the graph H(n, k). In fact, if $A\subset B$, then $B^c\subset A^c$, and hence if $\{A,B\}$ is an edge of the graph H(n, k) , then $\{\alpha (A), \alpha (B)\}$ is an edge of the graph H(n, k) . Therefore, we have $\langle H, \alpha \rangle \le \mathrm{Aut}(H(n,k))$.

In this paper, we show that for the bipartite Kneser graph H(n, k), we have, in fact, $\mathrm{Aut}(H(n,k))=\langle H, \alpha \rangle (\cong \mathrm{Sym}([n])\times {\mathbb {Z}}_2)$.

2 Preliminaries

In this paper, a graph $\Gamma =(V,E)$ is considered as a finite undirected simple graph, where $V=V(\Gamma )$ is the vertex-set and $E=E(\Gamma )$ is the edge-set. For all the terminologies and notations not defined here, we follow [1, 4, 5].

The graphs $\Gamma _1 = (V_1,E_1)$ and $\Gamma _2 = (V_2,E_2)$ are called isomorphic, if there is a bijection $\alpha : V_1 \longrightarrow V_2$ such that $\{a,b\} \in E_1$ if and only if $\{\alpha (a),\alpha (b)\} \in E_2$ for all $a,b \in V_1$. In such a case, the bijection $\alpha$ is called an isomorphism. An automorphism of a graph $\Gamma$ is an isomorphism of $\Gamma$ with itself. The set of automorphisms of $\Gamma$ with the operation of composition of functions is a group, called the automorphism group of $\Gamma$ and is denoted by $\mathrm{Aut}(\Gamma )$.

The group of all permutations of a set V is denoted by $\mathrm{Sym}(V)$ or just $\mathrm{Sym}(n)$ when $|V| =n$. A permutation group G on V is a subgroup of $\mathrm{Sym}(V)$. In this case, we say that G acts on V. If X is a graph with vertex-set V, then we can view each automorphism as a permutation of V, and so $\mathrm{Aut}(X)$ is a permutation group. If G acts on V, we say that G is transitive (or G acts transitively on V), when there is just one orbit. This means that given any two elements u and v of V, there is an element $\beta$ of G such that $\beta (u)= v$.

The graph $\Gamma$ is called vertex-transitive, if $\mathrm{Aut}(\Gamma )$ acts transitively on $V(\Gamma )$. For $v\in V(\Gamma )$ and $G=\mathrm{Aut}(\Gamma )$, the stabilizer subgroup $G_v$ is the subgroup of G consisting of all automorphisms that fix v. We say that $\Gamma$ is symmetric (or arc-transitive) if, for all vertices u, v, x, y of $\Gamma$ such that u and v are adjacent, x and y are also adjacent, and there is an automorphism $\pi$ in $\mathrm{Aut}(\Gamma )$ such that $\pi (u)=x$ and $\pi (v)=y$.

Let $n,k \in {\mathbb {N}}$ with $k \le \frac{n}{2}$, and let $[n]=\{1,\ldots ,n\}$. The Johnson graph J(n, k) is defined as the graph whose vertex set is $V=\{v\mid v\subseteq [n], |v|=k\}$ and two vertices v, w are adjacent if and only if $|v\cap w|=k-1$. The Johnson graph J(n, k) is a vertex-transitive graph [5]. It is an easy task to show that the set $H= \{ f_\theta |\ \theta \in \mathrm{Sym}([n]) \}$, $f_\theta (\{x_1, \ldots , x_k \}) = \{ \theta (x_1), \ldots , \theta (x_k) \}$ is a subgroup of $\mathrm{Aut}( J(n,k) )$ [5]. It has been shown that $\mathrm{Aut}(J(n,k)) \cong \mathrm{Sym}([n])$, if $n\ne 2k,$ and $\mathrm{Aut}(J(n,k)) \cong \mathrm{Sym}([n]) \times {\mathbb {Z}}_2$, if $n=2k$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2 [2, 9, 15].

Although, in most situations it is difficult to determine the automorphism group of a graph $\Gamma$ and how it acts on the vertex set of $\Gamma$, there are some recent works in the literature [7,8,9,10, 12,13,14,15,16, 18, 19].

3 Main results

Lemma 3.1

Let n and k be integers with $\frac{n}{2}> k\ge 1$, and let $\Gamma = (V,E)= H(n,k)$ be a bipartite Kneser graph with partition $V=V_1 \cup V_2$, $V_1 \cap V_2 =\varnothing$, where $V_1= \{ v \ | \ v\subset [n], |v|=k \}$ and $V_2= \{ w \ |\ w \subset [n], |w|=n-k \}$. If f is an automorphism of $\Gamma$ such that $f(v)=v$ for every $v\in V_1$, then f is the identity automorphism of $\Gamma$.

Proof

First, note that since f is a permutation of the vertex set V and $f(V_1)=V_1$, then $f(V_2)= V_2$. Let $w\in V_2$ be an arbitrary vertex in $V_2$. Since f is an automorphism of the graph $\Gamma$, then for the set $N(w)= \{ v | v\in V_1, v\leftrightarrow w \}$, we have $f(N(w))= \{ f(v) | v\in V_1, v\leftrightarrow w \}=N(f(w))$. On the other hand, since for every $v\in V_1$, $f(v)=v$, then $f(N(w))=N(w)$, and therefore $N(f(w))=N(w)$. In other words, w and f(w) are $(n-k)$-subsets of [n] such that their family of k-subsets are the same. Now, it is an easy task to show that $f(w)=w$. Therefore, for every vertex x in $\Gamma$, we have $f(x)=x$ and thus f is the identity automorphism of $\Gamma$. $\square$

Remark 3.2

If, in the assumptions of the above lemma, we replace with $f(v)=v$ for every $v\in V_2$, then we can show, by a similar discussion, that f is the identity automorphism of $\Gamma$.

Lemma 3.3

Let $\Gamma =(V, E)$ be a connected bipartite graph with partition $V=V_1 \cup V_2$, $V_1 \cap V_2 = \varnothing$. Let f be an automorphism of $\Gamma$ such that for a fixed vertex $v \in V_1$, we have $f(v) \in V_1$. Then, $f(V_1) = V_1$ and $f(V_2) =V_2$. Or, for a fixed vertex $v \in V_1$, we have $f(v) \in V_2$. Then, $f(V_1) = V_2$ and $f(V_2) =V_1$.

Proof

In the first step, we show that if $w \in V_1$, then $f(w) \in V_1$. We know that if $w\in V_1$, then $d_\Gamma (v, w) = d(v, w)$, the distance between v and w in the graph $\Gamma$, is an even integer. Assume $d(v, w) =2l$, $0\le 2l \le D$, where D is the diameter of $\Gamma$. We prove by induction on l, that $f(w) \in V_1$. If $l=0$, then $d(v, w) =0$, thus $v=w$, and hence $f(w)=f(v) \in V_1$. Suppose that if $w_1 \in V_1$ and $d(v, w_1)= 2(k-1)$, then $f(w_1) \in V_1$. Assume $w \in V_1$ and $d(v, w)=2k$. Then, there is a vertex $u \in \Gamma$ such that $d(v, u)=2k-2=2(k-1)$ and $d(u, w)=2$. We know (by the induction assumption) that $f(u) \in V_1$ and since $d(f(u),f(w))=2$, therefore $f(w) \in V_1$. Now, it follows that $f(V_1)=V_1$ and consequently $f(V_2)=V_2$. $\square$

COROLLARY 3.4

Let $\Gamma =H(n,k) = (V,E)$ be a bipartite Kneser graph with partition $V=V_1 \cup V_2$, $V_1 \cap V_2 = \varnothing$. If f is an automorphism of the graph $\Gamma$, then $f(V_1)=V_1$ and $f(V_2) =V_2$, or $f(V_1) = V_2$ and $f(V_2) = V_1$.

In the sequel, we need the following result for proving our main theorem.

Lemma 3.5

Let l, m and u be positive integers with $l > u$ and $m> u$. If $l>m$, then ${l} \atopwithdelims (){u}$ > ${m} \atopwithdelims (){u}$.

Proof

The proof is straightforward. $\square$

Theorem 3.6

Let n and k be integers with $\frac{n}{2}> k\ge 1$, and let $\Gamma = (V,E)= H(n,k)$ be a bipartite Kneser graph with partition $V=V_1 \cup V_2$, $V_1 \cap V_2 = \varnothing$, where $V_1= \{ v \ | \ v\subset [n], |v|=k \}$ and $V_2= \{ w \ | \ w \subset [n], |w|=n-k \}$. Then, $\mathrm{Aut}(\Gamma ) \cong \mathrm{Sym}([n]) \times {\mathbb {Z}}_2$, where ${\mathbb {Z}}_2$ is the cyclic group of order 2.

Proof

Let $\alpha : V(\Gamma )\rightarrow V(\Gamma )$, defined by the rule $\alpha (v) = v^c$, where $v^c$ is the complement of the subset v in [n]. Also, let $H =\{ f_\theta |\ \theta \in \mathrm{Sym} ([n]) \}$, $f_\theta (\{x_1, \ldots , x_k \}) = \{ \theta (x_1), \ldots , \theta (x_k)$. We have seen already that $H( \cong \mathrm{Sym}([n]))$ and $\langle \alpha \rangle ( \cong {\mathbb {Z}}_2)$ are subgroups of the group $G= \mathrm{Aut}(\Gamma )$. We can see that $\alpha \not \in H$, and for every $\theta \in \mathrm{Sym}([n])$, we have $f_{\theta }\alpha = \alpha f_{\theta }$ [15]. Therefore, $\mathrm{Sym}([n]) \times {\mathbb {Z}}_2 \cong H \times \langle \alpha \rangle \cong \langle H, \alpha \rangle =\{ f_{\gamma } \alpha ^i\ | \ \gamma \in \mathrm{Sym}([n]), 0\le i \le 1 \}=S$ is a subgroup of G. We now want to show that $G=S$. Let $f \in \mathrm{Aut}(\Gamma )=G$. We show that $f \in S$. There are two cases:

• (i) There is a vertex $v \in V_1$ such that $f(v) \in V_1$, and hence by Lemma 3.3, we have $f(V_1)=V_1$.

• (ii) There is a vertex $v \in V_1$ such that $f(v) \in V_2$, and hence by Lemma 3.3, we have $f(V_1)=V_2$.

Now let us consider the first case.

Case (i). Let $f(V_1)=V_1$. Then, for every vertex $v \in V_1$, we have $f(v) \in V_1$, and therefore the mapping $g=f_{|V_1}: V_1 \rightarrow V_1$ is a permutation of $V_1$, where $f_{|V_1}$ is the restriction of f to $V_1$. Let $\Gamma _2= J(n,k)$ be the Johnson graph with the vertex set $V_1$. Then, the vertices $v,w \in V_1$ are adjacent in $\Gamma _2$ if and only if $| v \cap w| =k-1$.

We assert that the permutation $g= f_{|V_1}$ is an automorphism of the graph $\Gamma _2$.

For proving our assertion, it is sufficient to show that if $v,w \in V_1$ are such that $| v \cap w| =k-1$, then we have $|g(v) \cap g(w) |= k-1$. Note that since v, w are k-subsets of [n], then if u is a common neighbour of v, w in the bipartite Kneser graph $\Gamma =H(n,k)$, then the set u contains the sets v and w. In particular, u contains the $(k+1)$-subset $v\cup w$. We now see that the number of vertices u, such that u is adjacent in $\Gamma$ to both the vertices v and w is ${n-k-1}\atopwithdelims (){n-2k-1}$. Note that if t is a positive integer such that $k+1+t=n-k$, then $t= n-2k-1$. Now, if we adjoin to the $(k+1)$-subset $v \cup w$ of [n], $n-2k-1$ elements of the complement of $v \cup w$ in [n], then we obtain a subset u of [n] such that $v \cup w \subseteq u$ and u is a $(n-k)$-subset of [n]. Now, since v and w have ${n-k-1} \atopwithdelims (){n-2k-1}$ common neighbours in the graph $\Gamma$, the vertices g(v) and g(w) must have ${n-k-1} \atopwithdelims (){n-2k-1}$=${n-k-1} \atopwithdelims (){k}$ neighbours in $\Gamma$, and therefore $| g(v) \cap g(w) |$= $k-1$. In fact, if $|g(v) \cap g(w)|= k-h < k-1$, then $h>1$ and hence $|g(v) \cup g(w)| = k+h$. Thus, if t is a positive integer such that $k+h+t=n-k$, then $t= n-2k-h$. Hence, for constructing a $(n-k)$-subset $u \supseteq g(v) \cup g(w)$, we must adjoin $t=n-2k-h$ elements of the complement of $g(v) \cup g(w)$ in [n], to the set $g(v) \cup g(w)$. Therefore the number of common neighbours of vertices g(v) and g(w) in the graph $\Gamma$ is ${n-k-h} \atopwithdelims (){n-2k-h}$=${n-k-h} \atopwithdelims (){k}$. Note that by Lemma 3.5. it follows that ${n-k-h} \atopwithdelims (){k}$ $\ne$ ${n-k-1} \atopwithdelims (){k}$.

Our argument shows that the permutation $g=f_{|V_1}$ is an automorphism of the Johnson graph $\Gamma _2=J(n,k)$, and therefore by [2, chapter 9, 15], there is a permutation $\theta \in \mathrm{Sym}([n])$ such that $g= f_{\theta }$.

On the other hand, we know that $f_{\theta }$ by its natural action on the vertex set of the bipartite Kneser graph $\Gamma = H(n,k)$ is an automorphism of $\Gamma$. Therefore, $l=f_{\theta }^{-1}f$ is an automorphism of the bipartite Kneser graph $\Gamma$ such that l is the identity automorphism on the subset $V_1$. We can now conclude, by Lemma 3.1 that $l= f_{\theta }^{-1}f$ is the identity automorphism of $\Gamma$, and therefore $f=f_{\theta }$.

In other words, we have proved that if f is an automorphism of $\Gamma = H(n,k)$ such that $f(V_1)=V_1$, then $f=f_{\theta }$, for some $\theta \in \mathrm{Sym}([n] )$, and hence $f \in S$.

Case (${ ii}$). We now assume that $f(V_1) \ne V_1$. Then, $f(V_1) = V_2$. Since the mapping $\alpha$ is an automorphism of the graph $\Gamma$, then $f \alpha$ is an automorphism of $\Gamma$ such that $f \alpha (V_1) = f(\alpha (V_1))= f(V_2)=V_1$. Therefore, by what is proved in (i), we have $f \alpha =f_{\theta }$, for some $\theta \in \mathrm{Sym}([n])$. Now since $\alpha$ is of order 2, then $f= f_{\theta } \alpha \in S=\{ f_{\gamma } \alpha ^i \ | \ \gamma \in \mathrm{Sym}([n]), 0\le i \le 1 \}$. $\square$

Let n, k be integers and $n >4, \ k< \frac{n}{2}, \ [n]=\{1,2,\ldots ,n \}$. Let $K(n,k)= \Gamma$ be a Kneser graph. It is a well known fact that $\mathrm{Aut} (\Gamma )\cong \mathrm{Sym}([n])$ [5, Chap. 7]. In fact, the proof in [5, Chap. 7] shows that the automorphism group of the Kneser graph K(n, k) is the group $H =\{ f_\theta \ |\ \theta \in \mathrm{Sym} ([n]) \}(\cong \mathrm{Sym}([n]))$. The proof of this result that appears in [5, Chap. 7] uses the following fact which is one of the fundamental results in extremal set theory.

Fact (Erdős-Ko-Rado). If $n> 2k$, then $\alpha (K(n,k))$ = ${n-1} \atopwithdelims (){k-1}$, where $\alpha (K(n,k))$ is the independence number of the Kneser graph K(n, k).

In the sequel, we provide a new proof for determining the automorphism groups of Kneser graphs. The main tool which we use in our method is Theorem 3.6. Note that the main tool which we use for proving Theorem 3.6 is the automorphism group of the Johnson graph J(n, k), which have been already obtained in [2, Chapter 9] and [15] by using elementary and relevant facts of graph theory and group theory.

Theorem 3.7

Assume that n, k are integers and $n >4, \ k< \frac{n}{2}, \ [n]=\{1,2,\ldots ,n \}$. If $K(n,k)= \Gamma$ is a Kneser graph, then we have $\mathrm{Aut} (\Gamma )\cong \mathrm{Sym}([n])$.

Proof

Let g be an automorphism of the graph $\Gamma$. We now consider the bipartite Kneser graph $\Gamma _1=H(n,k)=( V,E)$ with partition $V=V_1 \cup V_2$, $V_1 \cap V_2 =\varnothing$, where $V_1= \{ v \ | \ v\subset [n], |v|=k \}$ and $V_2= \{ w \ | \ w \subset [n], |w|=n-k \}$. We define the mapping $f: V \rightarrow V$ by the following rule:

$$\begin{aligned} f(v) = {\left\{ \begin{array}{ll} g(v) &{}\quad v \in V_1, \\ (\alpha g \alpha ) (v) &{} \quad v \in V_2.\\ \end{array}\right. } \end{aligned}$$

It is an easy task to show that f is a permutation of the vertex set V such that $f(V_1) = V_1 = g(V_1)$. We show that f is an automorphism of the bipartite Kneser graph $\Gamma _1$. Let $\{v,w\}$ be an edge of the graph $\Gamma _1$ with $v \in V_1$. Then $v \subset w$, and hence $v \cap w^c=v \cap \alpha (w) = \varnothing$. In other words, $\{v , \alpha (w) \}$ is an edge of the Kneser graph $\Gamma$. Now, since the mapping g is an automorphism of the Kneser graph $\Gamma$, then $\{g(v), \ g(\alpha (w)) \}$ is an edge of the Kneser graph $\Gamma$, and therefore we have $g(v)\cap g(\alpha (w)) = \varnothing$. This implies that $g(v) \subset {(g(\alpha (w))) }^c=\alpha ( g(\alpha (w)) )$. In other words, $\{g(v), \alpha (g(\alpha (w)) ) \} = \{f(v), f(w)\}$ is an edge of the bipartite Kneser graph $\Gamma _1$. Therefore f is an automorphism of the bipartite Kneser graph H(n, k). Now, since $f({V_1}) =V_1$, then by Theorem 3.6, there is a permutation $\theta$ in $\mathrm{Sym}([n])$ such that $f= f_{ \theta }$. Then, for every $v\in V_1$, we have $g(v)= f(v)=f_{\theta }(v)$, and therefore $g=f_{\theta }$. We now can conclude that $\mathrm{Aut}( K(n,k))$ is a subgroup of the group $H =\{ f_\gamma \ |\ \gamma \in \mathrm{Sym} ([n]) \}$. On the other hand, we can see that H is a subgroup of $\mathrm{Aut}(K(n,k))$, and therefore we have $\mathrm{Aut}(K(n,k))=H =\{ f_\gamma \ | \ \gamma \in \mathrm{Sym} ([n]) \} \cong \mathrm{Sym} ([n])$. $\square$

4 Conclusion

In this paper, we studied one of the algebraic properties of the bipartite Kneser graph H(n, k). We determined the automorphism group of this graph for all n, k, where $2k < n$ (Theorem 3.6). Then, by Theorem 3.6 we offered a new proof for determining the automorphism group of the Kneser graph K(n, k) (Theorem 3.7).