Paperlane

no. 13 · Wednesday 11 November 2026

The crossing number and the unit-distance crossing number of the Hamming graphs H(d,3)=K_3^{box d}, and their realizations over many coordinate fields

Haroldo Costa Silva Filho

math.CO · v2 · 49 pp

Abstract

The Hamming graph H(d,3)=K_3^{box d} (n=3^d vertices) is the graph of single-symbol errors of ternary codes. Can it be drawn in the plane with every edge one unit long and no two non-adjacent vertices a unit apart? It can, for every d, joining two problems into one. Arithmetic: over which coordinate fields is it realizable? As a Minkowski sum of unit triangles (planar for the whole family only in base 3), each H(d,3) has not one faithful realization but a (d-1)-parameter continuum, whose field climbs the constructibility hierarchy (ruler-and-compass, origami, and beyond); yet almost every realization is transcendental, in no number field, matching the exists-R hardness of unit-distance recognition. Combinatorial: beside the ordinary crossing number cr we introduce the unit-distance crossing number udcr(G), the fewest crossings over faithful unit drawings (every edge a unit segment); it is the rectilinear crossing number under unit length, so cr <= rcr <= udcr. We prove cr(H(d,3))=Theta(n^2) (one-page 7/6 n^2 above; spectral bisection Omega(n^2) below) and cr <= 2/3 n^2 via a two-page book layout; and udcr(H(3,3))=231 exactly, with udcr(H(d,3))=O(n^2 log n). A structure theorem makes every faithful planar realization a Minkowski sum, so the realization variety is an explicit (d-1)-parameter flex containing the udcr optimum; the matching udcr=Omega(n^2 log n) is the central open problem. The invariants differ: for cr the crossing-minimal drawings are structurally opaque, whereas the udcr optimum is itself a faithful Minkowski realization. All claims are verified in exact arithmetic with reproducible code and figures.

comments
v2: 49 pages. Introduces the unit-distance crossing number udcr as a defined invariant (now stated in the abstract); adds a two-page book bound cr(H(d,3)) <= 2/3 n^2, verified free rectilinear drawings cr(H(3,3)) <= 99 and cr(H(4,3)) <= 1817, spectral references (Fiedler; Brouwer-Haemers; Mohar), and a Conclusions section separating theorems from conjectures. Reproducible code and figures
fields
Combinatorics
pdf ↗ page arXiv:2609.13757 ↗