The Erdős unit distance problem for small point sets
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917920698793984 |
|---|---|
| author | Alexeev, Boris Mixon, Dustin G. Parshall, Hans |
| author_facet | Alexeev, Boris Mixon, Dustin G. Parshall, Hans |
| contents | We improve the best known upper bound on the number of edges in a unit-distance graph on $n$ vertices for each $n\in\{16,\ldots,30\}$. When $n\leq 21$, our bounds match the best known lower bounds, and we fully enumerate the densest unit-distance graphs in these cases.
On the combinatorial side, our principle technique is to more efficiently generate $\mathcal{F}$-free graphs for a set of forbidden subgraphs $\mathcal{F}$. On the algebraic side, we are able to determine programmatically whether many graphs are unit-distance, using a custom embedder that is more efficient in practice than tools such as cylindrical algebraic decomposition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_11914 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Erdős unit distance problem for small point sets Alexeev, Boris Mixon, Dustin G. Parshall, Hans Combinatorics Metric Geometry We improve the best known upper bound on the number of edges in a unit-distance graph on $n$ vertices for each $n\in\{16,\ldots,30\}$. When $n\leq 21$, our bounds match the best known lower bounds, and we fully enumerate the densest unit-distance graphs in these cases. On the combinatorial side, our principle technique is to more efficiently generate $\mathcal{F}$-free graphs for a set of forbidden subgraphs $\mathcal{F}$. On the algebraic side, we are able to determine programmatically whether many graphs are unit-distance, using a custom embedder that is more efficient in practice than tools such as cylindrical algebraic decomposition. |
| title | The Erdős unit distance problem for small point sets |
| topic | Combinatorics Metric Geometry |
| url | https://arxiv.org/abs/2412.11914 |