How few edges preserve a hypercube’s diameter?
- Kind
- Lower bounds with finite certificates
- Status
- General bound and finite certificates checked in Lean; unrefereed
- Prior work
- Builds on the edge-deletion bounds of Bouabdallah, Delorme and Djelloul and the construction of Charton and coauthors
On this page
The statement
The -cube has the strings of bits as vertices, joined when they differ in one bit; its diameter is . Let be the fewest edges of a spanning subgraph of that still has diameter (Graham's hypercube problem).
Theorem 1. For every , every spanning subgraph of with diameter has at least
edges.
Theorem 2. No spanning subgraph of with diameter 5 has 38 edges. With Theorem 1, . A construction with 40 edges is known, so is 39 or 40.
Stronger bounds. Counting distance layers from opposite corners gives , and . In dimension six an explicit graph gives . The integer certificates extend through dimension 32.
Check it yourself
How the bounds compare. The general inequality applies in every dimension. The finite certificates can give a larger lower bound.
| Dimension | General inequality | Certified lower bound | Edges in a known construction |
|---|---|---|---|
| 3 | 9 | 9 | 9 |
| 4 | 19 | 20 | 20 |
| 5 | 38 | 39 | 40 |
| 6 | 75 | 76 | 81 |
| 7 | 147 | 150 | 161 |
| 8 | 291 | 294 | 324 |
At : .
The first step of the proof, by hand. Every edge of joins a string of even weight to one of odd weight, so a path between two strings has the parity of their Hamming distance. Hence, in a subgraph of diameter , half of (the strings whose distance from a vertex has the parity of ) lies within distance of that vertex. And every vertex has degree at least 2: a vertex with one edge, along bit , could not reach the string that differs from it in every bit but within steps.
Worked examples
- . , and Theorem 1, the 1995 bound and the construction all give 9.
- . is a value the literature reports; two computations here checked it again, and a separate hand proof that was read by two agents with no gap found. Theorem 1 alone gives 19.
- Large . The distance-sphere argument raises the asymptotic lower coefficient to on the scale above . Theorem 1 alone gives . The 1995 bound gives , so Theorem 1 roughly doubles the second term. The construction has edges, so the true second term is still only known to lie between order and order .
Status and who checked it
- Written proofs, by hand. Theorem 1 counts the excess degree in balls around each vertex, using the parity fact above; Theorem 2 adds an identity special to .
- Formal verification. Lean checks the general lower bound and the integer certificates. The downloadable checker recomputes the finite inequalities, including the separate three-radius certificate in dimension seven.
- Comparison. The 1995 lower bound is never attained for . Five entries of a published edge-deletion table (Bass and Sudborough, Table 1, for to 8) are false: the table equals the 1995 bound at every , and at it implies a graph with 35 edges.
- Open. Whether is 39 or 40: a computer search to decide it ended "not decided" with no candidate.
Prior work
Credited. The question is from Erdős, Hamburger, Pippert and Weakley (1996), Graham and Harary (1992) and Bouabdallah, Delorme and Djelloul (1995). The 1995 bounds are Bouabdallah, Delorme and Djelloul's. The construction with edges is credited by Nenadov, Sawhney, Sudakov and Wagner to the 1996 paper; their paper gives a lower bound of the same order.
Searches run. Eight works the proofs cite were sought by title or DOI, with cached sources and digests: the 1992, 1995, 1996 and 1997 papers, Djelloul's 1993 thesis, Bass and Sudborough's 2000 and 2002 papers, and Jasim and Najim (2024). The 1995 summary calls both of its formulas bounds and claims no value; Bass and Sudborough's table goes back to 2000. No lower bound on above the 1995 one turned up, and no value of . No priority is claimed.
Still owed. The body of the 1995 paper, its 1990 version (a research report from Orsay) and Djelloul's thesis could not be reached on a second try; until they are read, this is a bounded reading, not an absence.
Further reading
- Nenadov, Sawhney, Sudakov and Wagner, "Bounded Degree Spanners of the Hypercube", arXiv 1910.09868
- A. Bouabdallah, C. Delorme and S. Djelloul, "Edge deletion preserving the diameter of the hypercube", Discrete Applied Mathematics 63 (1995), 91–95
- Niall Graham and Frank Harary, "Changing and unchanging the diameter of a hypercube", Discrete Applied Mathematics 37/38 (1992), 265–274.
- PatternBoost, arXiv 2411.00566, section 3.3