Opened 6 years ago
Closed 6 years ago
#19317 closed enhancement (fixed)
A (1288,792,476,504)strongly regular graph
Reported by:  ncohen  Owned by:  

Priority:  major  Milestone:  sage6.10 
Component:  graph theory  Keywords:  
Cc:  dimpase  Merged in:  
Authors:  Nathann Cohen  Reviewers:  Dima Pasechnik 
Report Upstream:  N/A  Work issues:  
Branch:  f6272d3 (Commits, GitHub, GitLab)  Commit:  f6272d39e0de839ef4e28e28d3d8fd207fe6cbae 
Dependencies:  Stopgaps: 
Description
As the title says.
Change History (17)
comment:1 Changed 6 years ago by
 Branch set to u/ncohen/19317
 Commit set to 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Commit changed from 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7 to f6272d39e0de839ef4e28e28d3d8fd207fe6cbae
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
f6272d3  trac #19317: A (1288,792,476,504)strongly regular graph

comment:3 followup: ↓ 4 Changed 6 years ago by
Do you really need the whole Golay code for this? This graph has vertextransitive automorphism group, Mathieu(24), acting on certain 12subsets. Or you can use AtlasGroup
:
sage: g=libgap.AtlasGroup("M24",libgap.NrMovedPoints,1288) sage: G=Graph() sage: G.add_edges(libgap.Orbit(g,[1,2],libgap.OnSets)) sage: G.is_strongly_regular(parameters=True) (1288, 495, 206, 180)
comment:4 in reply to: ↑ 3 ; followup: ↓ 5 Changed 6 years ago by
Do you really need the whole Golay code for this?
You can add a commit if you prefer. I admit that I prefer it the way it is written, as you can explain the construction a bit better than just "some orbit will work". I don't mind either way.
Nathann
comment:5 in reply to: ↑ 4 Changed 6 years ago by
Replying to ncohen:
Do you really need the whole Golay code for this?
You can add a commit if you prefer. I admit that I prefer it the way it is written, as you can explain the construction a bit better than just "some orbit will work". I don't mind either way.
"some orbit will work", as it is a rank 3 permutation representation of M_{24}
.
You can refer to Conway et al. Atlas of Finite Group. It was certainly wellknown long before the reference you provide.
It's also mindboggling the way it is given, that it works. In fact, it's a property of the extended Golay code (i.e. sage.coding.code_constructions.ExtendedBinaryGolayCode()
), that it only has words of length 0,8,12,16, and 24), so you can relate the graph vertices to certain 1288 partitions of the 24set into 12+12, with M_{24}
acting in the natural way (onSetsSets
?).
You work with the shorter (length 23) code, on which M_{24}
acts as a linear group, so this is less transparent.
comment:6 Changed 6 years ago by
Sorry Dima, I already wrote this code once and it works, now if you prefer a different set of 4 lines of code and a different documentation please add a commit, I will not mind.
Nathann
comment:7 Changed 6 years ago by
Anyway, if you take the symmetric differences of size 8, not 12, you will get the complementary graph  less edges, quicker to build, no?
comment:8 followup: ↓ 9 Changed 6 years ago by
and how about this doctest?
A realizable set of parameters that Sage cannot realize (help us!):: sage: graphs.strongly_regular_graph(1288, 495, 206, existence=True) True sage: graphs.strongly_regular_graph(1288, 495, 206) Traceback (most recent call last): ... RuntimeError: Andries Brouwer's database claims that such a (1288,495,206,180)strongly regular graph exists, but Sage does not know how to build it. ...
shouldn't you change it? (feel free to take the example on 378 vertices from Muzychuk's paper, this is not something we will have very soon...)
comment:9 in reply to: ↑ 8 Changed 6 years ago by
and how about this doctest?
Well, as we hope to fill all those cases in a couple of months, thought that we would be better without it :/
shouldn't you change it? (feel free to take the example on 378 vertices from Muzychuk's paper, this is not something we will have very soon...)
Why? We need all of them!
Nathann
comment:10 Changed 6 years ago by
Dimaaaaa ?? This one is easy :P
comment:11 followup: ↓ 12 Changed 6 years ago by
how about my comment 7?
comment:12 in reply to: ↑ 11 Changed 6 years ago by
how about my comment 7?
It saves around .3s over a 1.7 seconds computation. If that interests you, you are welcome to change all the figures in this function, change its name and the doc to get it.
Nathann
comment:14 Changed 6 years ago by
 Milestone changed from sage6.9 to sage6.10
Reviewer name. I think that I have said this comment before. :=)
.
comment:15 Changed 6 years ago by
 Status changed from positive_review to needs_work
comment:16 Changed 6 years ago by
 Reviewers set to Dima Pasechnik
 Status changed from needs_work to positive_review
oh well, this is not too far from "forgetting to zip up" stage :)
comment:17 Changed 6 years ago by
 Branch changed from u/ncohen/19317 to f6272d39e0de839ef4e28e28d3d8fd207fe6cbae
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
trac #19317: A (1288,792,476,504)strongly regular graph