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

Priority:  major  Milestone:  sage6.10 
Component:  graph theory  Keywords:  
Cc:  Dima Pasechnik  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 7 years ago by
Branch:  → u/ncohen/19317 

Commit:  → 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7 
Status:  new → needs_review 
comment:2 Changed 7 years ago by
Commit:  6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7 → 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 7 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 followup: 5 Changed 7 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 Changed 7 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 7 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 7 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 7 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 Changed 7 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:12 Changed 7 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 7 years ago by
Milestone:  sage6.9 → sage6.10 

Reviewer name. I think that I have said this comment before. :=)
.
comment:15 Changed 7 years ago by
Status:  positive_review → needs_work 

comment:16 Changed 7 years ago by
Reviewers:  → Dima Pasechnik 

Status:  needs_work → positive_review 
oh well, this is not too far from "forgetting to zip up" stage :)
comment:17 Changed 7 years ago by
Branch:  u/ncohen/19317 → f6272d39e0de839ef4e28e28d3d8fd207fe6cbae 

Resolution:  → fixed 
Status:  positive_review → closed 
New commits:
trac #19317: A (1288,792,476,504)strongly regular graph