Binomial andQ-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and TheirQ-Analogues

The Kneser graphK(n, k) has as vertices all thek-subsets of a fixedn-set and has as edges the pairs {A, B} of vertices such thatAandBare disjoint. It is known that these graphs are Hamiltonian if[formula]forn⩾2k+1. We determine asymptotically for fixedkthe minimum valuen=e(k) for which this inequality holds. In addition we give an asymptotic formula for the solution ofkΓ(n) Γ(n−2k+1)=Γ2(n−k+1) forn⩾2k+1, ask→∞, whennandkare not restricted to take integer values. We also show that for all prime powersqandn⩾2k,k⩾1, theq-analoguesKq(n, k) are Hamiltonian by consideration of the analogous inequality forq-binomial coefficients.