#19123: LatticePoset: add is_vertically_decomposable
-------------------------------------+-------------------------------------
Reporter: jmantysalo | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.9
Component: combinatorics | Resolution:
Keywords: | Merged in:
Authors: Jori Mäntysalo | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jmantysalo/vertically_decomposable|
893ecc133183398f0932e02c146f235230784915
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jmantysalo):
Now it should work with empty lattice, 1-element lattice and 2-element
lattice. There is backend ready for extending the function in
`lattices.py`. I may modify it as suggested by Nathann at comment 9. But
the more important question:
How should we exactly define "decomposing elements"? Let's start with
{{{
Posets.ChainPoset(2).ordinal_sum(Posets.BooleanLattice(3),
labels='integers')
}}}
Is `0` a decomposing element? What are "components" for the lattice? Maybe
`0-1`, `1-2` and `2-9`. But then, what are components of 2-element
lattice?
Replying to [comment:7 ncohen]:
> > If the poset has coverings `2 -> 6` and `4 -> 9`, then no element
`3..8` can be a decomposition element. After founding, say, `2 -> 6` we
could check `5 ->`, `4 ->` and so on. But after founding `4 -> 9` we
should have a somewhat complicated stack to skip re-checking biggest
covers of `4` and `5`. I guess that the algorithm would be slower in
reality, but I am quite sure that it would be better in some theoretical
meaning.
>
> HMmm... Skipping some edges without additional assumption on the order
in which they are returned?
I dont' mean that. If the lattice has `100` elements, then `0` is the
bottom and `99` is the top. If the lattice has coverings `0 -> 37`, `34 ->
88` and `77 -> 99`, then it is not vertically decomposable. There might be
faster way to find those coverings than going throught all elements. But
the code would be much more complicated.
--
Ticket URL: <http://trac.sagemath.org/ticket/19123#comment:10>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
