9
$\begingroup$

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$). Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges of $m$ convex sub-polygons of $P$ which do not share any edges.

($Q$ is a sub-polygon of $P$ if all vertices of $Q$ are vertices of $P$).

This question was proposed at a Chinese contest and maybe it's a known result in graph theory.

For $n=5$, for example, it's not hard to see that $m(5)=3$. If $P:=P_{1}P_{2}P_{3}P_{4}P_{5}$, $m(5)=3$ can be achieved by 3 convex sub-polygons: $P_{1}P_{2}P_{4}P_{5}$; $P_{1}P_{3}P_{4}$; $P_{2}P_{3}P_{5}$. I also found that $m(7) \leq 6$, but I couldn't go further.

Any suggestion would be appreciated. Thanks in advance.

$\endgroup$
  • $\begingroup$ If it is a contest problem, maybe you may ask organizers or participants of the contest? $\endgroup$ – Fedor Petrov Jul 18 '15 at 15:42
  • $\begingroup$ @FedorPetrov Unfortunately this one took place in the early 90s. I'm not aware of any organizer/participant of this contest. $\endgroup$ – jack Jul 18 '15 at 15:58
  • $\begingroup$ Must $m\lt n$ hold, or is $m\le n$ also possible? $\endgroup$ – Manfred Weis Jul 19 '15 at 7:45
  • $\begingroup$ @ManfredWeis There are no restrictions on $m$, except it has to be the smallest possible. So $m \leq n$ is also possible. $\endgroup$ – jack Jul 19 '15 at 14:57
  • $\begingroup$ I deleted my comment because I thought diagonals were also not to be shared. However, I thought a sub-polygon of a convex polygon was also convex (I guess vertex order matters?). There may still be a design interpretation, but my original one does not quite capture the problem. Gerhard "Thinks This Still Isn't Geometry" Paseman, 2015.07.19 $\endgroup$ – Gerhard Paseman Jul 19 '15 at 23:15
8
$\begingroup$

Here's a lower bound that heynongman and I worked out. (This was previously posted with equality, but there was a flaw in the argument.) This is assuming that the diagonals (as well as the edges) of $P$ are not to be shared among the sub-polygons.

Suppose that the edges and diagonals of $P$ can be covered by $m$ convex sub-polygons $Q_1$, $Q_2$, ..., $Q_m$, having $a_1$, $a_2$, ..., $a_m$ edges, respectively. We want to cover $n\choose2$ edges and diagonals in all, so

$$a_1+a_2+\cdots+a_m={n\choose2}.\tag{1}$$

We define the cost $c(e)$ of an edge $e$ of $P$ (around the perimeter) to be 0, and the cost $c(e)$ of a diagonal $e$ to be the smallest number of intermediate vertices of $P$ in a path along the perimeter of $P$ from one endpoint to the other. For example, for $n=7$ and $P=P_1P_2P_3P_4P_5P_6P_7$, the cost of the diagonal $P_2P_6$ is 2 (because the shortest path around the perimeter between the endpoints is $P_6P_7P_1P_2$, which has two intermediate vertices). Intuitively, the cost of a diagonal is the minimum number of vertices of $P$ that must be "skipped" by a sub-polygon $Q_i$ that uses that diagonal, traversing the vertices of $Q_i$ clockwise.

The maximum cost of a diagonal is $(n-3)/2$. At each vertex, because $n$ is odd, there are exactly two diagonals of each cost from 1 to $(n-3)/2$, so the total cost of diagonals incident upon a given vertex is $2\sum_{i=1}^{(n-3)/2}i=(n-1)(n-3)/4$. If we sum over all vertices, we count the cost of each diagonal twice, so the sum of the costs of all edges and diagonals of $P$ is

$$ \sum_{e\in P}c(e)={n\over2}\left[(n-1)(n-3)\over4\right]. $$

Now, for any sub-polygon $Q_i$, every vertex of $P$ is either a vertex of $Q_i$ or is "skipped" by $Q_i$. The total cost of the edges of $Q_i$, $\sum_{e\in Q_i}c(e)$, is a lower bound on the number $n-a_i$ of "skipped" vertices, which is to say that $n-a_i\ge\sum_{e\in Q_i}c(e)$. (Our previous post claimed that $\sum_{e\in Q_i}c(e)=n-a_i$, but this is not necessarily true, because a sub-polygon may lie entirely in "one half" of $P$.) Therefore,

$$(n-a_1)+(n-a_2)+\cdots+(n-a_m)\ge\sum_{i=1}^m\sum_{e\in Q_i}c(e)=\sum_{e\in P}c(e)={n(n-1)(n-3)\over8}.\tag{2}$$

Adding (1) and (2), we get

$$mn\ge{n\choose2}+{n(n-1)(n-3)\over8}={n(n-1)(n+1)\over8},$$

so $m\ge(n-1)(n+1)/8$.

This lower bound gives $m(5)\ge3$, $m(7)\ge6$, and $m(9)\ge10$. We have constructions that meet this bound for $n=5,7,9$, but we don't have a general construction.

$\endgroup$
2
$\begingroup$

I think the following construction realizes the lower bound in Brian's answer. Let $n=2k+1$ and label the first $2k$ vertices with $\mathbb{Z}_{2k}=\{0,\ldots,2k-1\}$ and the last vertex with $\infty$. First we take all the $(n-1)(n-3)/8=2k(k-1)/4$ 4-gons of the form \[(i,\,i+j,\,i+k,\,i+k+j)\] with $i\in\{0,\ldots,2k-1\}$ and $j\in\{1,\ldots,k-1\}$. That covers everything not involving $\infty$ except the "long" diagonals $(i,i+k)$, so we add $(n-1)/2=k$ triangles $(i,i+k,\infty)$ for $i\in\{0,\ldots,k-1\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.