In mathematical
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the Higman–Sims graph is a 22-
regular undirected graph
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...
with 100 vertices and 1100 edges. It 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 commo ...
srg(100,22,0,6), where no neighboring pair of vertices share a common neighbor and each non-neighboring pair of vertices share six common neighbors. It was first constructed by and rediscovered in 1968 by Donald G. Higman and Charles C. Sims as a way to define the
Higman–Sims group
In the area of modern algebra known as group theory, the Higman–Sims group HS is a sporadic simple group of order
: 29⋅32⋅53⋅7⋅11 = 44352000
: ≈ 4.
The Schur multiplier has order 2, the outer automorphis ...
, a subgroup of
index
Index (or its plural form indices) may refer to:
Arts, entertainment, and media Fictional entities
* Index (''A Certain Magical Index''), a character in the light novel series ''A Certain Magical Index''
* The Index, an item on a Halo megastru ...
two in the group of automorphisms of the Higman–Sims graph.
Construction
From M22 graph
Take the
M22 graph
The M22 graph, also called the Mesner graph or Witt graph is the unique strongly regular graph with parameters (77, 16, 0, 4). Brouwer, Andries E. “M22 Graph.” Technische Universiteit Eindhoven, http://www.win.tue.nl/~aeb/graphs/M22.html. Ac ...
, a
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 commo ...
srg(77,16,0,4) and augment it with 22 new vertices corresponding to the points of S(3,6,22), each block being connected to its points, and one additional vertex ''C'' connected to the 22 points.
From Hoffman–Singleton graph
There are 100
independent sets of size 15 in the
Hoffman–Singleton graph
In the mathematical field of graph theory, the Hoffman–Singleton graph is a 7- regular undirected graph with 50 vertices and 175 edges. It is the unique strongly regular graph with parameters (50,7,0,1). It was constructed by Alan Hoffman an ...
. Create a new graph with 100 corresponding vertices, and connect vertices whose corresponding independent sets have exactly 0 or 8 elements in common.
The resulting Higman–Sims graph can be partitioned into two copies of the
Hoffman–Singleton graph in 352 ways.
From a cube
Take a cube with vertices labeled 000, 001, 010, ..., 111. Take all 70 possible 4-sets of vertices, and retain only the ones whose
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
evaluates to 000; there are 14 such 4-sets, corresponding to the 6 faces + 6 diagonal-rectangles + 2 parity tetrahedra. This is a 3-(8,4,1)
block design
In combinatorial mathematics, a block design is an incidence structure consisting of a set together with a family of subsets known as ''blocks'', chosen such that frequency of the elements satisfies certain conditions making the collection of bl ...
on 8 points, with 14 blocks of block size 4, each point appearing in 7 blocks, each pair of points appearing 3 times, each triplet of points occurring exactly once. Permute the original 8 vertices any of 8! = 40320 ways, and discard duplicates. There are then 30 different ways to relabel the vertices (i.e., 30 different designs that are all isomorphic to each other by permutation of the points). This is because there are 1344
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
s, and 40320/1344 = 30.
Create a vertex for each of the 30 designs, and for each row of every design (there are 70 such rows in total, each row being a 4-set of 8 and appearing in 6 designs). Connect each design to its 14 rows. Connect disjoint designs to each other (each design is disjoint with 8 others). Connect rows to each other if they have exactly one element in common (there are 4x4 = 16 such neighbors). The resulting graph is the Higman–Sims graph. Rows are connected to 16 other rows and to 6 designs degree 22. Designs are connected to 14 rows and 8 disjoint designs degree 22. Thus all 100 vertices have degree 22 each.
Algebraic properties
The
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 ...
of the Higman–Sims graph is a group of order isomorphic to the
semidirect product
In mathematics, specifically in group theory, the concept of a semidirect product is a generalization of a direct product. There are two closely related concepts of semidirect product:
* an ''inner'' semidirect product is a particular way in w ...
of the
Higman–Sims group
In the area of modern algebra known as group theory, the Higman–Sims group HS is a sporadic simple group of order
: 29⋅32⋅53⋅7⋅11 = 44352000
: ≈ 4.
The Schur multiplier has order 2, the outer automorphis ...
of order with the
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
of order 2. It has automorphisms that take any edge to any other edge, making the Higman–Sims graph an
edge-transitive graph
In the mathematical field of graph theory, an edge-transitive graph is a graph such that, given any two edges and of , there is an automorphism of that maps to .
In other words, a graph is edge-transitive if its automorphism group acts ...
.
The characteristic polynomial of the Higman–Sims graph is (''x'' − 22)(''x'' − 2)
77(''x'' + 8)
22. Therefore, the Higman–Sims graph is an
integral graph In the mathematical field of graph theory, an integral graph is a graph whose adjacency matrix's spectrum consists entirely of integers. In other words, a graph is an integral graph if all of the roots of the characteristic polynomial of its adjace ...
: its
spectrum
A spectrum (plural ''spectra'' or ''spectrums'') is a condition that is not limited to a specific set of values but can vary, without gaps, across a continuum. The word was first used scientifically in optics to describe the rainbow of colors i ...
consists entirely of integers. It is also the only graph with this characteristic polynomial, making it a graph determined by its spectrum.
Inside the Leech lattice
The Higman–Sims graph naturally
occurs inside the
Leech lattice
In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space, which is one of the best models for the kissing number problem. It was discovered by . It may also have been discovered (but not published) by ...
: if ''X'', ''Y'' and ''Z'' are three points in the Leech lattice such that the distances ''XY'', ''XZ'' and ''YZ'' are
respectively, then there are exactly 100 Leech lattice points ''T'' such that all the distances ''XT'', ''YT'' and ''ZT'' are equal to 2, and if we connect two such points ''T'' and ''T''′ when the distance between them is
, the resulting graph is isomorphic to the Higman–Sims graph. Furthermore, the set of all automorphisms of the Leech lattice (that is, Euclidean congruences fixing it) which fix each of ''X'', ''Y'' and ''Z'' is the Higman–Sims group (if we allow exchanging ''X'' and ''Y'', the order 2 extension of all graph automorphisms is obtained). This shows that the Higman–Sims group occurs inside the
Conway group
In the area of modern algebra known as group theory, the Conway groups are the three sporadic simple groups Co1, Co2 and Co3 along with the related finite group Co0 introduced by .
The largest of the Conway groups, Co0, is the group of auto ...
s Co
2 (with its order 2 extension) and Co
3, and consequently also Co
1.
[ chapter 10 (John H. Conway, "Three Lectures on Exceptional Groups"), §3.5 ("The Higman–Sims and McLaughlin groups"), pp. 292–293.]
References
*
{{DEFAULTSORT:Higman-Sims graph
Group theory
Individual graphs
Regular graphs
Strongly regular graphs