The name for a partial order

2011-08-06T19:24:35Z

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

The name for a partial order - MathOverflow

The name for a partial order