%I #63 Mar 10 2024 09:34:02
%S 3,6,5,9,7,13,9,29,11,40,13,43,15,212,17,231,19
%N 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.
%C Theorem: If n is odd then a(n) = n.
%C 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.
%C (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.
%C 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.
%C If a(20) > 0 it is greater than 765 - _Scott R. Shannon_, Nov 30 2021
%H Martin Balko, Anna Brötzner, Fabian Klute, and Josef Tkadlec, <a href="https://eurocg2024.math.uoi.gr/data/uploads/paper_08.pdf">Faces in Rectilinear Drawings of Complete Graphs</a>, 40th European Workshop on Computational Geometry, Ioannina, Greece, March 13-15, 2024. See pp. 4, 7.
%H Scott R. Shannon, <a href="/A342222/a342222.gif">Image for a(3) = 3</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_1.gif">Image for a(4) = 6</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_2.gif">Image for a(5) = 5</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_3.gif">Image for a(6) = a(9) = 9</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_4.gif">Image for a(7) = 7</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_5.gif">Image for a(8) = a(13) = 13</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_6.gif">Image for a(10) = 29</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_7.gif">Image for a(11) = 11</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_8.gif">Image for a(12) = 40</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_9.gif">Image for a(14) = 43</a>.
%H Scott R. Shannon, <a href="/A342222/a342222_10.gif">Image for a(15) = 15</a>.
%e 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.
%Y Cf. A007678, A331450, A331451, A007569, A135565.
%Y See also A341729 and A341730 for the maximum number of sides in any cell.
%K nonn,more
%O 3,1
%A _Scott R. Shannon_ and _N. J. A. Sloane_, Mar 06 2021
%E a(16)-a(19) added by _Scott R. Shannon_, Mar 14 2021
|