On the Density of 2-Saturated Lattice Packings of Discs

 In a recent paper of G. Fejes Tóth, G. Kuperberg and W. Kuperberg [1] a conjecture has been published concerning the greatest lower bound of the density of a 2-saturated packing of unit discs in the plane. (A packing of unit discs is said to be 2-saturated if none of the discs could be replaced by two other ones of the same size to generate a new packing. A packing of the unit disc is a lattice packing if the centers form a point lattice.) In the present note we study this problem for lattice packings, however, in a more general form in which the removed unit disc is replaced by two discs of radius r. A corollary of our results supports the above conjecture proving that a lattice packing cannot be 2-saturated except if its density is larger than the conjectured bound. (Received 6 December 2000; in revised form March 29, 2001)     

Contact graphs of unit sphere packings revisited

The contact graph of an arbitrary finite packing of unit balls in Euclidean 3-space is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of a packing of n unit balls can have. In this paper, improving earlier estimates, we prove that the number of touching pairs in an arbitrary packing of n unit balls in ${\mathbb{E}^{3}}$ is always less than ${6n - 0.926n^{\frac{2}{3}}}$ . Moreover, as a natural extension of the above problem, we propose to study the maximum number of touching triplets (resp., quadruples) in an arbitrary packing of n unit balls in Euclidean 3-space. In particular, we prove that the number of touching triplets (resp., quadruples) in an arbitrary packing of n unit balls in ${\mathbb{E}^3}$ is at most ${\frac{25}{3}n}$ (resp., ${\frac{11}{4}n}$ ).     

Contact Numbers for Congruent Sphere Packings in Euclidean 3-Space

The contact graph of an arbitrary finite packing of unit balls in Euclidean 3-space is the (simple) graph whose vertices correspond to the packing elements and whose two vertices are connected by an edge if the corresponding two packing elements touch each other. One of the most basic questions on contact graphs is to find the maximum number of edges that a contact graph of a packing of n unit balls can have. Our method for finding lower and upper estimates for the largest contact numbers is a combination of analytic and combinatorial ideas and it is also based on some recent results on sphere packings. In particular, we prove that if C(n) denotes the largest number of touching pairs in a packing of n>1 congruent balls in Euclidean 3-space, then $0.695<\frac{6n-C(n)}{n^{\frac{2}{3}}}< \sqrt[3]{486}=7.862\dots$ for all $n=\frac{k(2k^{2}+1)}{3}$ with k??2.     

Wegner Estimate for Discrete Alloy-type Models

We study discrete alloy-type random Schrödinger operators on ${\ell^2(\mathbb{Z}^d)}We study discrete alloy-type random Schr?dinger operators on l²(\mathbbZ^d){\ell^2(\mathbb{Z}^d)} . Wegner estimates are bounds on the average number of eigenvalues in an energy interval of finite box restrictions of these types of operators. If the single site potential is compactly supported and the distribution of the coupling constant is of bounded variation a Wegner estimate holds. The bound is polynomial in the volume of the box and thus applicable as an ingredient for a localisation proof via multiscale analysis.     

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.     

Rigidity Theorem for Hypersurfaces in a Unit Sphere

By investigating hypersurfaces M ⁿ in the unit sphere S ⁿ⁺¹(1) with H _k = 0 and with two distinct principal curvatures, we give a characterization of torus the . We extend recent results of Perdomo [9], Wang [10] and Otsuki [8].     

Dual Toeplitz Operators on the Sphere Via Spherical Isometries

We solve a characterization problem for dual Hardy-space Toeplitz operators on the unit sphere \({\mathbb{S}_{n}}\) in \({\mathbb{C}^{n}}\) posed by Guediri (Acta Math Sin (English series) 29(9):1791–1808, 2013). Our proof relies on the observation that dual Toeplitz operators on the orthogonal complement \({H^{2}(\mathbb{S}_{n})^{\bot}}\) of the Hardy space in L ² can be viewed as Toeplitz operators with respect to a suitable spherical isometry. This correspondence also allows us to determine the commutator ideal of the dual Toeplitz C ^*-algebra.     

Multiple lattice packings and coverings of spheres

Let be a lattice inR ⁿ . Consider the systemS of unit spheres centered at the lattice points of .S is called ak-fold lattice packing (covering) if each point inR ⁿ lies in at most (least)k of the open (closed) spheres ofS. Letd _k ⁿ (D _k ⁿ ) be the density of the closest (thinnest)k-fold lattice packing (covering) ofR ⁿ . After dealing several cases left by G. Fejes Tóth and A. Florian, we have concluded thatd _k ⁿ >kd ₁ ⁿ for all (n, k) (n2,k2) except (2, 2), (2, 3), (2, 4); andD _k ³ <k D ₁ ³ for allk2.     

Line Transversals in Large <Emphasis Type="Italic">T</Emphasis>(3)- and <Emphasis Type="Italic">T</Emphasis>(4)-Families of Congruent Discs

A family of closed discs is said to have property T(k) if to every subset of at most k discs there belongs a common line transversal. A family of discs is said to be d-disjoint, d≥1, if the mutual distance between the centers of the discs is larger than d. It is known that a d-disjoint T(3)-family ℱ of unit diameter discs has a line transversal if . Similarly, a d-disjoint T(4)-family has a line transversal if . Both results are sharp in d, i.e., they do not hold for smaller values of d. The main result of this paper is that while the above lower bounds on d cannot be relaxed in general, some reduction of d can be compensated by imposing a proper d-dependent lower bound on the size of the family in both cases.     

A Note on Toeplitz Operators in Schatten-Herz Classes Associated with Rearrangement-invariant Spaces

In recent papers, B. Choe, H. Koo, K. Na (see [3]) and Loaiza, M. Lopez-Garcia e S. Perez-Esteva (see [5]) studied conditions in order to a Toeplitz operator, acting on the harmonic Bergman space over the unit ball in and on analytic Bergman space on the unit disk in the complex plane, respectively, belong to the so-called Schaten-Herz class. The purpose of this note is to prove necessary and sufficient conditions in order to a Toeplitz operator T _μ with positive symbol, acting on the harmonic Bergman space on the unit ball in belong to a Schatten-Herz class S ^F _E , associated with a pair of rearrangement invariant sequence spaces E and F. The conditions involve the Berezin transform of its symbol and the average function. on some euclidian discs. The main point is the characterization of Toeplitz operators, that belong to Schatten ideals S _E associated with an arbitrary rearrangement invariant sequence space E.      

An Alternate Characterization of the Bentness of Binary Functions, with Uniqueness

In a previous paper, we have obtained a characterization of the binary bent functions on (GF(2))ⁿ (n even) as linear combinations modulo , with integral coefficients, of characteristic functions (indicators) of -dimensional vector-subspaces of (GF(2))ⁿ. There is no uniqueness of the representation of a given bent function related to this characterization. We obtain now a new characterization for which there is uniqueness of the representation.     

Improving Rogers' Upper Bound for the Density of Unit Ball Packings via Estimating the Surface Area of Voronoi Cells from Below in Euclidean \sl d -Space for All \sl d ≥ \bf 8

   Abstract. The sphere packing problem asks for the densest packing of unit balls in E ^d . This problem has its roots in geometry, number theory and information theory and it is part of Hilbert's 18th problem. One of the most attractive results on the sphere packing problem was proved by Rogers in 1958. It can be phrased as follows. Take a regular d -dimensional simplex of edge length 2 in E ^d and then draw a d -dimensional unit ball around each vertex of the simplex. Let σ _d denote the ratio of the volume of the portion of the simplex covered by balls to the volume of the simplex. Then the volume of any Voronoi cell in a packing of unit balls in E ^d is at least ω _d /σ _d , where ω _d denotes the volume of a d -dimensional unit ball. This has the immediate corollary that the density of any unit ball packing in E ^d is at most σ _d . In 1978 Kabatjanskii and Levenštein improved this bound for large d . In fact, Rogers' bound is the presently known best bound for 4≤ d≤ 42 , and above that the Kabatjanskii—Levenštein bound takes over. In this paper we improve Rogers' upper bound for the density of unit ball packings in Euclidean d -space for all d≥ 8 and improve the Kabatjanskii—Levenštein upper bound in small dimensions. Namely, we show that the volume of any Voronoi cell in a packing of unit balls in E ^d , d≥ 8 , is at least ω _d /

The plane‐width of graphs

Map the vertices of a graph to (not necessarily distinct) points of the plane so that two adjacent vertices are mapped at least unit distance apart. The plane‐width of a graph is the minimum diameter of the image of its vertex set over all such mappings. We establish a relation between the plane‐width of a graph and its chromatic number. We also connect it to other well‐known areas, including the circular chromatic number and the problem of packing unit discs in the plane. © 2011 Wiley Periodicals, Inc. J Graph Theory 68: 229‐245, 2011     

Expected wasted space of optimal simple rectangle packing

A simple packing of a collection of rectangles contained in [0,1]² is a disjoint subcollection such that each vertical line meets at most one rectangle of the packing. The wasted space of the packing is the surface of the area of the part of [0,1]² not covered by the packing. We prove that for a certain number L, for all N2, the wasted space W_N in an optimal simple packing of N independent uniformly distributed rectangles satisfiesWork partially supported by an N.S.F. grant.Mathematics Subject Classification (2000): 60D05     

Complete Hypersurfaces with Constant Mean Curvature in a Unit Sphere

By investigating hypersurfaces M ⁿ in the unit sphere S ⁿ⁺¹(1) with constant mean curvature and with two distinct principal curvatures, we give a characterization of the torus S ¹(a) × , where . We extend recent results of Hasanis et al. [5] and Otsuki [10].     

Packing random intervals

Summary Letn random intervalsI ₁, ...,I _n be chosen by selecting endpoints independently from the uniform distribution on [0.1]. Apacking is a pairwise disjoint subset of the intervals; itswasted space is the Lebesgue measure of the points of [0,1] not covered by the packing. In any set of intervals the packing with least wasted space is computationally easy to find; but its expected wasted space in the random case is not obvious. We show that with high probability for largen, this best packing has wasted space . It turns out that if the endpoints 0 and 1 are identified, so that the problem is now one of packing random arcs in a unit-circumference circle, then optimal wasted space is reduced toO(1/n). Interestingly, there is a striking difference between thesizes of the best packings: about logn intervals in the unit interval case, but usually only one or two arcs in the circle case.     

Congruence by Dissection of Topological Discs—An Elementary Approach to Tarski's Circle Squaring Problem

Let G be a group of affine transformations of the plane R ² and let the family F consist of all topological discs in R ² whose boundary is subject to some smoothness condition (general, rectifiable, piecewise C ¹ , piecewise C ² ). Are any two members D,E ∈ F congruent by dissection with respect to G such that all the pieces in the corresponding dissections of D and E belong to F as well? We give an affirmative answer if G contains all affine transformations and F consists of the discs whose boundary is piecewise C ¹ . An example shows that C ¹ cannot be replaced by C ² . Moreover, if G is either the group of equiaffine transformations or the group of similarities, then congruence by dissection of two convex discs D and E turns out to be essentially equivalent to congruence by dissection of the boundaries bd(D ) and bd(E ).     

Spacing properties of the zeros of orthogonal polynomials on Cantor sets via a sequence of polynomial mappings

Let \({\varepsilon}\) be a (small) positive number. A packing of unit balls in \({{\mathbb{E}^{3}}}\) is said to be an \({\varepsilon}\)-quasi-twelve-neighbour packing if no two balls of the packing touch each other but for each unit ball B of the packing there are twelve other balls in the packing with the property that the distance of the centre of each of these twelve balls from the centre of B is smaller than \({2+\varepsilon}\). We construct \({\varepsilon}\)-quasi-twelve-neighbour packings of unit balls in \({{\mathbb{E}^{3}}}\) for arbitrary small positive \({\varepsilon}\) with some surprising properties.     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

A generalized Macaulay theorem and generalized face rings

We prove that the f-vector of members in a certain class of meet semi-lattices satisfies Macaulay inequalities 0?k^∂(fk)?fk−1 for all k?0. We construct a large family of meet semi-lattices belonging to this class, which includes all posets of multicomplexes, as well as meet semi-lattices with the “diamond property,” discussed by Wegner [G. Wegner, Kruskal-Katona's theorem in generalized complexes, in: Finite and Infinite Sets, vol. 2, in: Colloq. Math. Soc. János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 821-828], as special cases. Specializing the proof to the later family, one obtains the Kruskal-Katona inequalities and their proof as in [G. Wegner, Kruskal-Katona's theorem in generalized complexes, in: Finite and Infinite Sets, vol. 2, in: Colloq. Math. Soc. János Bolyai, vol. 37, North-Holland, Amsterdam, 1984, pp. 821-828].For geometric meet semi-lattices we construct an analogue of the exterior face ring, generalizing the classic construction for simplicial complexes. For a more general class, which also includes multicomplexes, we construct an analogue of the Stanley-Reisner ring. These two constructions provide algebraic counterparts (and thus also algebraic proofs) of Kruskal-Katona's and Macaulay's inequalities for these classes, respectively.