#14019: equality is broken for Posets
-------------------------------------+-------------------------------------
Reporter: ncohen | Owner: sage-combinat
Type: defect | Status: needs_work
Priority: major | Milestone: sage-6.4
Component: combinatorics | Resolution:
Keywords: posets | Merged in:
Authors: Travis Scrimshaw, | Reviewers: Travis Scrimshaw,
Anne Schilling | Anne Schilling
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/combinat/poset/fix_equality-14019|
115a32500018148858b06dc0040fc0a4e506041a
Dependencies: #17059 | Stopgaps: #14185
-------------------------------------+-------------------------------------
Comment (by tscrim):
Replying to [comment:66 ncohen]:
> > That condition is fine, but the labeling of the "canonical" labeling
is still arbitrary and not unique (as you can see, it has changed).
>
> No, it is unique. And it is always integers from 0 to n-1.
>
> Try it in Sage: take a graph `D1` labelled on whatever you want, then
compute its canonical representative `R`. Then relabel the vertices of
`D1` into a graph `D2` in any way you like: the representatie of `D2` will
be equal to `R`.
However the labeling itself is not unique. Consider the path on 3 vertices
with labelings `0 - 1 - 2` and `1 - 0 - 2`. The first one is no more
canonical than the second.
> Two pairs "Poset, linear_extension" are "isomorphic" if there is an
isomorphism of the two posets that sends the first linear extension on the
second linear extension. But we never check this second part (and
similarly for the canonical representatives).
> For instance, if `P` is a poset on three points 0,1,2 where the cover
relations are only (1<2), then the pair "Poset, linear extension" equal to
`P,[0,1,2]` is not isomorphic to `P,[1,0,2]`.
>
> > No, it checks that the posets are isomorphic (which has nothing to do
with the linear extension chosen).
>
> Indeed, and to me that is incorrect. It is quite simple: you cannot say
that two "posets with linear extension" `P1,P2` are isomorphic unless
there is a relabel function `f` such that `P1.relabel(f)==P2`.
>
> As it is implemented right now this does not hold.
It depends on what we want to actually check. Yet as currently stated in
the documentation of `is_isomorphic`, it does return the correct value as
it checks "if both posets are isomorphic". My thought is that ''if'' we
decide we want to also check with a specified linear extension, then we
add another argument to `is_isomorphic`. At present, the method should not
raise an error, and this should probably be done on another ticket.
Anyways, doctests are now all fixed.
--
Ticket URL: <http://trac.sagemath.org/ticket/14019#comment:68>
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.
