Opened 6 years ago

Closed 6 years ago

#14283 closed enhancement (fixed)

M22 and Cameron graph constructors

Reported by: ncohen Owned by: tbd
Priority: major Milestone: sage-5.10
Component: graph theory Keywords:
Cc: dimpase Merged in: sage-5.10.beta2
Authors: Nathann Cohen, Dmitrii Pasechnik Reviewers: Dmitrii Pasechnik
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14271, #14291 Stopgaps:

Attachments (2)

14283_extra.patch (720 bytes) - added by dimpase 6 years ago.
fix for Cameron graph
trac_14283.patch (5.9 KB) - added by ncohen 6 years ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 6 years ago by ncohen

  • Component changed from PLEASE CHANGE to graph theory
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 6 years ago by dimpase

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).

comment:3 Changed 6 years ago by dimpase

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

comment:4 follow-up: Changed 6 years ago by ncohen

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

comment:5 Changed 6 years ago by ncohen

  • Authors changed from Nathann Cohen to Nathann Cohen, Dmitrii Pasechnik
  • Description modified (diff)
  • Summary changed from M22 graph constructor to M22 and Cameron graph constructors

comment:6 Changed 6 years ago by ncohen

  • Dependencies changed from 14271 to 14271, 14291

comment:7 in reply to: ↑ 4 Changed 6 years ago by dimpase

Replying to ncohen:

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. 

comment:8 Changed 6 years ago by ncohen

Updated ! And thank you for the references !

Nathann

comment:9 Changed 6 years ago by dimpase

  • Dependencies changed from 14271, 14291 to #14271, #14291

comment:10 Changed 6 years ago by chapoton

a typo : unique strongly graph

comment:11 Changed 6 years ago by ncohen

Updated !

Nathann

comment:12 Changed 6 years ago by ncohen

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

Nathann

comment:13 follow-up: Changed 6 years ago by chapoton

  • Status changed from needs_review to needs_work

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

comment:14 in reply to: ↑ 13 Changed 6 years ago by dimpase

Replying to chapoton:

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.

Changed 6 years ago by dimpase

fix for Cameron graph

comment:15 Changed 6 years ago by dimpase

  • Description modified (diff)
  • Status changed from needs_work to positive_review

comment:16 Changed 6 years ago by jdemeyer

  • Reviewers set to Dmitrii Pasechnik

comment:17 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to documentation
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".

comment:18 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Arggggggggg... Sorry :-/

Fixed.

Nathann

comment:19 Changed 6 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues documentation deleted
# long

should be

# long time

comment:20 Changed 6 years ago by ncohen

  • Status changed from needs_work to positive_review

Fixed too.

Changed 6 years ago by ncohen

comment:21 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.10.beta2
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.