Opened 2 years ago

Closed 22 months ago

#25080 closed enhancement (fixed)

code for Cartesian factorization of posets

Reported by: chapoton Owned by:
Priority: major Milestone: sage-8.3
Component: combinatorics Keywords:
Cc: jmantysalo Merged in:
Authors: Frédéric Chapoton Reviewers: Jori Mäntysalo
Report Upstream: N/A Work issues:
Branch: 6ad6d44 (Commits) Commit: 6ad6d4400abe1e32812683da1a8301283bdb199c
Dependencies: Stopgaps:

Description (last modified by chapoton)

as a very useful tool to have

Change History (16)

comment:1 Changed 2 years ago by chapoton

  • Branch set to u/chapoton/25080
  • Cc jmantysalo added
  • Commit set to aaafd6a148397470a9cb6350b50991fc4b8b1e85
  • Description modified (diff)
  • Status changed from new to needs_review

New commits:

aaafd6acode for cartesian factorisation of posets

comment:2 Changed 2 years ago by git

  • Commit changed from aaafd6a148397470a9cb6350b50991fc4b8b1e85 to e1d1276ec1309b296a312bfc8cbc587d1981b947

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

e1d1276adding doi

comment:3 Changed 2 years ago by jmantysalo

  • Status changed from needs_review to needs_work

Fails with disconnected posets, see posets.AntichainPoset(4).factorize(). Works with the empty poset, but a test for the corner case would be nice.

Maybe this is the best name for this function; however, what will be the name for the converse of ordinal product?

I think that a factor of a lattice is always a lattice. Or is it? Got to think about this later.

E: Also, a test where the underlying undirected graph can be factorized, but the poset can not, would be nice.

Last edited 2 years ago by jmantysalo (previous) (diff)

comment:4 Changed 2 years ago by jmantysalo

Wrong indentation in the reference, i.e. may break Sphinx.

comment:5 Changed 2 years ago by git

  • Commit changed from e1d1276ec1309b296a312bfc8cbc587d1981b947 to c5e9234572681e19ede6a4e4dfbbd510996c09b5

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

c5e9234trac 25080 adding check that poset is connected

comment:6 Changed 2 years ago by git

  • Commit changed from c5e9234572681e19ede6a4e4dfbbd510996c09b5 to 4a72873d0c8a9bb4daebc0effc446e29c305b46f

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

4a72873trac 25080 adding more tests

comment:7 Changed 2 years ago by chapoton

Thanks for the comments, Jori.

For the name, my favorite choice would be just "factor". Other possibilies are "factor_cartesian" and "factor_ordinal" ; or maybe "cartesian_factor" and "ordinal_factor".

For the lattice property, I think this holds for the factors, and the same for MeetSemiLattice?, etc. But I do not feel any need for that.

comment:8 Changed 2 years ago by jmantysalo

See http://www.phy.olemiss.edu/~luca/Topics/p/poset_types.html: "Prime poset: One such that all its autonomous subsets are trivial." Is this the same concept with different words? If not, should that be mentioned in OUTPUT section?

Maybe "factor" or "factorize" is good, as also plain "product" means the Cartesian product.

Is it really a ValueError to run this with unconnected posets? IMO it should be seen as a missing implementation, as an unconnected poset can be a Cartesian product of two posets.

comment:9 Changed 2 years ago by jmantysalo

Error in seealso-link, cartesian_product() should be product().

Also there is now two seealso-blocks in product(), and it seems a little strange.

comment:10 Changed 2 years ago by git

  • Commit changed from 4a72873d0c8a9bb4daebc0effc446e29c305b46f to 6ad6d4400abe1e32812683da1a8301283bdb199c

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

6ad6d44trac 25080 change name to factor, other details

comment:11 Changed 2 years ago by chapoton

  • Status changed from needs_work to needs_review

All done.

There remains, maybe, the question of using LatticePoset for the factors when handling products of lattices.

comment:12 Changed 2 years ago by jmantysalo

Thanks. Now, to the code. When is if A1 != B1: evaluated as true? I guess you have implemented an algorithm to factor general digraph, and for poset you don't need all of that.

comment:13 Changed 2 years ago by chapoton

The idea is to check that every little square is a commutative square. There are certainly better ways than what I did quickly. The A1 != B1 test is meant to check that parallel arrows in one square go the same way.

The algorithm would possibly work for simple digraphs with no 2-cycles. Given this restricted domain, I think it is best to keep it here for the moment.

comment:14 Changed 2 years ago by jmantysalo

  • Reviewers set to Jori Mäntysalo
  • Status changed from needs_review to positive_review

OK, I'll mark this as positive review. (Change milestone when 8.3 is available.)

I don't see how there could be parallel arrows when the graph is the Hasse diagram of some poset. However, almost all the time is spent in factoring undirected graph, so this makes no real difference.

Output type for lattices can be changed later.

There are some shortcuts that could be used: for example the numbers of minimal elements must not be a prime. Also the number of edges in the Hasse diagram can show that a poset can't be a Cartesian product etc. However, all this can also be added later.

comment:15 Changed 23 months ago by jmantysalo

  • Milestone changed from sage-8.2 to sage-8.3

comment:16 Changed 22 months ago by vbraun

  • Branch changed from u/chapoton/25080 to 6ad6d4400abe1e32812683da1a8301283bdb199c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.