stringtranslate.com

Gráfica M22

El grafo M 22 , también llamado grafo de Mesner [1] [2] [3] o grafo de Witt [4] es el único grafo fuertemente regular con parámetros (77, 16, 0, 4). [5] Se construye a partir del sistema de Steiner (3, 6, 22) representando sus 77 bloques como vértices y uniendo dos vértices si no tienen términos en común o eliminando un vértice y sus vecinos del grafo de Higman-Sims . [6] [7]

Para cualquier término, la familia de bloques que contiene ese término forma un conjunto independiente en este grafo, con 21 vértices. En un resultado análogo al teorema de Erdős–Ko–Rado (que puede formularse en términos de conjuntos independientes en grafos de Kneser ), estos son los únicos conjuntos independientes máximos en este grafo. [4]

Es uno de los siete grafos fuertemente regulares libres de triángulos conocidos . [8] Su espectro gráfico es (−6) 21 2 55 16 1 , [6] y su grupo de automorfismos es el grupo de Mathieu M22 . [5]

Véase también

Referencias

  1. ^ ab "Gráfico de Mesner con parámetros (77,16,0,4). El grupo de automorfismos es de orden 887040 y es isomorfo al estabilizador de un punto en el grupo de automorfismos de NL2(10)"
  2. ^ ab Diapositiva 5 La lista de SRG sin triángulos dice "gráfico de Mesner"
  3. ^ ab Sección 3.2.6 Gráfico de Mesner
  4. ^ ab Godsil, Christopher ; Meagher, Karen (2015), "Sección 5.4: El gráfico de Witt", Teoremas de Erdős–Ko–Rado: enfoques algebraicos, Cambridge Studies in Advanced Mathematics, Cambridge University Press, págs. 94–96, ISBN 9781107128446
  5. ^ ab Brouwer, Andries E. "Gráfico M 22 ". Technische Universiteit Eindhoven , http://www.win.tue.nl/~aeb/graphs/M22.html. Consultado el 29 de mayo de 2018.
  6. ^ de Weisstein, Eric W. “M22 Graph”. MathWorld, http://mathworld.wolfram.com/M22Graph.html. Consultado el 29 de mayo de 2018.
  7. ^ Vis, Timothy. “El gráfico de Higman–Sims”. Universidad de Colorado en Denver, http://math.ucdenver.edu/~wcherowi/courses/m6023/tim.pdf. Consultado el 29 de mayo de 2018.
  8. ^ Weisstein, Eric W. “Gráfico fuertemente regular”. De Wolfram MathWorld, mathworld.wolfram.com/StronglyRegularGraph.html.

Enlaces externos