Embedding the n-cube in lower dimensions
From MaRDI portal
The sphericity of a graph G, sph(G), is the smallest integer m such that G is embeddable into the Euclidean space \(E^ m\) in a way that adjacent vertices have distance at most 1 while any two non-adjacent vertices are at distance more than 1. It is proved that for the n-dimensional cube \(Q_ n\) it holds \[ (1+o(1))n/\log_ 2n<sph(Q_ n)<(2\quad \log_ 23+o(1))n/\log_ 2n. \]
Recommendations
Cites work
Cited in
(14)- Contact patterns of equal nonoverlapping spheres
- On the sphericity of the graphs of semiregular polyhedra
- Sphericity exceeds cubicity for almost all complete bipartite graphs
- Embedding of trees in Euclidean spaces
- The Johnson-Lindenstrauss lemma and the sphericity of some graphs
- Geometrical embeddings of graphs
- Sphericity, cubicity, and edge clique covers of graphs
- Minimal embedding of hypercubic graphs on surface
- scientific article; zbMATH DE number 1023179 (Why is no real title available?)
- Classification of regular embeddings of \(n\)-dimensional cubes
- The coordinate representation of a graph and \(n\)-universal graph of radius 1
- On the sphericity and cubicity of graphs
- On the sphericity for the join of many graphs
- Dispersed points and geometric embedding of complete bipartite graphs
This page was built for publication: Embedding the n-cube in lower dimensions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q581416)
