On the Cayleyness of bipartite Kneser graphs

Abstract. For any given n, k ∈N with 2k n, the bipartite Kneser graph H(n, k) is defined as the graph whose vertex set is the family of k-subsets and (n − k)-subsets of [n] = {1, 2, . . . ,n} in which any two vertices are adjacent if and only if one of them is a subset of the other. In this paper, we study some algebraic properties of the bipartite Kneser graph H(n, k). In particular, we determine the values of n, k for which the bipartite Kneser graph H(n, k) is a Cayley graph.