Posets: Add is_series_parallel()

[jm58660]

Add a function to see if a poset is series-parallel (or "N-free").

First wait for #19659 to get closed. Series-parallel decomposition is just recursive applying of connected_components() and ordinal_sum_decomposition().

CC: @fchapoton

Component: combinatorics

Keywords: poset

Author: Jori Mäntysalo

Branch/Commit: b4b3254

Reviewer: Frédéric Chapoton

Issue created by migration from https://trac.sagemath.org/ticket/19215

[nathanncohen]

comment:1

Do we agree that being series-parallel is not at all equivalent to being prime in the sense of modular decomposition?

[jm58660]

comment:2

Replying to @nathanncohen:

Do we agree that being series-parallel is not at all equivalent to being prime in the sense of modular decomposition?

Arghs, is_prime() was not what I think. So maybe there is no direct function to wrap. But anyway, if modular_decomposition() ends "withot any Prime", then the corresponding poset is N-free.

Thanks for correcting.

[jm58660]

comment:4

Now we have both pieces for decomposition. Next, what should be the return type be? modular_decomposition() of a graph returns a tuple of tuples of tuples etc. But is there some tree class ready for this?

"Horizontal decomposition", i.e. connected_components() is commutative, but "vertical decomposition" of course is not. But I guess we don't have a tree for this specific situation. Maybe Frédéric can comment on this.

[jm58660]

Branch: u/jmantysalo/posets__add_is_series_parallel__

[jm58660]

Commit: b4b3254

[jm58660]

comment:6

I made at least the boolean (and maybe slow) version of this function. Anyways, better than nothing; a reviewer can check the documentation etc.

---

New commits:

b4b3254

Added is_series_parallel().

[saraedum]

Author: Jori Mäntysalo

[fchapoton]

Changed keywords from none to poset

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:9

looks good to me

[vbraun]

Changed branch from u/jmantysalo/posets__add_is_series_parallel__ to b4b3254