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:  sage9.3 
Component:  graph theory  Keywords:  
Cc:  ghferihr, dcoudert  Merged in:  
Authors:  Dima Pasechnik  Reviewers:  David Coudert 
Report Upstream:  N/A  Work issues:  
Branch:  13d1474 (Commits, GitHub, GitLab)  Commit:  13d14743b8f16a49d8fa9f563dfbb23c64bf365c 
Dependencies:  Stopgaps: 
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
 Branch set to u/dimpase/graphs/srg65
 Commit set to 8453ffb849b047893b6c61dd09176a84c9133342
comment:2 Changed 8 months ago by
 Commit changed from 8453ffb849b047893b6c61dd09176a84c9133342 to 1951a29709c20e85e8604fb77b026de81489cce1
Branch pushed to git repo; I updated commit sha1. New commits:
1951a29  updated parameters database (json)

comment:3 Changed 8 months ago by
 Commit changed from 1951a29709c20e85e8604fb77b026de81489cce1 to 15c678fef43c241eb099e3d51e5de487c6549ea8
Branch pushed to git repo; I updated commit sha1. New commits:
15c678f  Gritsenko srg implementation and reference

comment:4 Changed 8 months ago by
 Cc ghferihr dcoudert added
 Status changed from new to needs_review
comment:5 Changed 8 months ago by
 Reviewers set to David Coudert
a small typo: O.Gritsenko's
> O. Gritsenko's
comment:6 Changed 8 months ago by
Thanks. Any other things to fix?
comment:7 followup: ↓ 8 Changed 8 months ago by
80 columns alignment for the comments and possibly for the graph and groups ?
comment:8 in reply to: ↑ 7 Changed 8 months ago by
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
no.
comment:11 followup: ↓ 13 Changed 7 months ago by
 Status changed from positive_review to needs_work
sage t long warnlong 36.1 randomseed=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>; 2graph* 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: 2graph Sage cannot build a (540 294 168 150 ) that exists. Comment from Brouwer's database: from 2(45,5,1) with 1factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2graph Sage cannot build a (780 369 168 180 ) that exists. Comment from Brouwer's database: 2graph Sage cannot build a (780 410 220 210 ) that exists. Comment from Brouwer's database: from 2(39,3,1) with 1factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2graph Sage cannot build a (819 400 190 200 ) that exists. Comment from Brouwer's database: pg(20,19,10)?; 2graph* 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>; 2graph* Sage cannot build a (820 390 180 190 ) that exists. Comment from Brouwer's database: 2graph 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>; 2graph 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
 Commit changed from 15c678fef43c241eb099e3d51e5de487c6549ea8 to 13d14743b8f16a49d8fa9f563dfbb23c64bf365c
Branch pushed to git repo; I updated commit sha1. New commits:
13d1474  correct the srg database status in Sage

comment:13 in reply to: ↑ 11 Changed 7 months ago by
 Status changed from needs_work to positive_review
Replying to vbraun:
sage t long warnlong 36.1 randomseed=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>; 2graph*
because this can only happen if a test in lines 29668 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
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
 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 randomseed=0 src/sage/graphs/strongly_regular_db.pyx Running doctests with ID 202103131831562edca818. 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 warnlong 302.0 randomseed=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: 2graph Sage cannot build a (540 294 168 150 ) that exists. Comment from Brouwer's database: from 2(45,5,1) with 1factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2graph Sage cannot build a (780 369 168 180 ) that exists. Comment from Brouwer's database: 2graph Sage cannot build a (780 410 220 210 ) that exists. Comment from Brouwer's database: from 2(39,3,1) with 1factor <a href="srgtabrefs.html#Fickus_et_al15">Fickus et al.</a>; 2graph Sage cannot build a (819 400 190 200 ) that exists. Comment from Brouwer's database: pg(20,19,10)?; 2graph* 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>; 2graph* Sage cannot build a (820 390 180 190 ) that exists. Comment from Brouwer's database: 2graph 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>; 2graph <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 warnlong 302.0 randomseed=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
... 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
?
comment:17 Changed 7 months ago by
maybe you need to do
make graphsclean && make graphs
comment:18 followup: ↓ 19 Changed 7 months ago by
 Status changed from needs_work to positive_review
Oups...
Note that make graphsclean && 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
Replying to dcoudert:
Oups...
Note that
make graphsclean && make graphs
fails to download the package and in particular it don't try to use the specifiedupstream_url
(why ?).
this only works if configure was run with enabledownloadfromupstreamurl
.
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
so many options to configure and make. Not easy to remember them :P
comment:21 Changed 7 months ago by
 Branch changed from u/dimpase/graphs/srg65 to 13d14743b8f16a49d8fa9f563dfbb23c64bf365c
 Resolution set to fixed
 Status changed from positive_review to closed
update of graph parameters db was needed too