Bipartite Kneser graphs are Hamiltonian (Q5895045): Difference between revisions

The article under review considers the bipartite Kneser graph \(H(n,k)\) whose vertices are the \(k\) element and \(n-k\) element subsets of a ground set \([n]=\{1,2,\ldots n\}\) and an edge between any two vertices if and only if one of the corresponding sets is a subset of the other. In the paper, it is proved that \(H(n,k)\) is Hamiltonian. Further some new results are proved about long cycles in the Kneser graph \(K(2k+o(k),k)\) whose vertices are \(k\)-element subsets of \([n]\), two such being adjacent if and only if the corresponding sets are disjoint. These main results follow from a technical lemma about cycles and paths in the hypercube.