×

Contact graphs of unit sphere packings revisited. (English) Zbl 1273.52022

The vertices of the contact graph of a finite packing of unit balls in Euclidean \(3\)-space correspond to the single balls of the packing. Two vertices are connected by an edge if the respective balls touch each other.
The following are shown: A contact graph with \(n\) vertices has less than \(6n-0.926n^{\frac{2}{3}}\) edges. This improves a former bound from [K. Bezdek, Discrete Comput. Geom. 48, No. 2, 298–309 (2012; Zbl 1259.52013)].
A contact graph with \(n\) vertices contains at most \(\frac{25}{3}n\) triangles and at most \(\frac{11}{4}n\) complete subgraphs with \(4\) vertices. The authors point out that recent work of T. C. Hales allows to reduce the last two bounds to \(8n\) and \(\frac{5}{2}n\), respectively.
Similar results are obtained for contact graphs of lattice packings of unit balls.

MSC:

52C17 Packing and covering in \(n\) dimensions (aspects of discrete geometry)
05B40 Combinatorial aspects of packing and covering
11H31 Lattice packing and covering (number-theoretic aspects)
52C45 Combinatorial complexity of geometric structures

Citations:

Zbl 1259.52013

Software:

Flyspeck
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bezdek K: On the maximum number of touching pairs in a finite packing of translates of a convex body. J. Combin. Theory Ser. A 98, 192-200 (2002) · Zbl 1010.52014 · doi:10.1006/jcta.2001.3204
[2] Bezdek K.: Contact numbers for congruent sphere packings in Euclidean 3-space. Discrete Comput. Geom 48, 298-309 (2012) · Zbl 1259.52013 · doi:10.1007/s00454-012-9405-9
[3] Conway J.H., Sloane N.J.A.: Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices. Proc. R. Soc. Lond. A 436, 55-68 (1992) · Zbl 0747.11027 · doi:10.1098/rspa.1992.0004
[4] Csikós B., Lángi Zs., Naszódi M.: A generalization of the discrete isoperimetric inequality for piecewise smooth curves of constant geodesic curvature. Period. Math. Hungar 53, 121-131 (2006) · Zbl 1136.51014 · doi:10.1007/s10998-006-0026-z
[5] Fejes Tóth L.: Regular Figures. Pergamon Press, Oxford (1964) · Zbl 0134.15705
[6] Hales, T.C.: Dense Sphere Packing—A Blueprint for Formal Proofs, London Mathematical Society Lecture Note Series (No. 400). Cambridge University Press, Cambridge (2012) · Zbl 1263.52001
[7] Hales, T.C.: Personal communication at the AMS special session on discrete geometry and algebraic combinatorics. In: 2013 Joint Mathematics Meetings, San Diego (January 9-12, 2013)
[8] Hales, T.C.: Sharp Bounds on the Number of Touching Pairs and Triples in a Packing of Spherical Caps. http://flyspeck.googlecode.com/svn/trunk/projects_discrete_geom/bezdek_reid/ (January, 2013) · Zbl 0148.16202
[9] Harborth H.: Lösung zu Problem 664A. Elem. Math 29, 14-15 (1974)
[10] Hlineny P., Kratochvil J.: Representing graphs by disks and balls. Discret. Math 229, 101-124 (2001) · Zbl 0969.68118 · doi:10.1016/S0012-365X(00)00204-1
[11] Matousek J.: Lectures on Discrete Geometry. Springer, New York (2002) · Zbl 0999.52006 · doi:10.1007/978-1-4613-0039-7
[12] Molnár J.: Kreislagerungen auf Flächen konstanter Krümmung. Math. Ann 158, 365-376 (1965) · Zbl 0148.16202 · doi:10.1007/BF01360179
[13] Osserman R.: The isoperimetric inequality. Bull. Am. Math. Soc. 84, 1182-1238 (1978) · Zbl 0411.52006 · doi:10.1090/S0002-9904-1978-14553-4
[14] Ratcliffe J.G.: Foundations of Hyperbolic Manifolds, 2nd edn. Springer, New York (2006) · Zbl 1106.51009
[15] Rogers C.A.: Packing and Covering. Cambridge University Press, Cambridge (1964) · Zbl 0176.51401
[16] Schütte K., van der Waerden B.L.: Das Problem der dreizehn Kugeln. Math. Ann 125, 325-334 (1953) · Zbl 0050.16701 · doi:10.1007/BF01343127
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.