The M
22 graph, also called the Mesner graph or Witt graph,
is the unique
strongly regular graph
In graph theory, a strongly regular graph (SRG) is a regular graph with vertices and degree such that for some given integers \lambda, \mu \ge 0
* every two adjacent vertices have common neighbours, and
* every two non-adjacent vertices h ...
with parameters (77, 16, 0, 4).
[ Brouwer, Andries E. “M22 Graph.” ]Technische Universiteit Eindhoven
The Eindhoven University of Technology (), Abbreviation, abbr. TU/e, is a public university, public technical university in the Netherlands, situated in Eindhoven. In 2020–21, around 14,000 students were enrolled in its Bachelor of Science, BS ...
, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018. It is constructed from the
Steiner system (3, 6, 22) by representing its 77 blocks as vertices and joining two vertices
iff
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either both ...
they have no terms in common or by deleting a vertex and its neighbors from the
Higman–Sims graph
In mathematical graph theory, the Higman–Sims graph is a 22- regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor an ...
.
[Weisstein, Eric W. “M22 Graph.” MathWorld, http://mathworld.wolfram.com/M22Graph.html. Accessed 29 May 2018.][Vis, Timothy. “The Higman–Sims Graph.” University of Colorado Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Accessed 29 May 2018.]
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.][Weisstein, Eric W. “Strongly Regular Graph.” From Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.] Its graph spectrum is (−6)21255161,automorphism group
In mathematics, the automorphism group of an object ''X'' is the group consisting of automorphisms of ''X'' under composition of morphisms. For example, if ''X'' is a finite-dimensional vector space, then the automorphism group of ''X'' is the g ...
is the Mathieu group M22.
See also
* Cameron graph
*Higman–Sims graph
In mathematical graph theory, the Higman–Sims graph is a 22- regular undirected graph with 100 vertices and 1100 edges. It is the unique strongly regular graph srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor an ...
* Gewirtz graph
References
{{reflist
External links
M22 graph
at MathWorld
''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...
Individual graphs
Strongly regular graphs