M22 graph
≈ 2 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The M 22 graph, also called the Mesner graph or Witt graph, is the unique strongly regular graph with parameters (77, 16, 0, 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. 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. Its graph spectrum is (−6) 21 2 55 16 1 , and its automorphism group is the Mathieu group M22.
The M 22 graph, also called the Mesner graph or Witt graph, is the unique strongly regular graph with parameters (77, 16, 0, 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. 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. Its graph spectrum is (−6) 21 2 55 16 1 , and its automorphism group is the Mathieu group M22.
See also
Cameron graph Higman–Sims graph Gewirtz graph
References
External links
M 22 graph at MathWorld
Text derived from https://en.wikipedia.org/w/index.php?oldid=1335203042 under CC BY-SA 4.0; modifications have been made.