Posets package: Unexpected behavior of poset method
Nobody has claimed this yet.
- Dominant language
- Macaulay2
- Stars
- 435
- Forks
- 297
- Avg merge
- 4d 20h
- Merged PRs (30d)
- 11
Description
From the documentation of the poset method we have
This method creates a Poset by defining the set and giving the order relations between the elements in the set. The function assumes that each element in the ground set G is distinct and operates by taking the transitive and reflexive closure of the relations in R.
It seems that the poset method only operates this way in case poset (List) or poset (List, List) is called. On the other hand, both poset (List, List, Matrix) and poset (List, Function) exhibit aberrant behavior.
For example, here is the Boolean lattice on one element, built from the single relation using poset (List) .
i1 : R = {{set {}, set {0}}};
i2 : P = poset R;
i3 : peek P
o3 = Poset{cache => CacheTable{...1...} }
GroundSet => {set {}, set {0}}
RelationMatrix => | 1 1 |
| 0 1 |
Relations => {{set {}, set {0}}}
The same poset can be built with the poset (G, cmp) method where cmp is set inclusion.
i4 : cmp = (s,t) -> set s <= set t;
i5 : P == poset (subsets 1, cmp)
o5 = true
But taking cmp to be strict set inclusion gives devious results. The method throws an error if we use the default antisymmetry strategy.
i6 : cmp = (s,t) -> set s < set t;
i7 : poset (subsets 1, cmp)
stdio:7:1:(3): error: The relations are not anti-symmetric.
The error message is incorrect: the relation defined by cmp is clearly anti-symmetric. The issue with the relation defined by cmp is that it is irreflexive, an issue that, according to the documentation, should be taken care of by the method.
Mysteriously, we can avoid the error message in the above example by using the digraph antisymmetry strategy.
i8 : poset (subsets 1, cmp, AntisymmetryStrategy => "digraph")
o8 = Relation Matrix: | 0 1 |
| 0 0 |
o8 : Poset
The result is of type Poset but the relation matrix does not encode the reflexive relations, so this also seems to be a bug.
Examining the source code we see that poset (List, List) is the only poset constructor that calls transitiveClosure. So since poset (List) calls poset (List, List), it yields the right result. On the other hand, poset (List, Function) calls poset (List, List, Matrix) which does not call transitiveClosure and so strange behavior ensues.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Read the Posets.m2 source linked in the issue, especially the poset(List, List), poset(List, List, Matrix), and poset(List, Function) constructors and their use of transitiveClosure. Reproduce the supplied strict-inclusion examples, then verify that each constructor produces the expected transitive and reflexive relation and reports the correct validation error.
Written by the indexing model from the issue text.
Assessment
- Domain
- tooling
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 35/100