Opened 3 years ago

Closed 3 years ago

#19317 closed enhancement (fixed)

A (1288,792,476,504)-strongly regular graph

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.10
Component: graph theory Keywords:
Cc: dimpase Merged in:
Authors: Nathann Cohen Reviewers: Dima Pasechnik
Report Upstream: N/A Work issues:
Branch: f6272d3 (Commits) Commit: f6272d39e0de839ef4e28e28d3d8fd207fe6cbae
Dependencies: Stopgaps:

Description

As the title says.

Change History (17)

comment:1 Changed 3 years ago by ncohen

  • Branch set to u/ncohen/19317
  • Commit set to 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7
  • Status changed from new to needs_review

New commits:

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

comment:2 Changed 3 years ago by git

  • Commit changed from 6e4a3423ad237aa8cb2c46bddfbe08ef3641c9d7 to f6272d39e0de839ef4e28e28d3d8fd207fe6cbae

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 follow-up: Changed 3 years ago by dimpase

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 ; follow-up: Changed 3 years ago by 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.

Nathann

comment:5 in reply to: ↑ 4 Changed 3 years ago by dimpase

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 3 years ago by ncohen

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 3 years ago by dimpase

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 follow-up: Changed 3 years ago by dimpase

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 3 years ago by ncohen

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 3 years ago by ncohen

Dimaaaaa ?? This one is easy :-P

comment:11 follow-up: Changed 3 years ago by dimpase

how about my comment 7?

comment:12 in reply to: ↑ 11 Changed 3 years ago by ncohen

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 3 years ago by dimpase

  • Status changed from needs_review to positive_review

OK, OK...

comment:14 Changed 3 years ago by jmantysalo

  • Milestone changed from sage-6.9 to sage-6.10

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

comment:15 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_work

comment:16 Changed 3 years ago by dimpase

  • 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 3 years ago by vbraun

  • Branch changed from u/ncohen/19317 to f6272d39e0de839ef4e28e28d3d8fd207fe6cbae
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.