MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Algorithm to compute certain poset from a given poset.

Hi. Associated with a finite poset $P$, one can consider the poset $S(P)$, whose elements are the intervals of $P$, ordered by inclusion. (See http://mathoverflow.net/questions/73640 for some motivation why to look at this).

Does anyone know if there is an algorithm around which, given $P$, computes $S(P)$? I think it is not very difficult to come up with one, but I just want to know if it has already been implemented, say, in some computer algebra system, or studied in the literature.

-
show 1 more comment

I cannot tell if this will help, but mention it just in case. The area of formal concept analysis deals with algorithms for constructing lattices from sets of objects and attributes. A concept is a tuple $C = (O, A, R)$, where $O$ and $A$ are sets and $R$ is a binary relation from $O$ to $A$. The relation gives rise to a standard function $f$ from the powerset of $O$ to the powerset of $A$.

$f$ maps $X \subseteq O$ to $\{ y \in A \mid \text{for all }x \in X, (x,y) \in R \}$

A function $g$ from the powerset of $A$ to powerset of $O$ is similarly defined such that $f$ and $g$ form a Galois connection. The concept lattice consists of the Galois stable subsets of $A$. By choosing the relation $R$, one can generate lattices with various properties. Algorithms for lattice construction are surveyed in:

Algorithms for the Construction of Concept Lattices and Their Diagram Graphs, Kuznetsov, Sergei O.; Obiedkov, Sergei A. (2001)

The Formal Concept Analysis site contains links to relevant material and software.

-

Assuming that by "interval" you mean something of the form [x,y] (as in the earlier question you linked to), you could just represent intervals by ordered pairs $(x,y)\in P\times P$ with $x\leq y$. The inclusion relation on intervals is easily expressible in terms of the order relation of $P$ because $[x,y]\subseteq[u,v]$ if and only if $u\leq x\leq y\leq v$.

If, on the other hand, you mean by "interval" an arbitrary order-convex subset of $P$, as Gerhard Paseman's comment seems to suppose, then I agree with his comment, and I would caution you that $S(P)$ could, under this interpretation, be exponentially bigger than $P$.

-