Question

I consider all $k$ element subsets of the set $\{1,\ldots,n\}$ and define a partial order relation $\prec$ as follows: $\{a_1,\ldots,a_k\}\prec\{b_1,\ldots,b_k\}$, if and only if $a_1<\cdots<a_k$, $b_1<\cdots<b_k$ and $a_i\leq b_i$ for all $i=1,\ldots,k$.

What is this partial order commonly called in the literature? Can someone point out references?

Thanks a lot, Torsten

[edit] Here is a Hasse diagram of this partial order for $n=6$ and $k=3$: http://www.freeimagehosting.net/7pmk7

Answer 1

This order is sometimes denoted $L(k,n-k)$ and has many interesting properties. See for instance Chapter 6 of http://math.mit.edu/~rstan/algcomb.pdf. For the characteristic polynomial of the Hasse diagram of $L(k,n-k)$ (considered as a graph), see Remark 5.6 of http://math.mit.edu/~rstan/papers/vac.pdf.

Answer 2

This is the Bruhat order on $S_n / (S_k \times S_{n-k})$, which models the inclusion relations of Schubert varieties on the Grassmannian $Gr(k,n)$. The elements of $S_n / (S_k \times S_{n-k})$ are generally modeled by their minimal length representatives, called Grassmann permutations. You can biject your $k$-subset of $[n]$ to a Grassmann permutation by sending a $k$-subset $\lbrace{ a_1, \dots, a_k \rbrace}$ (with $a_1 < a_2 < \dots < a_k$) to the permutation of $[n]$ whose window (one-line) notation is $a_1 a_2 \cdots a_k b_1 b_2 \cdots b_{n-k}$ with $\lbrace{ b_1, b_2, \dots, b_{n-k} \rbrace}$ denoting the complement of your given set, again ordered in increasing order $b_1 < b_2 < \cdots < b_{n-k}$.

Answer 3

I call this the compression order on $[n]^{(r)}$, because it is the order induced by the operation of left-compression (or left-shifting) used in extremal set theory.