Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues (Q1924237)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues |
scientific article |
Statements
Binomial and \(q\)-binomial coefficient inequalities related to the hamiltonicity of the Kneser graphs and their \(q\)-analogues (English)
0 references
24 November 1996
0 references
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)\).
0 references
\(q\)-analogue
0 references
Kneser graph
0 references
hamiltonian
0 references
hamiltonian-connected
0 references
hamiltonicity
0 references