Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues
The \(q\)-analogue of the Kneser graph \(K(n,k)\) is the graph \(K_q(n,k)\), whose vertices are the \(k\)-subspaces of the \(n\)-dimensional vector space over the finite field with \(q\) elements and whose edges are the pairs of subspaces whose intersection is 0. It is shown that for any prime power \(q\) and for \(n\geq 2k\geq2\), the graph \(K_q(n,k)\) is hamiltonian, and in fact hamiltonian-connected. The key result in the proof is the following: If \(n\geq2k\geq2\), then \(K_q(n,k)\) is hamiltonian if \((\begin{smallmatrix} n-1\\ k-1\end{smallmatrix})_q\leq (\begin{smallmatrix} n-k\\ k\end{smallmatrix})_q\cdot q^{k^2}\), and hamiltonian-connected if the inequality is strict. The later result is analogous to the corresponding inequality that implies hamiltonicity for the Kneser graph \(K(n,q)\).
scientific article; zbMATH DE number 934992