Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

3 Answers

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

share|improve this answer
add comment

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|improve this answer
1  
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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.