Diverse Beam Search to Find Densest-Known Planar Unit Distance Graphs

Engel, Peter and Hammond-Lee, Owen and Su, Yiheng and Varga, Dániel and Zsámboki, Pál (2025) Diverse Beam Search to Find Densest-Known Planar Unit Distance Graphs. EXPERIMENTAL MATHEMATICS. ISSN 1058-6458 (In Press)

Preview

Text 2406.15317v2.pdf - Published Version Download (534kB) | Preview

Abstract

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˝os 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 ≤ 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 will be open-sourced at time of publication.

Actions (login required)

Edit Item