Higman–Sims graph

Higman–Sims graph

infobox graph
name = Higman–Sims graph


image_caption = Drawing based on Paul R. Hafner's construction.
namesake = Donald G. Higman Charles C. Sims
vertices = 100
edges =
chromatic_number =
chromatic_index =
properties = Strongly regular


The separated parts of Hafner's construction.

In mathematics, the Higman–Sims graph is the unique strongly regular graph with 100 vertices and valency 22, where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was constructed by Donald G. Higman and Charles C. Sims as a way to define the Higman–Sims group, and that group is a subgroup of index two in the group of automorphisms of the Higman–Sims graph.

Construction begins with the M22 graph, whose 77 vertices are the blocks of the S(3,6,22) Steiner system W22. Adjacent vertices are defined to be disjoint blocks. This graph is strongly regular; any vertex has 16 neighbors, any 2 adjacent vertices have no common neighbors, and any 2 non-adjacent vertices have 4 common neighbors. This graph has M22:2 as its automorphism group, M22 being a Mathieu group.

The Higman–Sims graph is then formed by appending the 22 points of W22 and a 100th vertex C. The neighbors of C are defined to be those 22 points. A point adjacent to a block is defined to be one that is included.

A Higman–Sims graph can be partitioned into 2 copies of the Hoffman-Singleton graph and there are 352 ways to do this.

References

*citation
last1 = Higman | first1 = Donald G. | authorlink = Donald G. Higman
last2 = Sims | first2 = Charles C.
title = A simple group of order 44,352,000
journal = Mathematische Zeitschrift
volume = 105 | issue = 2 | year = 1968 | pages = 110–113
doi = 10.1007/BF01110435.

*citation
last1 = Hafner | first1 = P. R.
title = [http://www.combinatorics.org/Volume_11/PDF/v11i1r77.pdf On the Graphs of Hoffman-Singleton and Higman-Sims]
journal = [http://www.combinatorics.org The Electronic Journal of Combinatorics]
volume = 11 | issue = 1 | year = 2004 | pages = R77(1-32) .

External links

* cite web
url = http://www.win.tue.nl/~aeb/drg/graphs/Higman-Sims.html
title = Higman-Sims graph
author = Brouwer, Andries E.

*


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Higman–Sims group — In the mathematical field of group theory, the Higman–Sims group HS (named after Donald G. Higman and Charles C. Sims) is a finite group of order : 29 · 32 · 53 · 7 · 11: = 44352000.: ≈ 4 · 107.It is a simple group , meaning it does not have any… …   Wikipedia

  • Graphe de Higman-Sims — Représentation du graphe de Higman Sims Nombre de sommets 100 Nombre d arêtes 1100 Distribution des degrés 22 régulier Rayon …   Wikipédia en Français

  • Donald G. Higman — Donald Gordon Higman (* 20. September 1928 in Vancouver; † 13. Februar 2006) war ein US amerikanischer Mathematiker, der sich mit endlichen Gruppen, Darstellungstheorie von Gruppen, Kombinatorik und geometrischen Anwendungen von Gruppen… …   Deutsch Wikipedia

  • Charles Sims (mathematician) — Charles C. Sims, 2006 (photo by Renate Schmid) Charles Coffin Sims (born 1938) is an American mathematician best known for his work in group theory. Together with Donald G. Higman he discovered the Higman–Sims group, one of the sporadic groups.… …   Wikipedia

  • Strongly regular graph — Let G = (V,E) be a regular graph with v vertices and degree k . G is said to be strongly regular if there are also integers λ and μ such that:* Every two adjacent vertices have λ common neighbours.* Every two non adjacent vertices have μ common… …   Wikipedia

  • List of finite simple groups — In mathematics, the classification of finite simple groups states thatevery finite simple group is cyclic, or alternating, or in one of 16 families of groups of Lie type (including the Tits group, which strictly speaking is not of Lie type),or… …   Wikipedia

  • List of mathematics articles (H) — NOTOC H H cobordism H derivative H index H infinity methods in control theory H relation H space H theorem H tree Haag s theorem Haagerup property Haaland equation Haar measure Haar wavelet Haboush s theorem Hackenbush Hadamard code Hadamard… …   Wikipedia

  • List of mathematical examples — This page will attempt to list examples in mathematics. To qualify for inclusion, an article should be about a mathematical object with a fair amount of concreteness. Usually a definition of an abstract concept, a theorem, or a proof would not be …   Wikipedia

  • Symmetric group — Not to be confused with Symmetry group. A Cayley graph of the symmetric group S4 …   Wikipedia

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”