A342222 a(n) is the smallest m such that a regular m-gon with all diagonals drawn contains a cell with n sides, or a(n) = -1 if no such m exists.

3, 6, 5, 9, 7, 13, 9, 29, 11, 40, 13, 43, 15, 212, 17, 231, 19

Offset: 3

Author

Scott R. Shannon and N. J. A. Sloane, Mar 06 2021

Keywords

• nonn
• more

Comments

Theorem: If n is odd then a(n) = n.

Proof. (i) If n is odd then the central cell in a regular n-gon with all diagonals drawn is a smaller regular n-gon. So if n is odd, then a(n) <= n.

(ii) Suppose a convex m-gon, not necessarily regular, with all diagonals drawn has a cell with e edges. Each edge when extended meets two vertices, so at most 2e vertices are involved in defining the boundary of that cell.

On the other hand no vertex can define more than two edges of the cell, so 2e <= 2m, so e <= m. So to get an n-sided cell, we need at least n vertices. So a(n) >= n. QED.

If a(20) > 0 it is greater than 765 - Scott R. Shannon, Nov 30 2021

Examples

			Examining the images in A007678, for example Michael Rubinstein's illustration, or the images shown here, we see that the first occurrence of a five-sided cell is for m = 5, so a(5) = 5. The first time we see a four-sided cell is for m = 6, so a(4) = 6.
		

Links

• Martin Balko, Anna Brötzner, Fabian Klute, and Josef Tkadlec, Faces in Rectilinear Drawings of Complete Graphs, 40th European Workshop on Computational Geometry, Ioannina, Greece, March 13-15, 2024. See pp. 4, 7.
• Scott R. Shannon, Image for a(3) = 3.
• Scott R. Shannon, Image for a(4) = 6.
• Scott R. Shannon, Image for a(5) = 5.
• Scott R. Shannon, Image for a(6) = a(9) = 9.
• Scott R. Shannon, Image for a(7) = 7.
• Scott R. Shannon, Image for a(8) = a(13) = 13.
• Scott R. Shannon, Image for a(10) = 29.
• Scott R. Shannon, Image for a(11) = 11.
• Scott R. Shannon, Image for a(12) = 40.
• Scott R. Shannon, Image for a(14) = 43.
• Scott R. Shannon, Image for a(15) = 15.

Crossrefs

Cf. A007678, A331450, A331451, A007569, A135565.

See also A341729 and A341730 for the maximum number of sides in any cell.

Extensions

a(16)-a(19) added by Scott R. Shannon, Mar 14 2021