bug in computing automorphism group of IncidenceStructure

[dimpase]

From sage-devel thread

B = [[1, 2, 3, 5, 7, 10],
 [1, 2, 3, 7, 10, 11],
 [1, 2, 4, 6, 9, 10],
 [1, 2, 4, 7, 8, 10],
 [1, 2, 5, 6, 10, 11],
 [1, 2, 7, 8, 9, 10],
 [2, 3, 4, 5, 9, 10],
 [2, 3, 4, 9, 10, 11],
 [2, 4, 5, 8, 10, 11],
 [2, 4, 6, 7, 9, 10],
 [2, 5, 6, 7, 10, 11],
 [2, 5, 8, 9, 10, 11]]
C = B + [[1..11]]
I1 = IncidenceStructure([1..11],B)
I2 = IncidenceStructure([1..11],C)
A1 = I1.automorphism_group()
A2 = I2.automorphism_group()
A1.order()==A2.order()

returs false - the group orders are 96 and 32, rather than equal to 96.
This still is correct (same group) in Sage 8.9 with Python 2, but wrong in 9.1.rc0 as well as in 9.0 (with Python 3).

CC: @dcoudert

Component: graph theory

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

[Shlokatadistance]

comment:1

Can it not be possible that the case is like a particular nuance? because as reported by the user in Sage-Devel, the results were accurate for the other test cases?
p.s : Just an observation, nevertheless, it needs to be fixed

[dimpase]

comment:2

it is indeed a corner case, as the "full" block, as added in C, is not usual. If you want to fix this, look at the code of IncidenceStructure and check that the automorphism group of the incidence graph constructed there is not correct, for some reason.

[soehms]

comment:3

I could reproduce the bug with version 9.1.rc0 under Python 2 and on a stable 8.1, too. So it seemes, that it is older than 8.9 but disappeared for a while.

[Shlokatadistance]

comment:4

I am trying to come up with a fix, but can someone suggest a few more test cases? Especially since we think this is a potential corner case, I dont want to suggest a fix which will output the wrong answer for the other right ones

[slel]

comment:6

Possibly related: #30637. Does your fix also solve that?

[soehms]

comment:7

I think this bug is located in search_tree (sage.groups.perm_gps.partn_ref.refinement_graphs) since with optional package bliss installed it is not reproducible.

Samuel, does #30637 fail with bliss, as well?

[dimpase]

comment:8

I can confirm that after installing bliss, the issue here goes away.

[dimpase]

comment:9

by the way, without (and with) bliss, still

sage: g1=I1.incidence_graph()                                                                                                                                           
sage: g2=I2.incidence_graph()                                                                                                                                           
sage: g1.automorphism_group().order()                                                                                                                                   
96
sage: g2.automorphism_group().order()                                                                                                                                   
96

are correct. As well, wihout bliss,

sage: I2.dual().automorphism_group().order()                                                                                                                            
48
sage: I1.dual().automorphism_group().order()                                                                                                                            
48

which is consistent with 96/2=48 (there are two points, 2 and 10, which are in all the blocks, so there is an order two automorhism (2,10) fixing all blocks).

[mkoeppe]

comment:11

Moving to 9.4, as 9.3 has been released.

[fchapoton]

comment:13

bump to 9.6