Diverse beam search to find densest-known planar unit distance graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911005655695360 |
|---|---|
| author | Engel, Peter Hammond-Lee, Owen Su, Yiheng Varga, Dániel Zsámboki, Pál |
| author_facet | Engel, Peter Hammond-Lee, Owen Su, Yiheng Varga, Dániel Zsámboki, Pál |
| contents | This paper addresses the problem of determining the maximum number of edges in a unit distance graph (UDG) of $n$ vertices using computer search. An unsolved problem of Paul Erdős asks the maximum number of edges $u(n)$ a UDG of $n$ vertices can have. Those UDGs that attain $u(n)$ are called "maximally dense." In this paper, we seek to demonstrate a computer algorithm to generate dense UDGs for vertex counts up to at least 100. Via beam search with an added visitation metric, our algorithm finds all known maximally dense UDGs up to isomorphism at the push of a button. In addition, for $15 < n$, where $u(n)$ is unknown, i) the algorithm finds all previously published densest UDGs up to isomorphism for $15 < n \le 30$, and ii) the rate of growth of $u(n)/n$ remains similar for $30 < n$. The code and database of over 60 million UDGs found by our algorithm can be found at https://codeberg.org/zsamboki/dbs-udg. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_15317 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Diverse beam search to find densest-known planar unit distance graphs Engel, Peter Hammond-Lee, Owen Su, Yiheng Varga, Dániel Zsámboki, Pál Combinatorics Discrete Mathematics Metric Geometry This paper addresses the problem of determining the maximum number of edges in a unit distance graph (UDG) of $n$ vertices using computer search. An unsolved problem of Paul Erdős asks the maximum number of edges $u(n)$ a UDG of $n$ vertices can have. Those UDGs that attain $u(n)$ are called "maximally dense." In this paper, we seek to demonstrate a computer algorithm to generate dense UDGs for vertex counts up to at least 100. Via beam search with an added visitation metric, our algorithm finds all known maximally dense UDGs up to isomorphism at the push of a button. In addition, for $15 < n$, where $u(n)$ is unknown, i) the algorithm finds all previously published densest UDGs up to isomorphism for $15 < n \le 30$, and ii) the rate of growth of $u(n)/n$ remains similar for $30 < n$. The code and database of over 60 million UDGs found by our algorithm can be found at https://codeberg.org/zsamboki/dbs-udg. |
| title | Diverse beam search to find densest-known planar unit distance graphs |
| topic | Combinatorics Discrete Mathematics Metric Geometry |
| url | https://arxiv.org/abs/2406.15317 |