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

, a branch of

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

, the simplex graph of an

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

is itself a graph, with one

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics *Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines, ...

for each

clique A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

(a set of mutually adjacent vertices) in . Two nodes of are linked by an edge whenever the corresponding two cliques differ in the presence or absence of a single vertex. The empty set is included as one of the cliques of that are used to form the clique graph, as is every set of one vertex and every set of two adjacent vertices. Therefore, the simplex graph contains within it a

subdivision Subdivision may refer to: Arts and entertainment * Subdivision (metre), in music * ''Subdivision'' (film), 2009 * "Subdivision", an episode of ''Prison Break'' (season 2) * ''Subdivisions'' (EP), by Sinch, 2005 * "Subdivisions" (song), by Rus ...

of itself. The simplex graph of a

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

is a

hypercube graph In graph theory, the hypercube graph is the graph formed from the vertices and edges of an -dimensional hypercube. For instance, the cube graph is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. has vertices, ...

, and the simplex graph of a

cycle graph In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...

of length four or more is a

gear graph This partial list of graphs contains definitions of graphs and graph families which are known by particular names, but do not have a Wikipedia article of their own. For collected definitions of graph theory terms that do not refer to individual g ...

. The simplex graph of 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 a ...

of a

path graph In the mathematical field of graph theory, a path graph or linear graph is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...

is a

Fibonacci cube In the mathematical field of graph theory, the Fibonacci cubes or Fibonacci networks are a family of undirected graphs with rich recursive properties derived from its origin in number theory. Mathematically they are similar to the hypercube graphs ...

. The complete subgraphs of can be given the structure of a

median algebra In mathematics, a median algebra is a set with a ternary operation \langle x,y,z \rangle satisfying a set of axioms which generalise the notions of medians of triples of real numbers and of the Boolean majority function. The axioms are # \lang ...

: the median of three cliques , , and is formed by the vertices that belong to a

majority A majority, also called a simple majority or absolute majority to distinguish it from #Related terms, related terms, is more than half of the total.Dictionary definitions of ''majority'' aMerriam-Webster median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...

corresponding to this median algebra structure. When is the

of a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

, the cliques of can be given a stronger structure as a

distributive lattice In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...

, and in this case the simplex graph is the graph of the lattice. As is true for median graphs more generally, every simplex graph is itself bipartite. The simplex graph has one vertex for every simplex in the

clique complex Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques (complete subgraphs) of an undir ...

of , and two vertices are linked by an edge when one of the two corresponding simplexes is a facet of the other. Thus, the objects (vertices in the simplex graph, simplexes in ) and relations between objects (edges in the simplex graph, inclusion relations between simplexes in ) are in one-to-one correspondence between and . Simplex graphs were introduced by , credit the introduction of simplex graphs to a later paper, also by Bandelt and van de Vel, but this appears to be a mistake. who observed that a simplex graph has no cubes if and only if the underlying graph is triangle-free, and showed that the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the underlying graph equals the minimum number such that the simplex graph can be isometrically embedded into a

Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\ti ...

of trees. As a consequence of the existence of triangle-free graphs with high chromatic number, they showed that there exist two-dimensional topological

s that cannot be embedded into products of finitely many

real tree In mathematics, real trees (also called \mathbb R-trees) are a class of metric spaces generalising simplicial trees. They arise naturally in many mathematical contexts, in particular geometric group theory and probability theory. They are also the s ...

s. also use simplex graphs as part of their proof that testing whether a graph is triangle-free or whether it is a median graph may be performed equally quickly.

Notes

References

*. *. *. *. *{{citation , last = Propp , first = James , arxiv = math.CO/9801066 , issue = 2 , journal = Electronic Journal of Combinatorics , page = R15 , title = Generating random elements of finite distributive lattices , volume = 4 , year = 1997. Graph operations Graph families Bipartite graphs