Sage: Ticket #19317: A (1288,792,476,504)-strongly regular graph
https://trac.sagemath.org/ticket/19317
<p>
As the title says.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/19317
Trac 1.1.6ncohenWed, 30 Sep 2015 10:14:12 GMTstatus changed; commit, branch set
https://trac.sagemath.org/ticket/19317#comment:1
https://trac.sagemath.org/ticket/19317#comment:1
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>commit</strong>
set to <em>6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7</em>
</li>
<li><strong>branch</strong>
set to <em>u/ncohen/19317</em>
</li>
</ul>
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7"><span class="icon"></span>6e4a342</a></td><td><code>trac #19317: A (1288,792,476,504)-strongly regular graph</code>
</td></tr></table>
TicketgitWed, 30 Sep 2015 10:14:23 GMTcommit changed
https://trac.sagemath.org/ticket/19317#comment:2
https://trac.sagemath.org/ticket/19317#comment:2
<ul>
<li><strong>commit</strong>
changed from <em>6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7</em> to <em>f6272d39e0de839ef4e28e28d3d8fd207fe6cbae</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=f6272d39e0de839ef4e28e28d3d8fd207fe6cbae"><span class="icon"></span>f6272d3</a></td><td><code>trac #19317: A (1288,792,476,504)-strongly regular graph</code>
</td></tr></table>
TicketdimpaseWed, 30 Sep 2015 16:58:23 GMT
https://trac.sagemath.org/ticket/19317#comment:3
https://trac.sagemath.org/ticket/19317#comment:3
<p>
Do you really need the whole Golay code for this? This graph has vertex-transitive automorphism group, Mathieu(24), acting on certain 12-subsets. Or you can use <code>AtlasGroup</code>:
</p>
<pre class="wiki">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)
</pre>
TicketncohenWed, 30 Sep 2015 17:44:21 GMT
https://trac.sagemath.org/ticket/19317#comment:4
https://trac.sagemath.org/ticket/19317#comment:4
<blockquote class="citation">
<p>
Do you really need the whole Golay code for this?
</p>
</blockquote>
<p>
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.
</p>
<p>
Nathann
</p>
TicketdimpaseWed, 30 Sep 2015 18:13:19 GMT
https://trac.sagemath.org/ticket/19317#comment:5
https://trac.sagemath.org/ticket/19317#comment:5
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/19317#comment:4" title="Comment 4">ncohen</a>:
</p>
<blockquote class="citation">
<blockquote class="citation">
<p>
Do you really need the whole Golay code for this?
</p>
</blockquote>
<p>
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.
</p>
</blockquote>
<p>
"some orbit will work", as it is a rank 3 permutation representation of <code>M_{24}</code>.
You can refer to Conway et al. Atlas of Finite Group. It was certainly well-known long before the reference you provide.
</p>
<p>
It's also mind-boggling the way it is given, that it works. In fact, it's a property of the extended Golay code (i.e. <code>sage.coding.code_constructions.ExtendedBinaryGolayCode()</code>), 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 24-set into 12+12, with <code>M_{24}</code> acting in the natural way (<code>onSetsSets</code> ?).
</p>
<p>
You work with the shorter (length 23) code, on which <code>M_{24}</code> acts as a linear group, so this is less transparent.
</p>
TicketncohenWed, 30 Sep 2015 18:15:57 GMT
https://trac.sagemath.org/ticket/19317#comment:6
https://trac.sagemath.org/ticket/19317#comment:6
<p>
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.
</p>
<p>
Nathann
</p>
TicketdimpaseWed, 30 Sep 2015 18:16:36 GMT
https://trac.sagemath.org/ticket/19317#comment:7
https://trac.sagemath.org/ticket/19317#comment:7
<p>
Anyway, if you take the symmetric differences of size 8, not 12, you will get the complementary graph - less edges, quicker to build, no?
</p>
TicketdimpaseWed, 30 Sep 2015 18:24:19 GMT
https://trac.sagemath.org/ticket/19317#comment:8
https://trac.sagemath.org/ticket/19317#comment:8
<p>
and how about this doctest?
</p>
<pre class="wiki"> 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.
...
</pre><p>
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...)
</p>
TicketncohenWed, 30 Sep 2015 18:33:52 GMT
https://trac.sagemath.org/ticket/19317#comment:9
https://trac.sagemath.org/ticket/19317#comment:9
<blockquote class="citation">
<p>
and how about this doctest?
</p>
</blockquote>
<p>
Well, as we hope to fill all those cases in a couple of months, thought that we would be better without it <code>:-/</code>
</p>
<blockquote class="citation">
<p>
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...)
</p>
</blockquote>
<p>
Why? We need all of them!
</p>
<p>
Nathann
</p>
TicketncohenMon, 26 Oct 2015 08:36:29 GMT
https://trac.sagemath.org/ticket/19317#comment:10
https://trac.sagemath.org/ticket/19317#comment:10
<p>
Dimaaaaa ?? This one is easy <code>:-P</code>
</p>
TicketdimpaseMon, 26 Oct 2015 10:03:11 GMT
https://trac.sagemath.org/ticket/19317#comment:11
https://trac.sagemath.org/ticket/19317#comment:11
<p>
how about my comment 7?
</p>
TicketncohenMon, 26 Oct 2015 10:42:02 GMT
https://trac.sagemath.org/ticket/19317#comment:12
https://trac.sagemath.org/ticket/19317#comment:12
<blockquote class="citation">
<p>
how about my comment 7?
</p>
</blockquote>
<p>
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.
</p>
<p>
Nathann
</p>
TicketdimpaseMon, 26 Oct 2015 10:46:29 GMTstatus changed
https://trac.sagemath.org/ticket/19317#comment:13
https://trac.sagemath.org/ticket/19317#comment:13
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
OK, OK...
</p>
TicketjmantysaloMon, 26 Oct 2015 11:13:45 GMTmilestone changed
https://trac.sagemath.org/ticket/19317#comment:14
https://trac.sagemath.org/ticket/19317#comment:14
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.9</em> to <em>sage-6.10</em>
</li>
</ul>
<p>
Reviewer name. I think that I have said this comment before. <code>:=)</code>.
</p>
TicketvbraunMon, 26 Oct 2015 20:08:40 GMTstatus changed
https://trac.sagemath.org/ticket/19317#comment:15
https://trac.sagemath.org/ticket/19317#comment:15
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
TicketdimpaseMon, 26 Oct 2015 21:01:06 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/19317#comment:16
https://trac.sagemath.org/ticket/19317#comment:16
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Dima Pasechnik</em>
</li>
</ul>
<p>
oh well, this is not too far from "forgetting to zip up" stage :-)
</p>
TicketvbraunTue, 27 Oct 2015 22:53:16 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/19317#comment:17
https://trac.sagemath.org/ticket/19317#comment:17
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/ncohen/19317</em> to <em>f6272d39e0de839ef4e28e28d3d8fd207fe6cbae</em>
</li>
</ul>
Ticket