Embedding the n-cube in lower dimensions (Q581416): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
| Property / author | |||
| Property / author: Peter Frankl / rank | |||
Normal rank | |||
| Property / author | |||
| Property / author: Hiroshi Maehara / rank | |||
Normal rank | |||
| Property / review text | |||
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. \] | |||
| Property / review text: 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. \] / rank | |||
Normal rank | |||
| Property / reviewed by | |||
| Property / reviewed by: Jozef Širáň / rank | |||
Normal rank | |||
| Property / Mathematics Subject Classification ID | |||
| Property / Mathematics Subject Classification ID: 05C99 / rank | |||
Normal rank | |||
| Property / zbMATH DE Number | |||
| Property / zbMATH DE Number: 4019105 / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
sphericity of a graph | |||
| Property / zbMATH Keywords: sphericity of a graph / rank | |||
Normal rank | |||
| Property / zbMATH Keywords | |||
n-dimensional cube | |||
| Property / zbMATH Keywords: n-dimensional cube / rank | |||
Normal rank | |||
Revision as of 18:53, 1 July 2023
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Embedding the n-cube in lower dimensions |
scientific article |
Statements
Embedding the n-cube in lower dimensions (English)
0 references
1986
0 references
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. \]
0 references
sphericity of a graph
0 references
n-dimensional cube
0 references
