The name for a partial order - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:58:44Z http://mathoverflow.net/feeds/question/72260 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72260/the-name-for-a-partial-order The name for a partial order Victor Miller 2011-08-06T19:24:35Z 2011-08-06T19:52:17Z <p>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.</p> <p>Here is a description of the partial order:</p> <p>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).</p> <p>For reference, here's a link to Kundgen's paper: <a href="http://www.csusm.edu/akundgen/papers/isoperi.ps" rel="nofollow">http://www.csusm.edu/akundgen/papers/isoperi.ps</a></p> <p>Here's a link to our paper that uses it: <a href="http://arxiv.org/abs/0806.3284" rel="nofollow">http://arxiv.org/abs/0806.3284</a></p>