Simplex Graph¶
Transform an undirected graph into a bipartite median graph whose vertices are all cliques, including the empty clique, with adjacency given by adding or deleting exactly one original vertex.
Core Idea¶
For an undirected graph \(G\), its simplex graph \(\kappa(G)\) has one vertex for every clique of \(G\), including the empty clique and all singletons. Two vertices of \(\kappa(G)\) are adjacent exactly when the corresponding cliques differ by adding or deleting one vertex—equivalently, their symmetric difference has cardinality one. This is a graph construction, not a label for the clique complex itself and not the better-known clique graph whose vertices are often maximal cliques. Bandelt and van de Vel used the construction in connecting graph coloring, median algebras, and embeddings into products of dendrons.
Scope of Application¶
Simplex graphs translate clique structure into metric and median-graph geometry.
- Median graph theory. Producing canonical median graphs with an identifiable central vertex.
- Graph coloring. Relating colorability of the input to tree-product embeddings of the output.
- Clique-complex analysis. Representing face-inclusion cover relations as graph edges.
- Cubical geometry. Turning each input clique into an induced hypercube through its subsets.
- Recognition complexity. Transferring questions between triangle-free graphs and cube-restricted median graphs.
- Named graph families. Recovering hypercubes, gear graphs, and Fibonacci cubes from suitable inputs.
Clarity¶
Define clique to include the empty set and every singleton. Use a separate symbol such as \(\kappa(G)\) for the output graph. State that its vertices are clique subsets of \(V(G)\), and that adjacency requires symmetric difference of exactly one—not at most one, which would also admit equality. Distinguish all cliques from maximal cliques. When identifying an output as a hypercube, specify that the input is complete; when claiming a cube restriction, translate cube dimension back to clique size.
Manages Complexity¶
Clique families are downward closed but can be exponentially large and difficult to view as a single object. The simplex-graph transformation externalizes this family as a graph whose edges record one-element changes. Set symmetric difference becomes path length, inclusion becomes edge orientation, and coordinatewise majority becomes a median operation. Cubes appear automatically from subsets of one clique, allowing clique number to be read as cubical dimension.
Abstract Reasoning¶
- Enumerate or characterize every clique of the undirected input graph, including the empty set. 2. Create one output vertex for each clique and retain the subset as its label. 3. Join two output vertices exactly when their labels differ by one original vertex. 4. Use subset inclusion to orient or rank edges by clique cardinality when useful. 5. Compute paths by deleting to an intersection and adding toward the target clique.
Knowledge Transfer¶
The strict parent is Transformation: a fully specified mapping takes an undirected graph to another graph, changes vertices into cliques, changes adjacency into unit symmetric difference, and preserves selected incidence information in metric form. The transferable pattern is to lift a family of admissible subsets into a state graph connected by atomic edits. The requirement that admissible subsets are cliques, the majority-closure proof, and the resulting median/cubical identities are graph-theoretic accent.
Relationships to Other Abstractions¶
Current abstraction Simplex Graph Domain-specific
Parents (1) — more general patterns this builds on
-
Simplex Graph is a kind of Transformation Prime
Transformation is the strict parent because \(\kappa\) is a rule-governed graph-to-graph mapping that restructures original vertices into clique states while preserving clique inclusion as unit-step metric geometry.
Hierarchy path (1) — routes to 1 parentless root
- Simplex Graph → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Simplex Graph sits in a sparse region of the domain-specific corpus (81st percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (1565 abstractions)
Nearest neighbors
- Clique graph — 0.84
- Clique (Graph Theory) — 0.83
- Pathwidth — 0.83
- Graph Sphericity — 0.81
- Quotient Graph — 0.81
Computed from structural-signature embeddings · 2026-09-08