Penny graphs in the hyperbolic plane
Ádám Sagmeister, Konrad J. Swanepoel · 2025
Read Penny graphs in the hyperbolic plane by Ádám Sagmeister, Konrad J. Swanepoel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24832.txt.
Introduction
Adam Sagmeister and Konrad Swanepoel bound how many touching pairs can occur among equal circles packed in the hyperbolic plane. In flat geometry, a spiral based on triangular tiling is best, and special hyperbolic cases were known for certain diameters tied to triangular tilings. They give upper and lower bounds for every positive diameter.
For diameters above a stated threshold, with one exception, the touching count falls below a spiral construction in the order-seven triangular tiling, which they conjecture is extremal. A lower bound above two per circle is also proved. Discrete geometry readers get a broad picture of penny graphs in curved space.
Catalog record
| CREATOR | Ádám Sagmeister, Konrad J. Swanepoel |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24832
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Penny graphs in the hyperbolic plane Thanks: Ádám Sagmeister is funded by the grant NKFIH 150151. Project no. 150151 has been implemented with the support provided by the Ministry of Culture and Innovation of Hungary from the National Research, Development and Innovation Fund, financed under the ADVANCED_24 funding scheme. Thanks: Konrad Swanepoel is partially supported by ERC grant no. 882971, “GeoScape,” and by the Erdős Center. Ádám Sagmeister, Konrad J. Swanepoel Abstract . We consider the problem of finding the maximum number e d ( n ) e_{d}(n) of pairs of touching circles in a packing of n n congruent circles of diameter d d in the hyperbolic plane of curvature − 1 -1 . In the Euclidean plane, the maximum comes from a spiral construction of the tiling of the plane with equilateral triangles (Harborth 1974), with a similar result in the hyperbolic plane for the values of d d corresponding to the order- k k triangular tilings (Bowen 2000). We present various upper and lower bounds for e d ( n ) e_{d}(n) for all values of d > 0 d>0 . In particular, we prove that if d > 0.66114 … d>0.66114\dots except for d = 0.76217 … d=0.76217\dots , then the number of touching pairs is less than the one coming from a spiral construction in the order- 7 7 triangular tiling, which we conjecture to be extremal. We also give a lower bound e d ( n ) > ( 2 + ε d ) n e_{d}(n)>(2+\varepsilon_{d})n where ε d > 1 \varepsilon_{d}>1 for all d > 0 d>0 . 1991 Mathematics Subject Classification Primary 52C15, Secondary 52C10, 51M09 1. Introduction A penny graph is the incidence graph of a finite packing of congruent circles. In other words, for each circle in the packing, there is a vertex in the penny graph, and we join two vertices if their corresponding circles touch. Equivalently, such a graph is the minimum-distance graph of a finite set of points with minimum distance d , and where two points are joined by an edge if their distance is d . In the Euclidean plane, the combinatorics of penny graphs have been well studied, starting with Erdős’s seminal paper [ 7 ] and Harborth’s determination of the maximum number of edges [ 9 ] , and with other contributions by Kupitz [ 11 ] , Pach and Tóth [ 15 ] , Tóth [ 24 ] , Csizmadia [ 5 ] , Swanepoel [ 20 ] , Eppstein [ 6 ] , and Sagdeev [ 18 ] . Harborth showed that the maximum number of edges of a penny graph with n vertices is \lfloor 3n-\sqrt{12n-3}\rfloor . The analogous question can be considered in higher dimensional Euclidean space [ 2 ] , in normed spaces (see the references in the survey [ 21 ] ) and for spaces of non-zero constant curvature, namely spherical and hyperbolic spaces. Note that in the latter cases, the maximum number of edges will depend on the size of the spheres relative to the curvature. For the 2 -dimensional sphere, Bezdek, Connelly and Kertész [ 1 ] improved on the trivial upper bound of 5n/2 , and for the hyperbolic plane, Bowen [ 4 ] showed that a certain construction is optimal if the minimum distance d is such that the plane can be tiled by equilateral triangles of side length d . It is the purpose of this paper to investigate the maximum number of minimum distances for all values of d>0 . Our main results are various upper and lower bounds for the maximum number of edges in a penny graph on n vertices, depending on d , as detailed in the next section. We also give a slightly simpler proof of Bowen’s result that when the distance is that of the order- k triangular tiling, the maximum number of edges is attained by a certain spiral construction. Using the same ideas, we show that a spiral construction is also optimal for maximizing the number of edges in subgraphs of the \{p,q\} -tilings in the hyperbolic plane. Finally, we also consider the simple problem of “infinite diameter circles”, and find the tight maximum number of touching pairs in a packing of n horocycles. 2. Our results Given d>0 and n\in\mathbb{N} , let e_{d}(n) denote the maximum number of touching pairs in a packing of circles of diameter d in the hyperbolic plane (of curvature -1 ). Equivalently, this is the largest number of edges in a minimum-distance graph on n vertices with minimum distance d in the hyperbolic plane. Since e_{d}(n) is superadditive, it follows from Fekete’s lemma that \lim_{n\to\infty}e_{d}(n)/n=:c(d) exists. In fact, it is easy to see that e_{d}(m+n)\geq e_{d}(m)+e_{d}(n)+2 if m\geq 2 and n\geq 1 . This (or a simple construction) immediately gives e_{d}(n)\geq 2n-3 for all d . Since all minimum-distance graphs are planar, we also have e_{d}(n)\leq 3n-6 . Thus, 2\leq c(d)\leq 3 . In this paper we show that both inequalities are strict and find upper bounds and lower bounds of c(d) for all values of d . The bounds are illustrated in Figure 1 and described more precisely below, after introducing some notation. Figure 1. Upper and lower bounds for c(d) . The red upper bound \gamma_{1}(d) holds for all d and is tight for the order- k triangular tilings (the dots on the red graph). The orange \gamma_{2}(d) and green \gamma_{3}(d) bounds hold for all d\neq d(k) . The bound \gamma_{3}(\overline{d}(6))=2.39698265738619\dots is the best we have for d=\overline{d}(6) (see the dot on the green curve), and the bounds \gamma_{2}(\overline{d}(k)) are the best for d=\overline{d}(k) , k\geq 7 (see the dots on the orange curve). The blue \gamma_{4}(d) and purple \gamma_{5}(d) upper bounds hold for all d such that d\neq d(k) , k\geq 7 and d\neq\overline{d}(k) , d\geq 6 . These curves intersect at d=1.1128036956703866\dots . Apart from the semiregular tiling d=\overline{d}(6) , we have that Conjecture 2.6 holds for all d>0.6611380871710578\dots , the solution of \gamma_{5}(d)=3-1/\varphi (shown by the dot on the purple curve). The vertical gray lines are at the values where d=\overline{d}(k) . The horizontal gray lines are at 3-1/\varphi and 2.75 . The black step function is the lower bound \gamma_{6}(d) . For k\geq 7 , let d(k) denote the side length of an equilateral triangle with angles all equal to 2\pi/k . These triangles are the prototiles of the order- k triangular tiling of the hyperbolic plane, where each vertex has degree k . For any distance d>0 in the hyperbolic plane of curvature -1 , denote the angle of a regular triangle with side length d by \alpha=\alpha(d) , and its area by A(d)=\pi-3\alpha . We can compute \alpha using the relation \cos\alpha=\dfrac{\tanh d/2}{\tanh d} . We also let \alpha_{m}=\alpha_{m}(d) denote the angle of a regular m -gon with side length d . Then \sin\alpha_{m}/2=\cos(\pi/k)/\cosh(d/2) . In particular, this gives another way to express the relation between \alpha=\alpha_{3} and d , namely \sin\alpha/2=(2\cosh d/2)^{-1} . Also, the angle \alpha_{4} of a square satisfies \sin\alpha_{4}/2=\sqrt{2}\sin\alpha/2 . For any k\geq 7 , we let d(k) be the value of d such that \alpha(d)=2\pi/k , and for k\geq