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 ...

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''₆

\square

''K''₂ in such a way that ''u'' and ''v'' belong to different ''K''₆ 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

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 ...

.; ; .

Notes

References

*. As cited by . *. *. As cited by . *. *. *. *.

External links