In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

field of

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

, the Schläfli graph, named after

Ludwig Schläfli Ludwig Schläfli (15 January 1814 – 20 March 1895) was a Swiss mathematician, specialising in geometry and complex analysis (at the time called function theory) who was one of the key figures in developing the notion of higher-dimensional space ...

, is a 16- 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 '' ve ...

with 27 vertices and 216 edges. It is 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 comm ...

with parameters srg(27, 16, 10, 8).

Construction

The

intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...

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

is a

locally linear graph In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be ...

that is the

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...

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

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

GQ(2, 4).

Subgraphs and neighborhoods

The neighborhood 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 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 mathematical field of graph theory, the Clebsch graph is either of two 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 the dimension-5 halved cube graph; it ...

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

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 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 them. The word i ...

between two of its

induced subgraph In the mathematical field of 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. Defini ...

s of at most ''k'' vertices can be extended to an automorphism of the whole graph. If a graph is 5-ultrahomogeneous, it is ultrahomogeneous for every ''k''; the only finite

connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...

graphs of this type are

Turán graph The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to di ...

s, 3 × 3

rook's graph In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on ...

s, and the 5- cycle. The infinite

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...

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 the finite simple groups is a result of group theory stating that every finite simple group is either cyclic, or alternating, or it belongs to a broad infinite class called the groups of Lie type, or else i ...

.; ; .

Notes

References

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

External links