2
$\begingroup$

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 Discrete version of Nullstellensatz? 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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Short answer: I don't know. Long answer: There is literature on the poset (lattice?) of ideals and filters in lattices and likely also arbitrary posets. Intervals being an intersection of a filter and an ideal, they may have been considered alongside such structures (possible keyword: convex). You might consider looking at the literature on the lattice of order ideals for lattices or other specific posets. You might be able to extend whatever algorithms they have to your situation. Gerhard "Ask Me About System Design" Paseman, 2011.09.02 $\endgroup$
    – Gerhard Paseman
    Commented Sep 2, 2011 at 16:47
  • $\begingroup$ I am not sure whether intervals can always be seen as the intersection you say (according to the definition of the cited post, i.e. something of the form [x,y]). Consider for instance the case where the filter and/or ideal are unions of principal ideals/filters. Then you have the union of two (disjoint) intervals, which is not something of the form [x,y] and is, in particular, not "convex". $\endgroup$
    – Camilo Sarmiento
    Commented Sep 5, 2011 at 12:37
  • $\begingroup$ Indeed, your notion of interval may not include the general case of an intersection of a filter and ideal. However, the literature may use convex, or it may use interval, in describing such intersections. If you are cautious in reading such literature, you may find it useful for answering your question. Gerhard "Ask Me About System Design" Paseman, 2011.09.07 $\endgroup$
    – Gerhard Paseman
    Commented Sep 7, 2011 at 19:14
  • $\begingroup$ Also, I cannot think of a poset where the intersection of an upset and a downset could be both nonempty and not convex. Your example of two disjoint (using your notion) intervals is convex in the context of a general poset. Of course, I am using what I understand for a notion of convexity; I have not seen your notion. Gerhard "Ask Me About System Design" Paseman, 2011.09.07 $\endgroup$
    – Gerhard Paseman
    Commented Sep 7, 2011 at 19:21
  • $\begingroup$ so, what is your definition of "convexity" in this case? $\endgroup$
    – Camilo Sarmiento
    Commented Sep 9, 2011 at 8:43

2 Answers 2

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .