Isomorphic multi digraphs have distinct number of spanning trees, bug?

[Georgi Guninski]

I need this for an algorithm, so even pointers to papers
will be appreciated.

The smallest bug I have is of order 36.

The attached file has two multi digraphs which are isomorphic,
but have distinct number of spanning trees.


print("isomorphic? ",G1.is_isomorphic(G2)) #True
print("equal trees?",G1.spanning_trees_count()==G2.spanning_trees_count())
#False
iso,map=G1.is_isomorphic(G2,certificate=True)
G3=G1.copy()
G3.relabel(lambda x: map[x])
print("verify iso",G3==G2) #True

[Emmanuel Briand]

Have you taken into account the following?

ignature:      G1.spanning_trees_count(root_vertex=None)
Docstring:     
   Return the number of spanning trees in a graph.

   In the case of a digraph, counts the number of spanning out-trees
   rooted in "root_vertex".  Default is to set first vertex as root.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD8LfAhfpRvgafWiL8cSX8-MrEhNbcOu0nKUt%2BGHnKLp3g%40mail.gmail.com.

[Georgi Guninski]

On Sun, Jun 18, 2023 at 10:16 AM Emmanuel Briand
<emmanue...@gmail.com> wrote:
>
> Have you taken into account the following?
>
> ignature: G1.spanning_trees_count(root_vertex=None)
> Docstring:
> Return the number of spanning trees in a graph.
>
> In the case of a digraph, counts the number of spanning out-trees
> rooted in "root_vertex". Default is to set first vertex as root.
>
>

Thanks, I should have RTFM.

This still doesn't work for me:

sage: G1.spanning_trees_count(root_vertex=None),G2.spanning_trees_count(root_ver
....: tex=None)
(27202601182632270746156805986464038912000,
40803901773948406119235208979696058368000)


Is it rigorous to set c1=G1.spanning_trees_count()
and then do:

sage: c1=G1.spanning_trees_count()
sage: for i in range(G1.order()):
....: c2=G2.spanning_trees_count(i)
....: if c2==c1: print(i)
....:
6

I expect for isomorphic multi digraphs the loop to find equal c1,c2?

[Dima Pasechnik]

It could be an integer overflow somewhere in the determinant
computation, as the numbers are very, very big.

By default, determinants are computed by flint, so it can be a bug there.
You can modify the code of spanning_trees_count() to allow passing of
the algorithm to compute determinant, and see if you can get it right.

HTH
Dima

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD_Zkf7g2py2PxWkYA4PqBOW6Ws%2BW31JtsQF2nmO6JE9tg%40mail.gmail.com.

[Vincent Delecroix]

sage: G1.spanning_trees_count(root_vertex=0)
27202601182632270746156805986464038912000
sage: G2.spanning_trees_count(root_vertex=6)
27202601182632270746156805986464038912000

> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD_Zkf7g2py2PxWkYA4PqBOW6Ws%2BW31JtsQF2nmO6JE9tg%40mail.gmail.com.

[Vincent Delecroix]

You could also check equality for all vertices with

sage: ans, isom = G1.is_isomorphic(G2, certificate=True)
sage: all(G1.spanning_trees_count(u) ==
G2.spanning_trees_count(isom[u]) for u in G1.vertices(sort=False))
True

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq2%2B_eejUwRr9M5%3DB%3Ddn36XMvU1hRbEQ_wwGu2obdWf2Kw%40mail.gmail.com.

[Dima Pasechnik]

On Sun, Jun 18, 2023 at 9:09 AM Vincent Delecroix

<20100.d...@gmail.com> wrote:
>
> sage: G1.spanning_trees_count(root_vertex=0)
> 27202601182632270746156805986464038912000
> sage: G2.spanning_trees_count(root_vertex=6)
> 27202601182632270746156805986464038912000

indeed, and for all other vertices I get
40803901773948406119235208979696058368000

so this is OK on my machine, at least.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGEwAAntJP%3DXemn%2BAmnYt6BfRfq8GujWQYZSpAjPyA81oOHxEw%40mail.gmail.com.

[Georgi Guninski]

On Sun, Jun 18, 2023 at 11:19 AM Dima Pasechnik <dim...@gmail.com> wrote:
>
> On Sun, Jun 18, 2023 at 9:09 AM Vincent Delecroix
> <20100.d...@gmail.com> wrote:
> >
> > sage: G1.spanning_trees_count(root_vertex=0)
> > 27202601182632270746156805986464038912000
> > sage: G2.spanning_trees_count(root_vertex=6)
> > 27202601182632270746156805986464038912000
>
> indeed, and for all other vertices I get
> 40803901773948406119235208979696058368000
>

Many thanks to all :)

Just to clarify:

1. If I don't equality for all V(G2) then G1,G2 are non-isomorphic
multi digraphs, right?
2. If I get equality for a single vertex (0 -> 6 in the example) then
then all isomorphisms map 0 to 6 (in this case
G1.automorphism_group().order() == 96)?

[Dima Pasechnik]

On Sun, 18 Jun 2023, 10:56 Georgi Guninski, <ggun...@gmail.com> wrote:

On Sun, Jun 18, 2023 at 11:19 AM Dima Pasechnik <dim...@gmail.com> wrote:
>
> On Sun, Jun 18, 2023 at 9:09 AM Vincent Delecroix
> <20100.d...@gmail.com> wrote:
> >
> > sage: G1.spanning_trees_count(root_vertex=0)
> > 27202601182632270746156805986464038912000
> > sage: G2.spanning_trees_count(root_vertex=6)
> > 27202601182632270746156805986464038912000
>
> indeed, and for all other vertices I get
> 40803901773948406119235208979696058368000
>


Many thanks to all :)

Just to clarify:

1. If I don't equality for all V(G2) then G1,G2 are non-isomorphic
multi digraphs, right?

yes

2. If I get equality for a single vertex (0 -> 6 in the example) then
then all isomorphisms map 0 to 6 (in this case
G1.automorphism_group().order() == 96)?

yes.

On the other hand, existence of such a 1-1 correspondence for all vertices between doesn't imply existence of an isomorphism. This follows from a general theorem by Cai-Furer-Immerman on 1st order logic with counting being insufficient for isomorphism recognition.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAGUWgD9DqNNy7TKExXz%2BaRkj7xni-STpaE%2BBO8tR3ouOLQzHsw%40mail.gmail.com.