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
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "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".
Emmy: Here's the gist of the paper. The Hamming graph H(d, 3) is explored as a purely combinatorial object to investigate its geometric properties, specifically whether it can be drawn in the plane with unit edge lengths and no non-adjacent vertices at distance one, revealing a rich interplay between arithmetic realizations over coordinate fields and combinatorial crossing constraints.
Ada: The Hamming graph H(d, 3) can be drawn faithfully in the plane for every d, but its realizations exhibit a hidden flexibility that allows it to be realized over many number fields at once, with almost every realization being transcendental.
Emmy: This flexibility is rooted in the Minkowski sum construction of unit triangles, which provides a continuum of faithful realizations that span the classical constructibility hierarchy—ruler-and-compass, origami, and exotic—as one moves through different base angles.
Ada: Arithmetic Realizations and Coordinate Fields The arithmetic aspect of the graph is tied to its realization over a coordinate field; while a rigid unit-distance graph has a fixed algebraic address, the flexible nature of H(d, 3) allows it to roam through different number fields.
Paper summary: Ada: So, wrapping up this paper, the authors are focusing on how the title itself—"The crossing number and the unit-distance crossing number of the Hamming graphs H(d,three)=K□d three and their realizations over many coordinate fields"—ties everything together <ref:2609.13757#pg1,The crossing number and the unit-distance crossing number of the Hamming>.
Emmy: They’re emphasizing that these two concepts, crossing numbers and unit-distance crossings, aren't separate problems. They are two sides of the same coin for this specific class of graphs.
Kolya: And they show that the flexibility of the graph is what dictates where you find the optimum for those unit-distance drawings. They found that this constructibility tier is exactly where those minimum crossing counts are located within all possible flexes.
Ada: So, the big implication is that if you want to minimize crossings in a unit-distance setting, you should look at constructions tied to ruler and compass or origami, not just some generic drawing.
Emmy: That’s what they found. The freedom that lets H(d, three) move across those constructibility tiers is precisely what governs the minimization of crossings <ref:2609.13757#pg1>.
Kolya: And they mention a future direction where they are trying to find a matching lower bound for the unit-distance crossing number that matches the order of growth we expect, which is proportional to n squared times log n.
Ada: So, it’s about proving that every single faithful unit realization of these graphs must have at least that many crossings. That would confirm the relationship they've been exploring between geometry and arithmetic in this context.
Conclusion: Ada: So we’re wrapping up on this paper about Hamming graphs and unit distances, specifically focusing on how they behave when you realize them over many different coordinate fields.
Emmy: The core idea is that these two things—the crossing number and the unit-distance crossing number—aren't just separate counting problems; they are tied to the graph’s flexibility.
Kolya: I think what they nail here is that this flexibility, this ability of the graph to roam over different mathematical fields, actually dictates where you find the best possible crossings.
Ada: Right. They found that this constructibility tier—the ruler-and-compass or origami level—is where you’re most likely to find those minimum unit-distance drawings.
Emmy: It’s interesting because the authors show that this freedom isn't just any freedom; it's tied to specific, constructible sets of numbers.
Kolya: And they are suggesting that this connection between geometry and arithmetic is what forces the unit-distance crossing number to grow in a specific way as you add more vertices.
Ada: Exactly. The paper establishes that the ordinary crossing number grows like n squared, but the unit-distance one has an extra log n factor because of those unit length constraints.
Emmy: That gap between those two numbers, that log n difference is what they think forces every single faithful unit drawing to have a minimum number of crossings that scales with n squared times log n.
Kolya: That’s the big question for me—is that lower bound actually achievable in practice, or does it just hold true for some theoretical configuration?
Ada: And the authors are pushing for a matching lower bound proof, trying to show that you can't draw any faithful unit realization with fewer crossings than that log n factor suggests.
Emmy: So we’ve seen how the structure of these graphs allows them to sit on different levels of construction, and now we’re looking at what that means for the actual minimum number of edges they have to cross when you force every edge to be exactly one unit long.
Universidade do Estado do Rio de Janeiro
math.CO
Submitted: 2026-09-12
Updated: 2026-11-09
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
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 89/100
The gist: The Hamming graph H(d, 3) is explored as a purely combinatorial object to investigate its geometric properties…
Key concepts
- Hamming Graph H(d, 3)
- This graph is a combinatorial object used to study geometric drawing problems. It has vertices representing sequences of length d with entries from {1, 2, 3}, and edges connect vertices differing in exactly one position by a specific rule. The paper focuses on its crossing numbers in different metrics.
- Constructibility Hierarchy
- This hierarchy classifies algebraic realizations of graphs based on the complexity of the number field required to draw them faithfully. It ranges from simple ruler-and-compass constructions to more exotic fields, showing how a graph's arithmetic properties are linked to its geometric drawing possibilities.
- Unit-Distance Crossing Number (udcr)
- This measures the minimum number of crossings when drawing a graph in the plane such that all edges have exactly unit length. The paper finds this number is related to the ordinary crossing number but is higher by a factor of Θ(log n), reflecting the difficulty introduced by forcing unit edge lengths.
- Flexibility and Realization Variety
- The graph H(d, 3) has a positive-dimensional space of faithful geometric drawings. This flexibility allows it to exist over many different coordinate fields simultaneously, spanning the constructibility hierarchy. This freedom is key to understanding how crossing numbers are minimized.
Terminology
Summary
The Hamming graph H(d, 3) is explored as a purely combinatorial object to investigate its geometric properties, specifically whether it can be drawn in the plane with unit edge lengths and no non-adjacent vertices at distance one, revealing a rich interplay between arithmetic realizations over coordinate fields and combinatorial crossing constraints. p. 0
The Hamming graph H(d, 3) can be drawn faithfully in the plane for every d, but its realizations exhibit a hidden flexibility that allows it to be realized over many number fields at once, with almost every realization being transcendental. p. 0 This flexibility is rooted in the Minkowski sum construction of unit triangles, which provides a continuum of faithful realizations that span the classical constructibility hierarchy—ruler-and-compass, origami, and exotic—as one moves through different base angles. p. 0
Arithmetic Realizations and Coordinate Fields
The arithmetic aspect of the graph is tied to its realization over a coordinate field; while a rigid unit-distance graph has a fixed algebraic address, the flexible nature of H(d, 3) allows it to roam through different number fields. The generic faithful realization is transcendental, meaning its coordinate field is not a number field at all, reflecting that the tidy Galois picture is only a measure-zero shadow of a vast transcendental continuum. p. 0 The constructibility hierarchy classifies algebraic realizations based on the degree [K:Q], ranging from ruler-and-compass to exotic fields. p. 4
Combinatorial Crossing Constraints
The paper separates the ordinary crossing number from the unit-distance crossing number, finding a recursive method that controls both invariants. The unit-distance crossing number is trapped between close bounds, with the constraint provably forcing strictly more crowding than in a generic drawing. p. 0 The recursive method decomposes the graph into three shrunken copies of itself plus a connecting bundle, leading to the recurrence c(n) = 3 c(n/3) + g(n), where g(n) represents the geometric sums of crossings. p. 0
The Bridge Between Geometry and Arithmetic
The bridge between these two problems is the flex itself, as the freedom over which crossings are minimized is not generic but a constructible one, leading to a realization that sits on the constructibility web. The same freedom that lets the graph roam coordinate fields also governs how crossings are minimized, and the least-crossing drawing found is a constructible one. p. 0
The Crossing Number Bounds
The ordinary crossing number cr(H) is settled to be Θ(n 2) unconditionally, with an upper bound derived from a one-page layout and a lower bound from the bisection width and. The unit-distance crossing number udcr(H) is bracketed between the ordinary crossing number and an upper bound derived from the Minkowski drawing, which is O(n squared log n). p. 0 Conjecture 1 posits that udcr(H) = Θ(n squared log n), matching the order of the Minkowski count. p. 6
Conclusion on Optimality
The study concludes that the constructibility tier is the location of the optimum for unit-distance drawings, as it is where minimum crossing counts are found within the flex. The flexibility that allows H(d, 3) to range over tiers is precisely what governs udcr minimization, and this same freedom is present in spatial realizations. p. 5
Future Directions
Future work focuses on several open questions, including the matching lower bound udcr(H) = omega(n squared log n), which requires forcing every faithful unit realization to have at least that many crossings. Additionally, determining whether the best crossing count for H(d, 3) is attained at a symmetric twist or a generic transcendental point remains open. p. 0 The study also suggests that for q ≥ 4, the rotational group being non-abelian means the internal flex dimension might be strictly larger than d − 1. p. 6
Reproducibility and Complexity
All realizations, edge counts, ghost counts, degree and irreducibility statements are produced and verified in exact arithmetic by the accompanying program generate h33.py. The recognition problem for unit-distance graphs is ∃R-complete, which is expected because the realization space is a positive-dimensional real semialgebraic set whose generic point is transcendental. p. 4 The complexity analysis shows that the ordinary crossing number cr(H) = Θ(n 2) and udcr(H) = O(n squared log n), which are polynomial bounds, far below the maximum Θ(n 4) of Kn. p. 0
Summary of Bounds
The paper establishes the bounds cr(H) = Θ(n 2) and udcr(H) = O(n squared log n), with the lower bound matching the upper bound order, suggesting that udcr(H) = Θ(n squared log n). The explicit closed-form majorant for udcr is given by 3/2 n squared (log3 n) squared - log3 n + 1. p. 6
Small Cases and Exact Values
For the base case H(3, 3), the ordinary crossing number cr(K3□K3) is settled exactly to be 3, while udcr(K3□K3) ≤ 9 is the Minkowski value, conjectured exact but without a matching lower bound. For d ≥ 3, determining the exact cr or udcr for any single d is open. p. 0 The origami realization for H(d, 3) provides a canonical algebraic reference, and its crossing count grows as shown in Table 1. p. 0
The Role of Flexibility
The structural contrast is that a rigid unit-distance graph pins its coordinate field, whereas a flexible one like H(3, 3) has a positive-dimensional realization variety that allows it to occupy the compass, origami, and exotic fields simultaneously. This flexibility is what lets the graph range over the constructibility hierarchy. p. 5 The unit-distance geometry and Galois arithmetic are two independent certificates of the same graph. p. 5 p. 5 p. 5
The Recursive Structure
The recursive structure H(d, 3) = H(d − 1, 3) □ K3 involves three translated copies plus triangle bundles, leading to the recurrence c(n) = 3 c(n/3) + g(n), where g(n) is the sum of crossings from bundle edges. This recursion allows for the explicit computation of upper bounds udcr ≤ c(n), and the lower bound cr ≥ n/3.
The Order of Growth
The order of growth for the ordinary crossing number is cr(H) = Θ(n 2), while for the unit-distance crossing number, udcr(H) = O(n squared log n). The single logarithm in udcr is a cost of the unit-length constraint alone, separating it from the ordinary counting. p. 0
The Unit Crossing Number Gap
The gap between the two invariants grows to a factor Θ(log n), implying that udcr(H)/cr(H) → ∞. This separation is conjectured to be the key to proving udcr(H) = Θ(n squared log n). p. 6 p. 6 The unit constraint then inflates the crossing number by a factor Θ(log n), suggesting that every faithful unit realization is forced into Ω(n squared log n) crossings. p. 0 p. 0
The Role of the Origami Realization
The origami realization, specifically the enneagon twist by 20◦ = 60◦/3 in the trisection field Q(sin 20◦), is adopted as a canonical algebraic reference because it provides both a crossing-minimizing constructible configuration and serves as a tight simple upper bound for udcr(H). The origami tier is thus the location of the optimum for unit-distance drawings. p. 0
The Nature of Faithfulness
Faithfulness is an open geometric condition certified over R with no algebraic extension, while the constructibility tier is an arithmetic invariant of the coordinate field, certified only inside that extension. Almost every faithful realization is transcendental and has no tier at all, meaning the compass/origami/exotic trichotomy is carried by a dense, measure-zero algebraic web inside the predominantly transcendental faithful family. p. 5 The unit-distance geometry and Galois arithmetic are two independent certificates of the same graph.
The Recursive Step Details
The recursive decomposition H(d, 3) = H(d − 1, 3) □ K3 involves three translated copies plus triangle bundles, which leads to the four-type crossing decomposition c(n) = 3 c(n/3) + g(n), where g is the sum of crossings from bundle edges. The intra-copy term is exactly 3 c(d-1) because each copy is a translate of the smaller drawing. p. 0 p. 0 The bundle remainder g(n) follows the predicted Θ(n squared log n) law, which settles udcr = O(n squared log n). p. 6 p. 6
The Unit Upper Bound Derivation
The upper bound for udcr is derived by bounding the crossings of the Minkowski drawing, where every edge is a unit segment and crossings are counted using concentration arguments. This yields udcr(H) ≤ c(n) ≤ 1/2 (d n) O(n), resulting in O(n squared log n). p. 6 The explicit closed-form majorant is given by 3/2 n squared ((log3 n) squared - log3 n + 1). p. 6
The Lower Bound Argument
The lower bound for the ordinary crossing number is established by the bisection–crossing inequality, which shows cr(H) ≥ omega(n 2). The unit-distance lower bound udcr(H) ≥ cr(H) is immediate, but a matching lower bound udcr(H) = omega(n squared log n) remains the single open point. p. 1
The Spatial Realizations
Spatial realizations in R cubed show that the flexibility grows, and the faithful spatial realizations form a nine-parameter continuum, which is vastly larger than the planar two-parameter family. These spatial realizations can reach the origami and exotic tiers through rotations of one triangle. p. 5 The transcendental abundance of faithful realizations is amplified in space rather than reduced, and the faithfulness diagram is a two-dimensional shadow of a much higher-dimensional faithful set. p. 5
The Final Synthesis
The two halves of the paper describe one object: the flexibility that lets H(3, 3) range over compass, origami, and exotic fields at once. The unit-distance geometry and Galois arithmetic are two independent certificates of the same graph. The crossing count is a function on the flex, and the lowest value found is at the origami enneagon twist, which is adopted as a reference drawing. p. 0 The constructibility tier is thus the location of the optimum for unit-distance drawings. p. 5
The Complexity Landscape
The complexity analysis shows that cr(H) = Θ(n 2) and udcr(H) = O(n squared log n), which are polynomial bounds, far below the maximum Θ(n 4) of Kn. The recognition problem is ∃R-complete, which is expected because the realization space is a positive-dimensional real semialgebraic set whose generic point is transcendental. p. 4 The jump from NP to ∃R is precisely the passage from a discrete/algebraic search to a real, transcendental one. p. 6
The Gap in the Unit Count
The gap between the two invariants grows to a factor Θ(log n), implying that udcr(H)/cr(H) → ∞. This separation is conjectured to be the key to proving udcr(H) = Θ(n squared log n). The unit constraint then inflates the crossing number by a factor Θ(log n), suggesting that every faithful unit realization is forced into Ω(n squared log n) crossings.
The Conjecture on Optimality
Conjecture 2 posits that constructible (compass or origami) realizations of H(d, 3) are near-optimal for udcr, strictly better than the equal-spacing symmetric realization and than a generic transcendental point. For H(3, 3), the minimum is attained exactly at the origami enneagon twist of Q(sin 20◦). p. 7
The recursive decomposition H(d, 3) = H(d − 1, 3) □ K3 involves three translated copies plus triangle bundles, leading to the four-type crossing decomposition c(n) = 3 c(n/3) + g(n), where g is the sum of crossings from bundle edges. The intra-copy term is exactly 3 c(d-1) because each copy is a translate of the smaller drawing. The bundle remainder g(n) follows the predicted Θ(n squared log n) law, which settles udcr = O(n squared log n).
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved geometric realization engine: AI systems can generate faithful unit-distance drawings for Hamming graphs H(d, 3) by selecting parameters (base angles) from known constructibility tiers like compass (Q(sqrt2, sqrt3)), origami (Q(sin 20), degree 6), or exotic fields to produce exact coordinates.
-
Realization field classification: The system can determine the arithmetic complexity of a graph realization by calculating the degree of the coordinate field K over Q, classifying it into ruler-and-compass, origami, or exotic tiers based on this degree.
-
Unit-distance crossing number estimation: AI can estimate the unit-distance crossing number udcr(H) by using recursive methods based on Cartesian product decomposition and geometric sums g(n), providing an order bound of O(n squared log n).
-
Crossing minimization optimization: The system can search for the optimal realization by minimizing the crossing count over the two-parameter flex, identifying constructible points (like the origami enneagon twist) as near-optimal solutions for specific graphs.
-
Realization flexibility analysis: The AI can calculate the internal infinitesimal flexibility dimension of a graph H(d, 3) by analyzing the rank of its rigidity matrix, determining it is exactly d minus one in generic Minkowski realizations.
Sources
- Exact certification of the coordinate fields of the triangle-free Exoo-Ismailescu unit-distance graphs EI17 and EI19 (HoG 51375, 51376): a solvable-non-solvable dichotomy (origami vs. S20) and the Laman-number conjecture
- Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
- Remarks on the disproof of the unit distance conjecture
- Unit distance graphs with few crossings per edge
- Rectilinear Crossing Number of Graphs Excluding Single-Crossing Graphs as Minors
- Hypercube drawings with no long plane paths
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality