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: sage-6.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:

Status badges

Description

As the title says.

Change History (17)

comment:1 Changed 7 years ago by Nathann Cohen

Branch: u/ncohen/19317
Commit: 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7
Status: newneeds_review

New commits:

6e4a342trac #19317: A (1288,792,476,504)-strongly regular graph

comment:2 Changed 7 years ago by git

Commit: 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7f6272d39e0de839ef4e28e28d3d8fd207fe6cbae

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

f6272d3trac #19317: A (1288,792,476,504)-strongly regular graph

comment:3 Changed 7 years ago by Dima Pasechnik

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 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 ; Changed 7 years ago by Nathann Cohen

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 7 years ago by Dima Pasechnik

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 well-known long before the reference you provide.

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. 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 24-set 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 Nathann Cohen

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 Dima Pasechnik

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 Changed 7 years ago by Dima Pasechnik

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 7 years ago by Nathann Cohen

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 7 years ago by Nathann Cohen

Dimaaaaa ?? This one is easy :-P

comment:11 Changed 7 years ago by Dima Pasechnik

how about my comment 7?

comment:12 in reply to:  11 Changed 7 years ago by Nathann Cohen

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:13 Changed 7 years ago by Dima Pasechnik

Status: needs_reviewpositive_review

OK, OK...

comment:14 Changed 7 years ago by Jori Mäntysalo

Milestone: sage-6.9sage-6.10

Reviewer name. I think that I have said this comment before. :=).

comment:15 Changed 7 years ago by Volker Braun

Status: positive_reviewneeds_work

comment:16 Changed 7 years ago by Dima Pasechnik

Reviewers: Dima Pasechnik
Status: needs_workpositive_review

oh well, this is not too far from "forgetting to zip up" stage :-)

comment:17 Changed 7 years ago by Volker Braun

Branch: u/ncohen/19317f6272d39e0de839ef4e28e28d3d8fd207fe6cbae
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.