Opened 4 years ago

Last modified 4 years ago

#19123 closed enhancement

LatticePoset: add is_vertically_decomposable — at Version 17

Reported by: jmantysalo Owned by:
Priority: major Milestone: sage-7.0
Component: combinatorics Keywords:
Cc: ncohen, tscrim, kdilks Merged in:
Authors: Jori Mäntysalo Reviewers:
Report Upstream: N/A Work issues:
Branch: u/jmantysalo/vertically_decomposable (Commits) Commit: 667173c9117e910378f3bc959821a7922a1f9c39
Dependencies: Stopgaps:

Description (last modified by jmantysalo)

This patch adds a function is_vertically_decomposable to finite lattices.

For testing see https://oeis.org/A058800 ; for example

sum([1 for L in Posets(6) if L.is_lattice() and
 not LatticePoset(L).is_vertically_decomposable()])

returns 7 as it should.

There is a place for possible optimization: If there is, say, covering relations bottom -> 5, 3 -> 8 and 7 -> top, is suffices to show that the lattice is not vertically decomposable. This might be faster on average. Now the complexity is linear to number of covering relations.

Change History (17)

comment:1 Changed 4 years ago by jmantysalo

  • Branch set to u/jmantysalo/vertically_decomposable

comment:2 Changed 4 years ago by jmantysalo

  • Cc ncohen added
  • Commit set to 0d472a68c9edf4ddea1404ff0cb6d2f508de55d0
  • Status changed from new to needs_review

Quite easy one. Nathann selected as a random victim for a possible reviewer. :=)


New commits:

decffe6Added function is_vertically_decomposable().
0d472a6Spaces on empty lines.

comment:3 follow-up: Changed 4 years ago by ncohen

Sounds good, but don't you think it may be useful to *know* where the poset splits? Also, why is it only defined for lattices? The algorithm works in all cases.

I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?

Nathann

comment:4 in reply to: ↑ 3 ; follow-up: Changed 4 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Replying to ncohen:

Sounds good, but don't you think it may be useful to *know* where the poset splits?

Yes, I think that will be usefull. For posets we have is_connected(), connected_components() and disjoint_union(). I guess we should have is_vertically_decomposable(), vertically_indecomposable_parts() and vertical_sum() for lattices.

There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements". The user could then run interval() on them to get parts.

Also, why is it only defined for lattices? The algorithm works in all cases.

How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.

I did not test it, but from the code's look I am not sure that it works for the chain of length 2, as the docstring indicates. Could you add a doctest for that?

Arghs! You are right, of course. I forget the special case when writing the code. I'll correct it.

(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)

comment:5 in reply to: ↑ 4 ; follow-up: Changed 4 years ago by ncohen

There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".

+1 to that.

How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.

Hmmm, okay okay... I attempted to write a definition, but indeed for non-lattices you have 1000 different corner-cases, and th definition would be a mess.

(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)

What do you mean? Your algorithm looks very reliable. I do not see it waste much.

Nathann

comment:6 in reply to: ↑ 5 ; follow-up: Changed 4 years ago by jmantysalo

Replying to ncohen:

There are of course other options, like having a function (this one, with an argument?) returning list of "decomposition elements".

+1 to that.

OK. What should be the name of the argument? certificate? give_me_the_list=True?

How should it be defined on non-connected posets? And I am not sure if this works with non-bounded posets; I thinked about bounded ones when writing this.

Hmmm, okay okay... I attempted to write a definition, but indeed for non-lattices you have 1000 different corner-cases, and th definition would be a mess.

Except for the 2-element lattice there is one simple definition that generalizes this:

any(P.cover_relations_graph().is_cut_vertex(e) for e in P)

But in any case, it is easy to move this to posets later if we want so.

(Btw, this would be nice exercise of (totally unneeded) optimization. One should not need to look for all edged of Hasse diagram to see that a poset is indecomposable.)

What do you mean? Your algorithm looks very reliable. I do not see it waste much.

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.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 4 years ago by ncohen

OK. What should be the name of the argument? certificate? give_me_the_list=True?

Isn't there a terminology for those points? If it is only for lattices, maybe you could have return_cutvertices=True or something?

Except for the 2-element lattice there is one simple definition that generalizes this:

any(P.cover_relations_graph().is_cut_vertex(e) for e in P)

Wouldn't work for a poset on three elements, one being greater than the two others (which are incomparable).

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 do not know... This is not so bad, for the moment :-)

Nathann

comment:8 Changed 4 years ago by git

  • Commit changed from 0d472a68c9edf4ddea1404ff0cb6d2f508de55d0 to 893ecc133183398f0932e02c146f235230784915

Branch pushed to git repo; I updated commit sha1. New commits:

893ecc1Added an option to get "decomposing elements".

comment:9 Changed 4 years ago by ncohen

You don't have to write this algorithm twice to make it work in all situations. Once is enough. And if you are worried of the cost of a 'if' inside of the loop, then you should not be writing Python code.

Furthermore, be careful with '::' as they are not needed after an INPUT block. Build the doc to check it.

Nathann

comment:10 in reply to: ↑ 7 Changed 4 years ago 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 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.

comment:11 follow-up: Changed 4 years ago by ncohen

Could you also add to your docstring a reference toward a textbook that defines this notion?

comment:12 Changed 4 years ago by git

  • Commit changed from 893ecc133183398f0932e02c146f235230784915 to ca909a0c05fee489a071ff672b9f3b5392ba8158

Branch pushed to git repo; I updated commit sha1. New commits:

ca909a0Indentation of INPUT block.

comment:13 in reply to: ↑ 11 Changed 4 years ago by jmantysalo

  • Cc tscrim added
  • Description modified (diff)

Replying to ncohen:

Could you also add to your docstring a reference toward a textbook that defines this notion?

Duh. Counting Finite Lattices by Heitzig and Reinhold defines it "- - contains an element which is neither the greatest not the least element of L but comparable to every element of L." On the other hand, On the number of distributive lattices by Erné and (same) Heitzig and Reinhold says "- - if it is either a singleton or the vertical sum of two nonempty posets - -", and vertical sum on two two-element lattice by their definition is the two-element lattice.

I select tscrim as another random victim. Travis, should we define the two-element lattice to be vertically decomposable or indecomposable?

(Or raise OtherError("developers don't know how to define this")? :=))

comment:14 Changed 4 years ago by jmantysalo

OEIS uses the definition where the two-element lattice is vertically indecomposable: https://oeis.org/A058800. Does this suffice as a base for the definition?

comment:15 Changed 4 years ago by ncohen

Helloooooooo !

Yeah yeah I guess. Could you just add a link in the doc toward a textbook/paper that defines it the way you use it?

(Or raise OtherError?("developers don't know how to define this")?

We have had very non-enlightening debates here about whether the empty graph is connected or not. In such a situation, I would add such a warning rather than have those stupid conversations :-P Nathann

comment:16 Changed 4 years ago by git

  • Commit changed from ca909a0c05fee489a071ff672b9f3b5392ba8158 to 667173c9117e910378f3bc959821a7922a1f9c39

Branch pushed to git repo; I updated commit sha1. New commits:

667173cOptions to is_vertically_decomposable().

comment:17 Changed 4 years ago by jmantysalo

  • Description modified (diff)

This code should now work.

I still don't know how to make the user interface... For posets we have boolean-valued is_connected() and subposets-valued connected_components(). But what should then be the function returning only "decomposing elements". I will ask in sage-devel.

Comments on documentation are welcome.

Note: See TracTickets for help on using tickets.