The M₂₂ graph, also called the Mesner graph or Witt graph is the unique

strongly regular graph In graph theory, a strongly regular graph (SRG) is defined as follows. Let be a regular graph with vertices and degree . is said to be strongly regular if there are also integers and such that: * Every two adjacent vertices have comm ...

with parameters (77, 16, 0, 4). Brouwer, Andries E. “M₂₂ Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Accessed 29 May 2018. It is constructed from the

Steiner system 250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line. In combinatorial mathematics, a Steiner system (named after Jakob Steiner) ...

(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 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 and ...

.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 graph In graph theory, the Kneser graph (alternatively ) is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs a ...

s), these are the unique

maximum independent set In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no edge connecting the tw ...

s 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)²¹2⁵⁵16¹, and its

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.

References

{{reflist

External links

M₂₂ 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 Di ...

Individual graphs Strongly regular graphs

See also

References

External links