M22 graph

{{Short description|Strongly regular graph}}

{{DISPLAYTITLE:M₂₂ graph}}

{{infobox graph

| name = M₂₂ graph, Mesner graph[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)"][http://euler.doa.fmph.uniba.sk/iwont2014/abstracts/kovacikova.pdf Slide 5 list of triangle-free SRGs says "Mesner graph"][http://my.svgalib.org/phdfiles/thesis.pdf Section 3.2.6 Mesner graph]

| image = M22 graph.svg

| image_caption =

| namesake = Mathieu group M₂₂, Dale M. Mesner

| vertices = 77

| edges = 616

| radius =

| diameter =

| girth =

| automorphisms =

| chromatic_number =

| chromatic_index =

| genus =

| book thickness =

| queue number =

| spectrum =

| properties =

| notation =

}}

The M₂₂ graph, also called the Mesner graph or Witt graph,{{citation

| last1 = Godsil | first1 = Christopher | author1-link = Chris Godsil

| last2 = Meagher | first2 = Karen

| contribution = Section 5.4: The Witt graph

| isbn = 9781107128446

| pages = 94–96

| publisher = Cambridge University Press

| series = Cambridge Studies in Advanced Mathematics

| title = Erdős–Ko–Rado Theorems: Algebraic Approaches

| url = https://www.cambridge.org/ht/academic/subjects/mathematics/discrete-mathematics-information-theory-and-coding/erdoskorado-theorems-algebraic-approaches

| year = 2015}} is the unique strongly regular graph 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 (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.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)²¹2⁵⁵16¹, and its automorphism group is the Mathieu group M22.