Check easy invariants first for simplicial complex isomorphism

[tscrim]

In order to more quickly check if two simplicial complexes are not isomorphic, we should check that their (ordered) facet dimension sequences agree.

We also check that edge labels are respected for the isomorphism, so isomorphisms of the fake degree vertex is not part of the isomorphism.

Depends on #20720

CC: @jhpalmieri @sagetrac-jeremy-l-martin

Component: algebraic topology

Keywords: days74

Author: Travis Scrimshaw

Branch: fbe4c3d

Reviewer: John Palmieri

Issue created by migration from https://trac.sagemath.org/ticket/20751

[tscrim]

New commits:

7b1a299	Having vertices() return a tuple instead of a Simplex.
3ace10e	Fixing a doctest in combinat/cluster_complex.py.
00c48e8	trac 20720: referee changes

[tscrim]

Commit: 00c48e8

[tscrim]

Dependencies: #20720

[tscrim]

Branch: public/simplicial_complex/check_easy_invariants-20751

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 00c48e8 to 0af2d7f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0af2d7f

Added check against the facet dimension sequence.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

69709a2

Make sure edge labels are respected

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0af2d7f to 69709a2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 69709a2 to fbe4c3d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

fbe4c3d

Some doc tweaks reflecting then new behavior.

[tscrim]

Description changed:

--- 
+++ 
@@ -1 +1,3 @@
 In order to more quickly check if two simplicial complexes are not isomorphic, we should check that their (ordered) facet dimension sequences agree.
+
+We also check that edge labels are respected for the isomorphism, so isomorphisms of the fake degree vertex is not part of the isomorphism.

[jhpalmieri]

comment:6

I think the initial checks can slow things down. Actually, if two complexes are not isomorphic for "obvious" reasons, it is now much faster (by a factor of 40 on my machine) to check that they are not, but if they are actually isomorphic, it is slower (by a factor of 2) to check that. For these timings, I used the complexes Z1, Z2, Z3 from the doctests, and ran

%timeit Z1.is_isomorphic(Z2)  # True
%timeit Z1.is_isomorphic(Z3)  # False

[tscrim]

comment:7

It is not the initial checks that are slowing it down, it is the additional check(s) of edge labels for the graph isomorphism. The additional checks are very small (< 1%) in comparison to the isomorphism check (both with and without edge label checks), which you can see via

%lprun -f X.is_isomorphic X.is_isomorphic(X)

However, Jeremy found it necessary to check the edge labels, at least when we want the certificate. Yet we don't have an example where there is not an isomorphism but the graphs are isomorphic without preserving edge labels. So it might be feasible that we don't need to check the edge labels in that case...

[jhpalmieri]

Reviewer: John Palmieri

[vbraun]

Changed branch from public/simplicial_complex/check_easy_invariants-20751 to fbe4c3d

[jdemeyer]

Changed commit from fbe4c3d to none

[jdemeyer]

comment:10

Exactly what is this doctest supposed to test?

        We check that :trac:`20751` is fixed::

            sage: C1 = SimplicialComplex([[1,2,3], [1,2,4], [1,3,4]])
            sage: C2 = SimplicialComplex([['j','k','l'], ['j','l','m'], ['j','k','m']])
            sage: C1.is_isomorphic(C2, certificate=True)
            (True, {1: 'j', 2: 'k', 3: 'l', 4: 'm'})

I am asking because the output is not unique (one can exchange vertices 2, 3 and 4).

[jdemeyer]

comment:11

I'll update that test to one with a unique output at #27027.

[tscrim]

comment:12

I believe the fake_vertex was getting added to the certificate in that test before this ticket.

[jdemeyer]

comment:13

Thanks for the info. So it shouldn't be a problem to replace that test with a different one.