Opened 3 years ago

Last modified 3 years ago

#25800 new enhancement

Posets: Add converse of lexicographic sum

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-8.4
Component: combinatorics Keywords:
Cc: Merged in:
Authors: Jori Mäntysalo Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #25872 Stopgaps:

Status badges

Description (last modified by jmantysalo)

Add decomposition of poset to prime posets (or chains or antichains), i.e. kind of converse of lexicographic_sum.

This should be useful for optimizing dimension and jump number. However I suppose that this is also nice to have as public method.

Change History (2)

comment:1 Changed 3 years ago by jmantysalo

  • Description modified (diff)

Something like this, I suppose. 8.3rc0 is out, so target will be 8.4.

def decompose(self):
    Decompose the poset to prime posets.

    A poset that is not prime can be expressed as a nontrivial
    lexicographic sum. This function decomposes the poset so that
    the index poset is as large as possible -- conversedly said, so
    that lexicographic summands are prime posets.

    Exceptions are chains and antichains. They are not decomposed;
    for example the 9-element chain could be written as the lexicographic
    sum of two 3-element chain using the 2-element chain as index poset.
    With this exception the decomposition is unique.

    A list of posets `[T, P_0, P_1, \ldots, P_{n-1}]`. Poset `T` is the
    index poset having integers `0, 1, \ldots, n-1` as
    elements. Posets `P_i` are either chains, antichains or prime posets.

    We create a lexicographic sum, decompose it back to parts and check
    by re-computing the sum::

        sage: V = Poset({1: [2, 3]})
        sage: N = Poset({1: [3, 4], 2: [4]})
        sage: C5 = posets.ChainPoset(5)
        sage: S3 = posets.StandardExample(3)
        sage: P = V.lexicographic_sum({1: N, 2: C5, 3: S3}); P
        Finite poset containing 12 elements
        sage: decomp = P.decompose()
        sage: decomp[0] == V
        sage: decomp[1] == N
        sage: decomp[0].lexicographic_sum(decomp[1:]).relabel(lambda x: x[0]) == P

    .. SEEALSO::
        - :meth:~`lexicographic_sum`
        sage: Poset().decompose()
        sage: posets.StandardExample(4).decompose()  # prime poset
        [Finite poset containing 1 elements, Finite poset containing 8 elements]
    H = self._hasse_diagram
    decomposition = H.transitive_closure().to_undirected().modular_decomposition()

    # First a trivial recursive decomposition.
    def rec_split(decomp, part_dict):
        if all(isinstance(x, int) for x in decomp[1]):
            part_dict[decomp[1][0]] = decomp[1]
        for part in decomp[1]:
            if isinstance(part, int):
                part_dict[part] = [part]
                rec_split(part, part_dict)

    D = {}
    rec_split(decomposition, D)

    # And now make and relabel the index poset.
    tmp = self.subposet([self._vertex_to_element(x) for x in D])
    t = D.keys()
    n = len(t)
    rel1 = {i:t[i] for i in range(n)}
    D = {i:D[rel1[i]] for i in range(n)}
    rel2 = {self[t[i]]:i for i in range(n)}
    return [tmp.relabel(rel2)] + [self.subposet(D[i]) for i in range(n)]

comment:2 Changed 3 years ago by jmantysalo

  • Dependencies set to #25872
  • Milestone changed from sage-wishlist to sage-8.4

On hold until #25872 is fixed.

Note: See TracTickets for help on using tickets.