Rigidity-Induced Scaling Laws in Unit Distance Graphs: The Algebraic Collapse of Dense Substructures
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915757345996800 |
|---|---|
| author | Aloisio, Lucas |
| author_facet | Aloisio, Lucas |
| contents | We revisit the classical Unit Distance Problem posed by Erdős in 1946. While the upper bound of $O(n^{4/3})$ established by Spencer, Szemer'edi, and Trotter (1984) is tight for systems of pseudo-circles, it fails to account for the algebraic rigidity inherent to the Euclidean metric. By integrating structural rigidity decomposition with the theory of Cayley-Menger varieties, we demonstrate that unit distance graphs exceeding a critical density must contain rigid bipartite subgraphs. We prove a "Flatness Lemma," supported by symbolic computation of the elimination ideal, showing that the configuration variety of a unit-distance $K_{3,3}$ (and by extension $K_{4,4}$) in $\mathbb{R}^2$ is algebraically singular and collapses to a lower-dimensional locus. This dimensional reduction precludes the existence of the amorphous, high-incidence structures required to sustain the $n^{4/3}$ scaling, effectively improving the upper bound for non-degenerate Euclidean configurations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18831 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rigidity-Induced Scaling Laws in Unit Distance Graphs: The Algebraic Collapse of Dense Substructures Aloisio, Lucas Combinatorics Metric Geometry 52C10 (Primary), 14P10, 05C10 (Secondary) We revisit the classical Unit Distance Problem posed by Erdős in 1946. While the upper bound of $O(n^{4/3})$ established by Spencer, Szemer'edi, and Trotter (1984) is tight for systems of pseudo-circles, it fails to account for the algebraic rigidity inherent to the Euclidean metric. By integrating structural rigidity decomposition with the theory of Cayley-Menger varieties, we demonstrate that unit distance graphs exceeding a critical density must contain rigid bipartite subgraphs. We prove a "Flatness Lemma," supported by symbolic computation of the elimination ideal, showing that the configuration variety of a unit-distance $K_{3,3}$ (and by extension $K_{4,4}$) in $\mathbb{R}^2$ is algebraically singular and collapses to a lower-dimensional locus. This dimensional reduction precludes the existence of the amorphous, high-incidence structures required to sustain the $n^{4/3}$ scaling, effectively improving the upper bound for non-degenerate Euclidean configurations. |
| title | Rigidity-Induced Scaling Laws in Unit Distance Graphs: The Algebraic Collapse of Dense Substructures |
| topic | Combinatorics Metric Geometry 52C10 (Primary), 14P10, 05C10 (Secondary) |
| url | https://arxiv.org/abs/2601.18831 |