# Connectivity of bipartite Kneser graph

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.netApr 2 '18 at 17:33

This question came from our site for professional mathematicians.

• 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$. – Chris Godsil Mar 12 '18 at 14:35
• @ChrisGodsil So what should i do now? – Jethro Mar 12 '18 at 22:53
• 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. – Chris Godsil Mar 12 '18 at 23:31