Intervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets? - MathOverflow most recent 30 from http://mathoverflow.net2013-06-19T05:41:18Zhttp://mathoverflow.net/feeds/question/74297http://www.creativecommons.org/licenses/by-nc/2.5/rdfhttp://mathoverflow.net/questions/74297/intervals-in-posets-how-to-extend-interval-orders-allens-algebra-and-intervalIntervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets?Cliff Joslyn2011-09-01T21:43:30Z2011-09-03T01:35:22Z
<h2>BACKGROUND</h2>
<p>Assume a poset $\langle P, \le \rangle$. For two points $a,b \in P$
with $a \le b$, then $I = [a,b] = \{ x : a \le x \le b \}$ is the
interval between $a$ and $b$.</p>
<p>When $P$ is a chain (e.g. ${\mathbb Z}, {\mathbb R}$), then the $I$
are just standard intervals. Two real intervals $I=[a,b],J=[c,d]
\subseteq {\mathbb R}$ are ordered usually to mean that $I \le J$ iff
$b \le c$. Call this the "strong order", which isn't actually a proper
order (it needs to be "reflexivized" to require that $I \le I$). Two
other true orders are also available, namely that $a \le c$ and $b \le
d$ (the product order of the endpoints), or that $a \le c$ and $b \ge
d$ (subset order). These last two are conjugate orders. All of these
are defined in the context of Allen's alegbra, enumerating all the
possible relations between $I,J$ given combinations of both equal and
unequal endpoints.</p>
<p>Additionally, the intersection graphs of sets of real intervals are
interval graphs, which are well studied.</p>
<h2>MOTIVATION</h2>
<p>We work with data objects represented as finite, bounded posets.
Analyzing the intervals therein, and their orderings and
intersections, is very useful in a range of applications in layout and
display. </p>
<h2>QUESTION</h2>
<p>We are thus seeking extensions from real intervals to poset intervals
for the concepts of interval order, Allen's algebra, and inteveral
graphs. Our preliminary literature reviews haven't turned up anything,
and we're preparing to start the development from first
principles. Pointers appreciated, thanks!</p>
http://mathoverflow.net/questions/74297/intervals-in-posets-how-to-extend-interval-orders-allens-algebra-and-interval/74411#74411Answer by Richard Stanley for Intervals in posets: how to extend interval orders, Allen's algebra, and interval graphs to intervals of posets?Richard Stanley2011-09-03T01:35:22Z2011-09-03T01:35:22Z<p>The subset order on intervals of a finite poset has received some
attention. See for example Exercises 3.10, 3.76(b), 3.138, and 3.158(c)
of <a href="http://math.mit.edu/~rstan/ec/ec1.pdf" rel="nofollow">http://math.mit.edu/~rstan/ec/ec1.pdf</a>.</p>