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

  • 2
    $\begingroup$ 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. $\endgroup$ 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}$.

  • 1
    $\begingroup$ it seems like you have to use \lbrace and \rbrace instead. (in comments, \{ and \} work.) $\endgroup$
    – Wolfgang
    Feb 15 '13 at 11:00
  • $\begingroup$ Thanks! I've used \{ and \} successfully in the past, but it must have been in the comments. $\endgroup$ Feb 15 '13 at 12:37

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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.