Packing and Covering with Centrally Symmetric Convex Disks

Given a convex disk K (a convex compact planar set with nonempty interior), let δ _L (K) and θ _L (K) denote the lattice packing density and the lattice covering density of K, respectively. We prove that for every centrally-symmetric convex disk K we have that $$ 1\le\delta_L(K)\theta_L(K)\le1.17225\ldots $$ The left inequality is tight and it improves a 10-year old result.     

Covering the plane with copies of a convex disk

We prove that for every convex disk in the plane there exists a double-lattice covering of the plane with copies of with density ≤ 1.2281772 . This improves the best previously known upper bound ≤ 8/(3+2\sqrt{3}) 1.2376043 , due to Kuperberg, but it is still far from the conjectured value . <lsiheader> <onlinepub>7 August, 1998 <editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt; <pdfname>20n2p251.pdf <pdfexist>yes <htmlexist>no <htmlfexist>no <texexist>no <sectionname> </lsiheader> Received June 1, 1996, and in revised form January 24, 1997.     

On the Chromatic Number of \mathbb {R}^4

The lower bound for the chromatic number of \(\mathbb {R}^4\) is improved from \(7\) to \(9\) . Three graphs with unit distance embeddings in \(\mathbb {R}^4\) are described. The first is a \(7\) -chromatic graph of order \(14\) whose chromatic number can be verified by inspection. The second is an \(8\) -chromatic graph of order \(26\) . In this case the chromatic number can be verified quickly by a simple computer program. The third graph is a \(9\) -chromatic graph of order \(65\) for which computer verification takes about one minute.     

On Sequences of Nested Triangles

Summary For a given triangle, we consider several sequences of nested triangles obtained via iterative procedures. We are interested in the limiting behavior of these sequences. We briefly mention the relevant known results and prove that the triangle determined by the feet of the angle bisectors converges in shape towards an equilateral one. This solves a problem raised by Trimble~[5].     

Minimizer graphs for a class of extremal problems

We consider the family of graphs with a fixed number of vertices and edges. Among all these graphs, we are looking for those minimizing the sum of the square roots of the vertex degrees. We prove that there is a unique such graph, which consists of the largest possible complete subgraph plus only one other non‐isolated vertex. The same result is proven for any power of the vertex‐degrees less than one half. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 230–240, 2002; DOI 10.1002/jgt.10025     

Restricted Point Configurations with Many Collinear {k}-Tuplets

   Abstract. Given k≥ 3 , denote by t' _k (N) the largest integer for which there is a set of N points in the plane, no k+1 of them on a line such that there are t' _k (N) lines, each containing exactly k of the points. Erdos (1962) raised the problem of estimating the order of magnitude of t' _k (N) . We prove that

A dense planar point set from iterated line intersections

Given S₁, a starting set of points in the plane, not all on a line, we define a sequence of planar point sets {S_i}_i=1^∞ as follows. With S_i already determined, let L_i be the set of all the lines determined by pairs of points from S_i, and let S_i+1 be the set of all the intersection points of lines in L_i. We show that with the exception of some very particular starting configurations, the limiting point set _i=1^∞S_i is everywhere dense in the plane.     

Slicing the Pie

Given a circular unit disc and n lines such that any two of them intersect inside the disc, we show that there exists a cell of area at least /4n.     

Illuminating a convex polygon with vertex lights

We prove that the interior of every convex polygon with n vertices (n ≥ 4) can be illuminated by four 45°-vertex lights. We restrict each vertex to anchoring at most one floodlight. This answers a question of O’Rourke, Shermer and Streinu [5].