Binomial andQ-Binomial Coefficient Inequalities Related to the Hamiltonicity of the Kneser Graphs and TheirQ-Analogues
✍ Scribed by W.Edwin Clark; Mourad E.H. Ismail
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 449 KB
- Volume
- 76
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
The Kneser graph K(n, k) has as vertices all the k-subsets of a fixed n-set and has as edges the pairs [A, B] of vertices such that A and B are disjoint. It is known that these graphs are Hamiltonian if ( n&1 k&1 ) ( n&k k ) for n 2k+1. We determine asymptotically for fixed k the minimum value n=e(k) for which this inequality holds. In addition we give an asymptotic formula for the solution of k1 (n) 1 (n&2k+1)= 1 2 (n&k+1) for n 2k+1, as k Ä , when n and k are not restricted to take integer values. We also show that for all prime powers q and n 2k, k 1, the q-analogues K q (n, k) are Hamiltonian by consideration of the analogous inequality for q-binomial coefficients.