# Partial order relation on subsets

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

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

• Essentially you are taking strictly increasing maps from {1,...,k} to {1,...,n}. Than, given two strictly increasing maps $f,g:\{1,...,k\}\to \{1,\dots,n\}$ you say that $f\prec g$ if $f(i)\leq g(i)$ for all $i\in\{1,\dots,k\}$. I would call it just a pointwise order... I cannot help you with any reference. Feb 14 '13 at 14:35

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.
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}$.
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.