Expandability radius versus density of a lattice packing

In the present paper lattice packings of open unit discs are considered in the Euclidean plane. Usually, efficiency of a packing is measured by its density, which in case of lattice packings is the quotient of the area of the discs and the area of the fundamental domain of the packing. In this paper another measure, the expandability radius is introduced and its relation to the density is studied. The expandability radius is the radius of the largest disc which can be used to substitute a disc of the packing without overlapping the rest of the packing. Lower and upper bounds are given for the density of a lattice packing of given expandability radius for any feasible value. The bounds are sharp and the extremal configurations are also presented. This packing problem is related to a covering problem studied by Bezdek and Kuperberg [BK97]. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the Existence of Completely Saturated Packings and Completely Reduced Coverings

We prove the following conjecture of G. Fejes Toth, G. Kuperberg, and W.Kuperberg: every body K in either n-dimensional Euclidean or n-dimensional hyperbolic space admits a completely saturated packing and a completely reduced covering. Also we prove the following counterintuitive result: for every >0, there is a body K in hyperbolic n-space which admits a completely saturated packing with density less than but which also admits a tiling.     

A Bound on the Ratio between the Packing and Covering Densities of a Convex Body

It is shown that if K is a compact convex set which is centrally symmetric and has a nonempty interior, then the density of the tightest lattice packing with copies of K in Euclidean 3-space divided by the density of the thinnest lattice covering of Euclidean 3-space with copies of K is greater than or equal to 1/4. It is likely this bound can be improved, though not beyond approximately 1/2. Received October 8, 1998, and in revised form December 30, 1998.     

Highly saturated packings and reduced coverings

We introduce and study certain notions which might serve as substitutes for maximum density packings and minimum density coverings. A body is a compact connected set which is the closure of its interior. A packingP with congruent replicas of a bodyK isn-saturated if non–1 members of it can be replaced withn replicas ofK, and it is completely saturated if it isn-saturated for eachn1. Similarly, a coveringC with congruent replicas of a bodyK isn-reduced if non members of it can be replaced byn–1 replicas ofK without uncovering a portion of the space, and its is completely reduced if it isn-reduced for eachn1. We prove that every bodyK ind-dimensional Euclidean or hyperbolic space admits both ann-saturated packing and ann-reduced covering with replicas ofK. Under some assumptions onKE ^d (somewhat weaker than convexity), we prove the existence of completely saturated packings and completely reduced coverings, but in general, the problem of existence of completely saturated packings, and completely reduced coverings remains unsolved. Also, we investigate some problems related to the the densities ofn-saturated packings andn-reduced coverings. Among other things, we prove that there exists an upper bound for the density of ad+2-reduced covering ofE ^d with congruent balls, and we produce some density bounds for then-saturated packings andn-reduced coverings of the plane with congruent circles.     

On the Number of Cylinders Touching a Ball

In this note we prove an upper bound of seven for the maximum number of unit cylinders touching a unit ball in a packing. This improves a previous bound of eight by Heppers and Szab. The value conjectured by Kuperberg in 1990 is six.     

An Improvement of an Inequality Linking Packing and Covering Densities in 3-space

It is shown that if K is a compact convex set which is centrally symmetric and has a nonempty interior, then the density of the tightest lattice packing with copies of K in Euclidean 3-space divided by the density of the thinnest lattice covering of Euclidean 3-space with copies of K is greater than or equal to 1/3. This improves the previous bound in [5] of 1/4. It is possible this bound will be improved in the future, though not beyond approximately 1/2     

ON THE MINIMUM INTRINSIC 1-VOLUME OF VORONOI CELLS IN LATTICE UNIT SPHERE PACKINGS

A typical 3-dimensional (in short '3D') Voronoi cell of a 3Dlattice has six families of parallel edges. We call any six representants of these six families the generating edges of the Voronoi cell. The sum s of lengths of generating edges of a Voronoi-cell of a lattice unit sphere packing in the 3-dimensional Euclidean space is a special case of intrinsic 1-volumes of 3Dzonotopes with inradius 1 which are investigated accurately in [B]. However, the minimum of this value is unknown even in this special case. As the regular rhombic dodecahedron shows optimal properties in many similar problems, it was reasonable to conjecture that it also has the minimal s value. In this note we present a construction of a lattice unit ball packing whose Voronoi cell possesses an intrinsic 1-volume strictly less than the one of the proper regular rhombic dodecahedron, hence providing a smaller upper bound for s than it was conjectured. A further issue of the note is a formula for edge-lengths of Voronoi cells of lattice unit ball packings that can be used efficiently in similar calculations. This revised version was published online in August 2006 with corrections to the Cover Date.     

Maximum density space packing with parallel strings of spheres

A string of spheres is a sequence of nonoverlapping unit spheres inR ³ whose centers are collinear and such that each sphere is tangent to exactly two other spheres. We prove that if a packing with spheres inR ³ consists of parallel translates of a string of spheres, then the density of the packing is smaller than or equal to . This density is attained in the well-known densest lattice sphere packing. A long-standing conjecture is that this density is maximum among all sphere packings in space, to which our proof can be considered a partial result. The work of A. Bezdek and E. Makai was partially supported by the Hungarian National Foundation for Scientific Research under Grant Number 1238.     

Bounds for Local Density of Sphere Packings and the Kepler Conjecture

This paper formalizes the local density inequality approach to getting upper bounds for sphere packing densities in R ⁿ . This approach was first suggested by L. Fejes Tóth in 1953 as a method to prove the Kepler conjecture that the densest packing of unit spheres in R ³ has density π/\sqrt 18 , which is attained by the ``cannonball packing.' Local density inequalities give upper bounds for the sphere packing density formulated as an optimization problem of a nonlinear function over a compact set in a finite-dimensional Euclidean space. The approaches of Fejes Tóth, of Hsiang, and of Hales to the Kepler conjecture are each based on (different) local density inequalities. Recently Hales, together with Ferguson, has presented extensive details carrying out a modified version of the Hales approach to prove the Kepler conjecture. We describe the particular local density inequality underlying the Hales and Ferguson approach to prove Kepler's conjecture and sketch some features of their proof. Received November 19, 1999, and in revised form April 17, 2001. Online publication December 17, 2001.     

Densest Packings of More than Three d -Spheres Are Nonplanar

We prove that for a densest packing of more than three d -balls, d \geq 3 , where the density is measured by parametric density, the convex hull of their centers is either linear (a sausage) or at least three-dimensional. This is also true for restrictions to lattice packings. These results support the general conjecture that densest sphere packings have extreme dimensions. The proofs require a Lagrange-type theorem from number theory and Minkowski's theory of mixed volumes. Received November 27, 1998, and in revised form January 4, 1999. Online publication May 16, 2000.     

Optimal packings of up to six equal circles on a triangular flat torus

For each n between 1 and 6, we prove that a certain arrangement of n equal circles is the unique optimally dense packing on a standard triangular flat torus (the quotient of the plane by the lattice generated by two unit vectors with a 60^? angle). The packings of 1, 2, 3, 4 and 6 circles are based on either a toroidal triangular close packing or a toroidal triangular close packing with one circle removed. The packing of 5 circles is irregular. This proves two cases of a conjecture stronger than L. Fejes Toth??s conjecture about the strong solidity of the triangular close packing on the plane.     

Packing Cones and Their Negatives in Space

Let C be a cone in R³ whose base B is a planar convex body in a horizontal plane π and whose tip is a point v ∉ π. Let C be a packing formed by translates of C and -C in R³. We exhibit an explicit constant c > 0 such that the density of any such C is smaller than 1 - c, answering a question of Wlodek Kuperberg.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

Traces of Torsion Units

A conjecture due to Zassenhaus asserts that if G is a finite group then any torsion unit in ?G is conjugate in ?G to an element of G. Here, a weaker form of this conjecture is proved for some infinite groups.     

Direct Sum of Distributive Lattices on the Perfect Matchings of a Plane Bipartite Graph

Let G be a plane bipartite graph and M(G){\cal M}(G) the set of perfect matchings of G. A property that the Z-transformation digraph of perfect matchings of G is acyclic implies a partially ordered relation on M(G){\cal M}(G). It was shown that M(G){\cal M}(G) is a distributive lattice if G is (weakly) elementary. Based on the unit decomposition of alternating cycle systems, in this article we show that the poset M(G){\cal M}(G) is direct sum of finite distributive lattices if G is non-weakly elementary; Further, if G is elementary, then the height of distributive lattice M(G){\cal M}(G) equals the diameter of Z-transformation graph, and both quantities have a sharp upper bound é\fracn(n+2)4ù\lceil\frac{n(n+2)}{4}\rceil, where n denotes the number of inner faces of G.     

The Forest Hiding Problem

Let Ω be a disk of radius R in the plane. A set F of unit disks contained in Ω forms a maximal packing if the unit disks are pairwise interior-disjoint and the set is maximal, i.e., it is not possible to add another disk to F while maintaining the packing property. A point p is hidden within the “forest” defined by F if any ray with apex p intersects some disk of F, that is, a person standing at p can hide without being seen from outside the forest. We show that if the radius R of Ω is large enough, one can find a hidden point for any maximal packing of unit disks in Ω. This proves a conjecture of Joseph Mitchell. We also present an O(n ^5/2log n)-time algorithm that, given a forest with n (not necessarily congruent) disks, computes the boundary illumination map of all disks in the forest.     

Double-saturated packing of unit disks

A set of closed unit disks in the Euclidean plane is said to be double-saturated packing if no two disks have inner points in common and any closed unit disk intersects at least two disks of the set. We prove that the density of a double saturated packing of unit disks is ≥ and the lower bound is attained by the family of disks inscribed into the faces of the regular triangular tiling. Partially supported by the Hungarian National Foundation for Scientific Research, grant number 1238.     

On convex bodies that permit packings of high density

It is well known that ann-dimensional convex body permits a lattice packing of density 1 only if it is a centrally symmetric polytope of at most 2(2 ⁿ –1) facets. This article concerns itself with the associated stability problem whether a convex body that permits a packing of high density is in some sense close to such a polytope. Several inequalities that address this stability problem are proved. A corresponding theorem for coverings by two-dimensional convex bodies is also proved.Supported by National Science Foundation Research Grants DMS 8300825 and DMS 8701893.     

Sphere Packing, III. Extremal Cases

This paper is the third in a series of six papers devoted to the proof of the Kepler conjecture, which asserts that no packing of congruent balls in three dimensions has density greater than the face-centered cubic packing. In the previous paper in this series, a continuous function f on a compact space was defined, certain points in the domain were conjectured to give the global maxima, and the relation between this conjecture and the Kepler conjecture was established. This paper shows that those points are indeed local maxima. Various approximations to f are developed, that will be used in subsequent papers to bound the value of the function f. The function f can be expressed as a sum of terms, indexed by regions on a unit sphere. Detailed estimates of the terms corresponding to triangular and quadrilateral regions are developed.     

Compact Packings of the Plane with Two Sizes of Discs

We consider packings of the plane using discs of radius 1 and r. A packing is compact if every disc D is tangent to a sequence of discs D₁, D₂, ..., D_n such that D_i is tangent to D_i+1. We prove that there are only nine values of r with r < 1 for which such packings are possible. For each of the nine values we describe the possible compact packings.