9
$\begingroup$

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

$\endgroup$
1
  • 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, 2013 at 14:35

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The first link in the post no longer works - but it can still be found in the Wayback Machine. (Sorry for notifications from my several comments - I did not want to bump several old posts by editing, that's why I posted comments instead.) $\endgroup$ Jun 15, 2022 at 16:30
7
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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