Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Question

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.

Answer 1

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.

Answer 2

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\}$.