Opened 8 months ago

Closed 7 months ago

#31394 closed enhancement (fixed)

add Gritsenko's SRG(65, 32, 15, 16)

Reported by: dimpase Owned by:
Priority: major Milestone: sage-9.3
Component: graph theory Keywords:
Cc: gh-ferihr, dcoudert Merged in:
Authors: Dima Pasechnik Reviewers: David Coudert
Report Upstream: N/A Work issues:
Branch: 13d1474 (Commits, GitHub, GitLab) Commit: 13d14743b8f16a49d8fa9f563dfbb23c64bf365c
Dependencies: Stopgaps:

Status badges

Description

https://arxiv.org/abs/2102.05432 gives a construction of SRG(65, 32, 15, 16), which can be built as follows:

a=PermutationGroup([
 '(0)(1,17,2,18)(3,6,4,5)(7,31,8,32)(9,25,10,26)(11,14,12,13)(15,24,16,23)(19,22,20,21)(27,29,28,30)(33,35,34,36)(37,61,38,62)(39,55,40,56)(41,43,42,44)(45,53,46,54)(47,63,48,64)(49,52,50,51)(57,59,58,60)',
 '(0)(1,20,32,6,9,27,23,13,2,19,31,5,10,28,24,14)(3,8,22,18,11,15,29,25,4,7,21,17,12,16,30,26)(33,37,52,63,41,46,60,55,34,38,51,64,42,45,59,56)(35,39,58,53,44,47,49,62,36,40,57,54,43,48,50,61)'])
oe=[(0,1), (1,2), (1,6), (1,7), (1,9), (1,11), (1,14), (1,21), (1,24), (1,36), (1,38), (1,40), (1,42),
 (1,44), (1,47), (1,48), (1,50), (1,52), (1,54), (1,55), (1,56), (1,58), (1,62), (1,63), (1,64), (33,35),
 (33,38), (33,46), (33,47), (33,49), (33,51), (33,57), (33,61)]
ee=reduce(lambda x,y: x+y, map(lambda o: a.orbit(o,action='OnSets'), oe))
ggg=Graph(ee,format='list_of_edges')
ggg.is_strongly_regular(parameters=True)
# (65, 32, 15, 16)

we should add this construction.

Change History (21)

comment:1 Changed 8 months ago by dimpase

  • Branch set to u/dimpase/graphs/srg65
  • Commit set to 8453ffb849b047893b6c61dd09176a84c9133342

update of graph parameters db was needed too

comment:2 Changed 8 months ago by git

  • Commit changed from 8453ffb849b047893b6c61dd09176a84c9133342 to 1951a29709c20e85e8604fb77b026de81489cce1

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

1951a29updated parameters database (json)

comment:3 Changed 8 months ago by git

  • Commit changed from 1951a29709c20e85e8604fb77b026de81489cce1 to 15c678fef43c241eb099e3d51e5de487c6549ea8

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

15c678fGritsenko srg implementation and reference

comment:4 Changed 8 months ago by dimpase

  • Cc gh-ferihr dcoudert added
  • Status changed from new to needs_review

comment:5 Changed 8 months ago by dcoudert

  • Reviewers set to David Coudert

a small typo: O.Gritsenko's -> O. Gritsenko's

comment:6 Changed 8 months ago by dimpase

Thanks. Any other things to fix?

comment:7 follow-up: Changed 8 months ago by dcoudert

80 columns alignment for the comments and possibly for the graph and groups ?

comment:8 in reply to: ↑ 7 Changed 8 months ago by dimpase

Replying to dcoudert:

80 columns alignment for the comments and possibly for the graph and groups ?

I'd hate to chop strings into parts - do you instist on this?

comment:9 Changed 8 months ago by dcoudert

no.

comment:10 Changed 8 months ago by dcoudert

  • Status changed from needs_review to positive_review

LGTM.

comment:11 follow-up: Changed 7 months ago by vbraun

  • Status changed from positive_review to needs_work
sage -t --long --warn-long 36.1 --random-seed=0 src/sage/graphs/strongly_regular_db.pyx
**********************************************************************
File "src/sage/graphs/strongly_regular_db.pyx", line 3215, in sage.graphs.strongly_regular_db._check_database
Failed example:
    _check_database() # long time
Expected:
    Sage cannot build a (512  133  24   38  ) that exists. Comment ...
    ...
    In Andries Brouwer's database:
    - 462 impossible entries
    - 2916 undecided entries
    - 1160 realizable entries (Sage misses ... of them)
Got:
    Sage cannot build a (65   32   15   16  ) that exists. Comment from Brouwer's database: <a href="srgtabrefs.html#Gritsenko20">Gritsenko</a>; 2-graph*
    Sage cannot build a (512  133  24   38  ) that exists. Comment from Brouwer's database: <a href="srgtabrefs.html#Godsil92">Godsil</a>(q=8,r=3); pg(7,18,2)?
    Sage cannot build a (512  378  282  270 ) that exists. Comment from Brouwer's database: 
    Sage cannot build a (540  245  100  120 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (540  294  168  150 ) that exists. Comment from Brouwer's database: from 2-(45,5,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
    Sage cannot build a (780  369  168  180 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (780  410  220  210 ) that exists. Comment from Brouwer's database: from 2-(39,3,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
    Sage cannot build a (819  400  190  200 ) that exists. Comment from Brouwer's database: pg(20,19,10)?; 2-graph*
    Sage cannot build a (819  418  217  209 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph*
    Sage cannot build a (820  390  180  190 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (820  429  228  220 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph
    Sage cannot build a (1216 144  24   16  ) that exists. Comment from Brouwer's database: Wallis (AR(8,1)+S(2,3,19)); pg(18,7,2)?
    Sage cannot build a (1216 1071 942  952 ) that exists. Comment from Brouwer's database: 
    Sage cannot build a (1225 168  35   21  ) that exists. Comment from Brouwer's database: Wallis (AR(7,1)+S(2,4,25)); pg(24,6,3)?
    Sage cannot build a (1225 1056 908  924 ) that exists. Comment from Brouwer's database: 
    <BLANKLINE>
    In Andries Brouwer's database:
    - 462 impossible entries
    - 2911 undecided entries
    - 1165 realizable entries (Sage misses 15 of them)
**********************************************************************

comment:12 Changed 7 months ago by git

  • Commit changed from 15c678fef43c241eb099e3d51e5de487c6549ea8 to 13d14743b8f16a49d8fa9f563dfbb23c64bf365c

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

13d1474correct the srg database status in Sage

comment:13 in reply to: ↑ 11 Changed 7 months ago by dimpase

  • Status changed from needs_work to positive_review

Replying to vbraun:

sage -t --long --warn-long 36.1 --random-seed=0 src/sage/graphs/strongly_regular_db.pyx

yes, this doctest missed a fix, now added in comment:12. But I don't understand

> **********************************************************************
> File "src/sage/graphs/strongly_regular_db.pyx", line 3215, in sage.graphs.strongly_regular_db._check_database
...
>     Sage cannot build a (65   32   15   16  ) that exists. Comment from Brouwer's database: <a href="srgtabrefs.html#Gritsenko20">Gritsenko</a>; 2-graph*

because this can only happen if a test in lines 2966-8 of src/sage/graphs/generators/smallgraphs.py, where this construction is added, also fails.

For me now --long tests pass (merged over 9.3.beta8), so I'm setting this to positive review. Hopefully this will just work, and we don't need to dig deeper.

comment:14 Changed 7 months ago by dimpase

One possible explanation for the report in comment:11 would be that the update of graphs spkg on this ticket went in, but not the rest of the ticket.

comment:15 Changed 7 months ago by dcoudert

  • Status changed from positive_review to needs_work

I tried on macOS 10.15.7 and I still have reported error.

sapristi:sage dcoudert$ ./sage -t --long --random-seed=0 src/sage/graphs/strongly_regular_db.pyx
Running doctests with ID 2021-03-13-18-31-56-2edca818.
Git branch: HEAD
Using --optional=bliss,build,dochtml,homebrew,pip,python_igraph,sage,sage_numerical_backends_cplex,sage_spkg,tdlib,texttable
Doctesting 1 file.
sage -t --long --warn-long 302.0 --random-seed=0 src/sage/graphs/strongly_regular_db.pyx
**********************************************************************
File "src/sage/graphs/strongly_regular_db.pyx", line 3217, in sage.graphs.strongly_regular_db._check_database
Failed example:
    _check_database() # long time
Expected:
    Sage cannot build a (512  133  24   38  ) that exists. Comment ...
    ...
    In Andries Brouwer's database:
    - 462 impossible entries
    - 2911 undecided entries
    - 1165 realizable entries (Sage misses ... of them)
Got:
    Sage can build a (65, 32, 15, 16), Brouwer's database cannot
    Sage cannot build a (512  133  24   38  ) that exists. Comment from Brouwer's database: <a href="srgtabrefs.html#Godsil92">Godsil</a>(q=8,r=3); pg(7,18,2)?
    Sage cannot build a (512  378  282  270 ) that exists. Comment from Brouwer's database: 
    Sage cannot build a (540  245  100  120 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (540  294  168  150 ) that exists. Comment from Brouwer's database: from 2-(45,5,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
    Sage cannot build a (780  369  168  180 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (780  410  220  210 ) that exists. Comment from Brouwer's database: from 2-(39,3,1) with 1-factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2-graph
    Sage cannot build a (819  400  190  200 ) that exists. Comment from Brouwer's database: pg(20,19,10)?; 2-graph*
    Sage cannot build a (819  418  217  209 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph*
    Sage cannot build a (820  390  180  190 ) that exists. Comment from Brouwer's database: 2-graph
    Sage cannot build a (820  429  228  220 ) that exists. Comment from Brouwer's database: from ETF <a href="srgtabrefs.html#Fickus_et_al16">Fickus et al.</a>; 2-graph
    <BLANKLINE>
    In Andries Brouwer's database:
    - 462 impossible entries
    - 2916 undecided entries
    - 1160 realizable entries (Sage misses 10 of them)
**********************************************************************
1 item had failures:
   1 of   3 in sage.graphs.strongly_regular_db._check_database
    [330 tests, 1 failure, 23.42 s]
----------------------------------------------------------------------
sage -t --long --warn-long 302.0 --random-seed=0 src/sage/graphs/strongly_regular_db.pyx  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 23.5 seconds
    cpu time: 23.2 seconds
    cumulative wall time: 23.4 seconds

Am I missing something in how to test this ticket ?

comment:16 Changed 7 months ago by dimpase

...
Got:
   Sage can build a (65, 32, 15, 16), Brouwer's database cannot`
...

means you have not updated the graphs spkg.

Did you do make build ?

Last edited 7 months ago by dimpase (previous) (diff)

comment:17 Changed 7 months ago by dimpase

maybe you need to do

make graphs-clean && make graphs

comment:18 follow-up: Changed 7 months ago by dcoudert

  • Status changed from needs_work to positive_review

Oups...

Note that make graphs-clean && make graphs fails to download the package and in particular it don't try to use the specified upstream_url (why ?). So I downloaded it manually and then all tests pass.

I set this ticket back to positive review.

comment:19 in reply to: ↑ 18 Changed 7 months ago by dimpase

Replying to dcoudert:

Oups...

Note that make graphs-clean && make graphs fails to download the package and in particular it don't try to use the specified upstream_url (why ?).

this only works if configure was run with --enable-download-from-upstream-url.

So I downloaded it manually and then all tests pass.

I set this ticket back to positive review.

Thanks!

comment:20 Changed 7 months ago by dcoudert

so many options to configure and make. Not easy to remember them :P

comment:21 Changed 7 months ago by vbraun

  • Branch changed from u/dimpase/graphs/srg65 to 13d14743b8f16a49d8fa9f563dfbb23c64bf365c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.