For a positive integer $n > 1$, let $[n] = {1, 2, ..., n}$ and $V$ be the set of all k-subsets and $(n−k)$-subsets of $[n]$. The bipartite Kneser graph $H(n, k)$ has $V$ as its vertex set, and two vertices $A, B$ are adjacent if and only if $A ⊂ B$ or $B ⊂ A$.

We assume that $n ≥ 2k + 1$, or else the graph $H(n, k)$ would be null.

What is the connectivity of the bipartite Kneser graph $H(n, k)$? Is it just $^{n-k}C_n$? How can I approach this problem?

Further, is the graph $H(n, k)$ a symmetric (arc-transitive) graph?


migrated from mathoverflow.net Apr 2 '18 at 17:33

This question came from our site for professional mathematicians.

  • 4
    $\begingroup$ This would be better on math.stackexchange. The graph is arc-transitive and its vertex connectivity (by results of Mader and Watkins) is $\binom{n-k}k$. $\endgroup$ – Chris Godsil Mar 12 '18 at 14:35
  • $\begingroup$ @ChrisGodsil So what should i do now? $\endgroup$ – Jethro Mar 12 '18 at 22:53
  • $\begingroup$ you do not have to do anything, if enough people vote that way, your question could be transferred to math.stackexchange. Otherwise it stays here. $\endgroup$ – Chris Godsil Mar 12 '18 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.