MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$:

share|cite|improve this question
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. – Simone Virili Feb 14 '13 at 14:35
up vote 5 down vote accepted

This order is sometimes denoted $L(k,n-k)$ and has many interesting properties. See for instance Chapter 6 of For the characteristic polynomial of the Hasse diagram of $L(k,n-k)$ (considered as a graph), see Remark 5.6 of

share|cite|improve this answer

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

share|cite|improve this answer
it seems like you have to use \lbrace and \rbrace instead. (in comments, \{ and \} work.) – Wolfgang Feb 15 '13 at 11:00
Thanks! I've used \{ and \} successfully in the past, but it must have been in the comments. – Michael Joyce 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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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