In a recent paper of mine, my co-authors found that a partial order that we were using was contained in a paper by Kundgen. In it, he called it "right-shifted partial order". I was curious, and found that I couldn't find that term used anywhere other than in our paper and Kundgen's. It wasn't even in the Handbook of Combinatorics in the chapter on set systems. I wrote to Kundgen and asked where he got that terminology from. He told me that he had heard it in a seminar conducted by Doug West. I wrote to West, and he said that he had never heard of it! I have a sneaking suspicion that it's been used before but under a different name, and so would like to know what that name is.

Here is a description of the partial order:

The set over which we define the partial order is the set of finite subsets of $\mathbb{N}$ the positive integers. If $S$ is a finite subset of $\mathbb{N}$ denote by $S_i$ the $i$-th largest element of $S$. Say that $S \ge_R T$ if $|S| \ge |T|$ and $S_i \ge T_i$ for $i=1, \dots, |T|$. This is a refinement of the partial order given by set inclusion. The name "right-shifted" comes from the fact that if you make the standard identification of $S$ with the vector $(v_i)$ where $v_i = 1$ if $i \in S$ and $0$ otherwise and write this bit string big-endian then to get the elements which are $\le_R$ a particular bit vector we can shift any 1 "to the right" (including deleting it entirely).

For reference, here's a link to Kundgen's paper: http://www.csusm.edu/akundgen/papers/isoperi.ps

Here's a link to our paper that uses it: http://arxiv.org/abs/0806.3284

  • 1
    $\begingroup$ This looks like the partial order I used for my dissertation for ordering signatures of finite functional languages. I did not come up with a name for it, but I used the fact that it was well founded (and maybe some other property) to show that a certain class of sets was a class of recursive sets. Although I came up with my own proof of these properties, Libor Polak (who essentially simultaneously discovered one of the results of my dissertation) had proven these properties years before. He might know of a name. Gerhard "Ask Me About System Design" Paseman, 2011.08.05 $\endgroup$ – Gerhard Paseman Aug 6 '11 at 19:37
  • $\begingroup$ @Gerhard, Thanks. And I didn't realize that it had anything to do with Universal Algebra! $\endgroup$ – Victor Miller Aug 6 '11 at 19:45
  • $\begingroup$ I took the liberty of adding the universal-algebra tag, as both Libor Polak and I were doing work in that field. It would not surprise me if the order occurred in some earlier papers in model theory as well, but that's a guess on my part. Gerhard "Ask Me About System Design" Paseman, 2011.08.06 $\endgroup$ – Gerhard Paseman Aug 6 '11 at 19:46
  • 7
    $\begingroup$ In combinatorics this poset, restricted to subsets of {1,2...,n}, is denoted $M(n)$. For an application, see Sections 4.1.2-4.1.3 of math.mit.edu/~rstan/pubs/pubfiles/84.pdf. $\endgroup$ – Richard Stanley Aug 7 '11 at 0:12
  • 2
    $\begingroup$ @Richard, Thanks so much! Since there's an obvious inclusion $M(n) \rightarrow M(n+1)$ so that we have the direct limit $M(\infty)$. I'm interested in theorems about order ideals in $M(n)$. Can you supply any references? $\endgroup$ – Victor Miller Aug 7 '11 at 16:17

Your Answer

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

Browse other questions tagged or ask your own question.