Maximal number of edges and triangular cells for n points in a triangular lattice - MathOverflow

Maximal number of edges and triangular cells for n points in a triangular lattice

2011-08-25T01:39:08Z

Consider a subset of $n$ points in an equilateral triangular lattice. Draw all the edges between nearest-neighbor points.

What is the maximum, over all such subsets, of the number of edges? This sequence appears to start 0, 1, 3, 5, 7, 9, 12, 14, 16...

What is the maximum number of triangular lattice cells? (Not the number of all triangles, just the number of smallest possible equilateral triangles in the lattice.) This sequence appears to start 0, 0, 1, 2, 3, 4, 6, 7, 8, 10, 11, 13...

http://oeis.org/A047932 is related to the first sequence but I have no proof it's the same. (There might be some other way of arranging the pennies that yields a higher number of contacts. A047932 is a lower bound on my sequence.) I can't find any OEIS sequences relevant to the second one.

Answer by Noam D. Elkies for Maximal number of edges and triangular cells for n points in a triangular lattice

2011-08-25T02:43:45Z

You might have noticed that the difference between your two sequences is $0,1,2,3,4,5,6,7,8,\ldots$ and that the optimal configurations seem to be the same for both problems.

This is true in general, and is a nice application of Euler's formula $V-E+F=2$. (NB this requires showing that in an optimal configuration the edges form a connected component.) Here $V=n$, the number of edges is $E$, and the number of triangles, call it $t$, is $F-1$ because we must count the exterior of the graph as a face. So the difference between the edge and triangle maxima is $(n-1)$ — at least assuming we can prove it's never to our advantage in either problem to have holes bigger than a unit triangle in the picture, which seems clear but may be annoying to prove rigorously. [EDIT see below on this point.]

Another standard graph-theory formula that applies here: the sum of all the faces' edge-counts is $2E$. [Proof: count in two ways the pairs $(e,f)$ where $f$ is a face and $e$ is one of its edges.] In our setting all but one of the faces has $3$ edges, so $2E=3t+p$ where $p$ (for perimeter) is the number of outside edges (counting an edge twice if both sides abut the infinite face, as happens for $n=2$, and again assuming no internal holes). So $t+2 = 2n-p$, and the problem comes down to minimizing $t$. It certainly looks plausible that the "penny spiral" does this, but it's getting late so I'll leave it as an exercise :-) This would identify your first sequence with OEIS A047932, and thus determine the second sequence as well.

UPDATE Denote the sequences in question by $s_1(n)$ and $s_2(n)$ respectively. As pointed out in G.Zaimi's accepted answer, the formula $s_1(n) = \lfloor 3n-\sqrt{12n-3}\rfloor$, consistent with the original proposer's guess/question, follows from a much more general result of Harbroth that this is the maximal number of times that the minimum distance can occur in any configuration of $n$ points in the plane. I looked up the solution (which is freely available online), and it seems to use ultimately the same technique: see the reference to the "Eulerschen Polyedersatz" before equation (3). Using the Euler "Polyedersatz" we also deduce $$s_2(n) = s_1(n) - (n-1) = \lfloor 2n-\sqrt{12n-3}+1\rfloor,$$ answering the second question. Indeed Euler says that $s_2(n) \leq s_1(n) - (n-1)$ with equality iff there's an optimal configuration without holes bigger than a unit triangle; and Harbroth's solution gives such a configuration.

Answer by Gjergji Zaimi for Maximal number of edges and triangular cells for n points in a triangular lattice

2011-08-25T03:13:39Z

The following was conjectured by D. Reutter in problem 664A, Elemente der mathematik 27 and proved by H. Harborth in Solution to problem 664A, Elemente der mathematik 29, 14-15

The maximum number of times the minimum distance can occur among $n$ points in the plane is $\lfloor 3n-\sqrt{12n-3}\rfloor$.

This is achieved by a hexagonal piece in the triangular lattice, i.e. from points forming a hexagonal spiral. In particular, this gives a formula for your first sequence.