Kneser graphs are Hamiltonian for \(n\geq 3k\) (Q1850485): Difference between revisions

The Kneser graph \(K(n, k)\) has as vertices the \(k\)-subsets of \([n]= \{1,2,\dots, n\}\). Two vertices are adjacent if the \(k\)-subsets are disjoint. The Kneser graph \(K(2k- 1, k-1)\) is also called the odd graph \(O_k\) for \(k\geq 2\). Meredith and Lloyd showed that \(O_k\) is Hamiltonian for \(4\leq k\leq 7\). They conjectured that \(O_k\) for \(k\neq 3\) is an edge-disjoint union of Hamiltonian cycles plus, perhaps, a 1-factor. We prove that the Kneser graph \(K(n, k)\) is Hamiltonian for \(n\geq 3k\). The bipartite Kneser graph \(H(n, k)\) has as its partite sets the \(k\)- and \((n-k)\)-subsets of \([n]\), respectively. Two vertices from different partite sets are adjacent if the \(k\)-subset is contained in the \((n- k)\)-subset. Consider a hotel with \(k\) customers in the lobby and \((k+1)\) customers outside, separated by a revolving door. One customer can pass through the door at a time. P. Erdős (also Hável, Kelly) conjectured that by adding or removing one customer at a time, it is possible to cycle through the subsets consisting of \(k\) or \(k+ 1\) customers in the lobby. Each subset occurs exactly once, and then the last transition restores the original subset. Savage and Shields showed that \(H(2k+ 1, k)\) is Hamiltonian for \(k\leq 15\), and that \(H(2k+ 1, k)\) has a cycle of length at least as large as 86\% of the number of vertices. We prove that the bipartite Kneser graph \(H(n, k)\) is Hamiltonian for \(n> 3k\), and \(H(3k, k)\) is Hamiltonian when \({3k\choose k}\) is odd.