M22 graph explained

M22 graph, Mesner graph^[1] ^[2] ^[3]
Namesake:	Mathieu group M22, Dale M. Mesner
Vertices:	77
Edges:	616

The M₂₂ graph, also called the Mesner graph^{[1] [2] [3]} or Witt graph is the unique strongly regular graph with parameters (77, 16, 0, 4).^[4] It is constructed from the Steiner system (3, 6, 22) by representing its 77 blocks as vertices and joining two vertices iff they have no terms in common or by deleting a vertex and its neighbors from the Higman–Sims graph.^{[5] [6]}

For any term, the family of blocks that contain that term forms an independent set in this graph, with 21 vertices. In a result analogous to the Erdős–Ko–Rado theorem (which can be formulated in terms of independent sets in Kneser graphs), these are the unique maximum independent sets in this graph.

It is one of seven known triangle-free strongly regular graphs.^[7] Its graph spectrum is (−6)²¹2⁵⁵16¹,^[5] and its automorphism group is the Mathieu group M22.^[4]

See also

• Cameron graph
• Higman–Sims graph
• Gewirtz graph

External links

• M₂₂ graph at MathWorld

Notes and References

1. https://easychair.org/publications/open/BbN2 "Mesner graph with parameters (77,16,0,4). The automorphism group is of order 887040 and is isomorphic to the stabilizer of a point in the automorphism group of NL2(10)"
2. http://euler.doa.fmph.uniba.sk/iwont2014/abstracts/kovacikova.pdf Slide 5 list of triangle-free SRGs says "Mesner graph"
3. http://my.svgalib.org/phdfiles/thesis.pdf Section 3.2.6 Mesner graph
4. [Brouwer, Andries E.]
5. Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.
6. Vis, Timothy. “The Higman–Sims Graph.” University of Colorado Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Accessed 29 May 2018.
7. Weisstein, Eric W. “Strongly Regular Graph.” From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.