In the
mathematical
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
field of
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, the Schläfli graph, named after
Ludwig Schläfli, is a 16-
regular undirected graph
In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
with 27 vertices and 216 edges. It is a
strongly regular graph with parameters srg(27, 16, 10, 8).
Construction

The
intersection graph of the 27 lines on a
cubic surface
In mathematics, a cubic surface is a surface in 3-dimensional space defined by one polynomial equation of degree 3. Cubic surfaces are fundamental examples in algebraic geometry. The theory is simplified by working in projective space rather than ...
is a
locally linear graph that is the
complement of the Schläfli graph. That is, two vertices are adjacent in the Schläfli graph if and only if the corresponding pair of lines are
skew.
[.]
The Schläfli graph may also be constructed from the system of eight-dimensional vectors
:(1, 0, 0, 0, 0, 0, 1, 0),
:(1, 0, 0, 0, 0, 0, 0, 1), and
:(−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),
and the 24 other vectors obtained by permuting the first six coordinates of these three vectors.
These 27 vectors correspond to the vertices of the Schläfli graph; two vertices are adjacent if and only if the corresponding two vectors have 1 as their
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, ofte ...
.
[.]
Alternately, this graph can be seen as the complement of the collinearity graph of the
generalized quadrangle
In geometry, a generalized quadrangle is an incidence structure whose main feature is the lack of any triangles yet containing many quadrangles. A generalized quadrangle is by definition a polar space of rank two. They are the with ''n'' = 4 a ...
GQ(2, 4).
Subgraphs and neighborhoods
The
neighborhood
A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...
of any vertex in the Schläfli graph forms a 16-vertex subgraph in which each vertex has 10 neighbors (the numbers 16 and 10 coming from the parameters of the Schläfli graph as a strongly regular graph). These subgraphs are all
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
to the
complement graph
In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
of the
Clebsch graph
In the mathematics, mathematical field of graph theory, the Clebsch graph is either of two complement (graph theory), complementary graphs on 16 vertices, a 5-regular graph with 40 edges and a 10-regular graph with 80 edges. The 80-edge graph is ...
.
Since the Clebsch graph is
triangle-free, the Schläfli graph is
claw-free. It plays an important role in the structure theory for claw-free graphs by .
Any two skew lines of these 27 belong to a unique
Schläfli double six configuration
Configuration or configurations may refer to:
Computing
* Computer configuration or system configuration
* Configuration file, a software file used to configure the initial settings for a computer program
* Configurator, also known as choice board ...
, a set of 12 lines whose intersection graph is a
crown graph in which the two lines have disjoint neighborhoods. Correspondingly, in the Schläfli graph, each edge ''uv'' belongs uniquely to a subgraph in the form of a
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is
A\times B = \.
A table c ...
of
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s ''K''
6 ''K''
2 in such a way that ''u'' and ''v'' belong to different ''K''
6 subgraphs of the product. The Schläfli graph has a total of 36 subgraphs of this form, one of which consists of the zero-one vectors in the eight-dimensional representation described above.
Ultrahomogeneity
A graph is defined to be
''k''-ultrahomogeneous if every
isomorphism
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
between two of its
induced subgraph
In graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges, from the original graph, connecting pairs of vertices in that subset.
Definition
Formally, let G=(V,E) ...
s of at most ''k'' vertices can be extended to an
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 automorphism ...
of the whole graph. If a graph is 5-ultrahomogeneous, it is ultrahomogeneous for every ''k''; the only finite
connected graphs of this type are
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
s,
Turán graphs, 3 × 3
rook's graphs, and the 5-
cycle. The infinite
Rado graph
In the mathematics, mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a Countable set, countably infinite graph that can be constructed (with probability one) by choosing independently at random for eac ...
is countably ultrahomogeneous. There are only two connected graphs that are 4-ultrahomogeneous but not 5-ultrahomogeneous: the Schläfli graph and its complement. The proof relies on the
classification of finite simple groups
In mathematics, the classification of finite simple groups (popularly called the enormous theorem) is a result of group theory stating that every List of finite simple groups, finite simple group is either cyclic group, cyclic, or alternating gro ...
.
[; ; .]
See also
*
Gosset graph - contains the Schläfli graph as an induced subgraph of the neighborhood of any vertex.
Notes
References
*. As cited by .
*.
*. As cited by .
*.
*.
*.
*.
External links
*
Andries E. Brouwer page.
{{DEFAULTSORT:Schlafli graph
Individual graphs
Regular graphs
Strongly regular graphs