Opened 3 years ago

# Posets: Add converse of lexicographic sum

Reported by: Owned by: jmantysalo major sage-8.4 combinatorics Jori Mäntysalo N/A #25872

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.

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

OUTPUT:

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.

EXAMPLES:

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: })
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 == V
True
sage: decomp == N
True
sage: decomp.lexicographic_sum(decomp[1:]).relabel(lambda x: x) == P
True

.. SEEALSO::

- :meth:~`lexicographic_sum`

TESTS::

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):
part_dict[decomp] = decomp
return
for part in decomp:
if isinstance(part, int):
part_dict[part] = [part]
else:
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.