M22 and Cameron graph constructors

[nathanncohen]

Two other strongly regular graphs !

http://www.win.tue.nl/~aeb/graphs/M22.html
http://www.win.tue.nl/~aeb/graphs/Cameron.html

Nathann

apply

• attachment: trac_14283.patch
• attachment: 14283_extra.patch

Depends on #14271
Depends on #14291

CC: @dimpase

Component: graph theory

Author: Nathann Cohen, Dmitrii Pasechnik

Reviewer: Dmitrii Pasechnik

Merged: sage-5.10.beta2

Issue created by migration from https://trac.sagemath.org/ticket/14283

[dimpase]

comment:2

A much better way is to create these 77 blocks by applying the Mathieu group M_22 to one block, directly.
Replace s= [long long boring list] by

s = MathieuGroup(22)._gap_().Orbit([1,2,3,7,10,20],"OnSets").sage()

This is a bit unfortunate that one needs to write such an ugly call, instead of just MathieuGroup(22).orbit([1,2,3,7,10,20],"OnSets").
IMHO it's worth opening a ticket and fixing this, i.e. adding "OnSets" and other GAP options to the orbit method.

PS. How does one find the block? Well, take the pointwise stabilizer of 3 points, say, 1, 2, 3 in MathieuGroup(22) and compute its orbits on the 22 points the group acts naturally. Such a stabilizer is the stabilizer of two points, 1 and 2, in the projective plane of order 4 induced on 2,3,...,22. There is unique like on 1 and 2 in this plane, so you'll see an orbit of length 3 that you need to add to 1, 2, 3 to get the block (this is the unique block on the 3 points 1, 2, 3).

[dimpase]

comment:3

And with a minimum extra effort one may construct http://www.win.tue.nl/~aeb/graphs/Cameron.html using the same s=[...].

[nathanncohen]

comment:4

T_T

Dimaaaaaaaaaaaaa... Please, give me one book to read so that I will know and understand all these things by myself and not stay helpless in front of your black magic ?.. T_T

Patch updated. Thank you very much !

Nathann

[nathanncohen]

Changed author from Nathann Cohen to Nathann Cohen, Dmitrii Pasechnik

[nathanncohen]

Changed dependencies from 14271 to 14271, 14291

[dimpase]

comment:7

Replying to @nathanncohen:

T_T

Dimaaaaaaaaaaaaa... Please, give me one book to read so that I will know and understand all these things by myself and not stay helpless in front of your black magic ?.. T_T

regarding Mathieu groups and Witt designs, there is e.g. a chapter "Three lectures on exceptional groups" in Conway & Sloan "Sphere Packings, Lattices and Groups". There are many more places where this stuff can be found, though. E.g. here: http://www.win.tue.nl/~aeb/2WF02/Witt.pdf

By the way, there are more distance-transitive graphs which can be constructed from blocks of these designs. See [loc.cit.] and
the book `Distance-Regular Graphs' by Brouwer, Cohen and Neumaier (Springer, 1989).

Patch updated. Thank you very much !

Thanks for adding me in as a coauthor!

a typo:

1108	    Returns the Cameon graph. 

[nathanncohen]

comment:8

Updated ! And thank you for the references !

Nathann

[dimpase]

Changed dependencies from 14271, 14291 to #14271, #14291

[fchapoton]

comment:10

a typo : unique strongly graph

[nathanncohen]

comment:11

Updated !

Nathann

[nathanncohen]

comment:12

Now with an embedding. I recommend using g.show(figsize=40) :-P

Nathann

[fchapoton]

comment:13

The doctests are failing : the Cameron graph does not seem to be correct

[dimpase]

comment:14

Replying to @fchapoton:

The doctests are failing : the Cameron graph does not seem to be correct

that's due to a bug or a feature in #14291 : the action "OnSets" returns unsorted tuples. Attached 1-line patch fixes this; although I think that #14291 must be fixed, too.

[dimpase]

Attachment: 14283_extra.patch.gz

fix for Cameron graph

[jdemeyer]

Reviewer: Dmitrii Pasechnik

[jdemeyer]

Work Issues: documentation

[jdemeyer]

comment:17

dochtml.log:[graphs   ] /mazur/release/merger/sage-5.10.beta1/local/lib/python2.7/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.CameronGraph:6: ERROR: Unknown target name: "http://www.win.tue.nl/~aeb/graphs/cameron.html".
dochtml.log:[graphs   ] /mazur/release/merger/sage-5.10.beta1/local/lib/python2.7/site-packages/sage/graphs/graph_generators.py:docstring of sage.graphs.graph_generators.GraphGenerators.M22Graph:6: ERROR: Unknown target name: "http://www.win.tue.nl/~aeb/graphs/m22.html".

[nathanncohen]

comment:18

Arggggggggg... Sorry :-/

Fixed.

Nathann

[jdemeyer]

comment:19

# long

should be

# long time

[jdemeyer]

Changed work issues from documentation to none

[nathanncohen]

comment:20

Fixed too.

[jdemeyer]

Merged: sage-5.10.beta2

[jdemeyer]

comment:21

Attachment: trac_14283.patch.gz