On the construction of convex $n$-gons with convex $(n-k)$-gons

Question

I am trying to determine how many convex $(n-k)$-gons, with their vertices in general position and such that at most they pairwise intersect in one vertex, guarantee that we can construct a convex $n$-gon using only the vertices of the convex $(n-k)$-gons.

I would like to know if there are some known results, literature in the subject, or some useful lemmas and theorems that you could share to help me.

Thanks in advance!

EDIT

An example of what I mean for $n=4$ would be to ask how many triangles (convex $(4-1)$-gons) such that their vertices are points in general position (no more than two in the same line) and such that at most they pairwise interesect in one vertex, guarantee that we can construct some convex cuadrilateral using only the vertices of the triangles.

In this regard, it is easy to show that two triangles guarantee that we can construct some convex cuadrilateral, as five points in general position guarantee the construction of some convex cuadrilateral (as proved in the context of the the happy ending problem).

Indeed, the question is somewhat related to this last problem, adding the constraint of local independent convexities to the points in general position.

Answer 1

This is a partial answer.

This answer proves the following two claims :

Let $g(n,n-k)$ be our number. (For example, one has $g(4,3)=2$ which you've already pointed out.)

Claim 1 : $g(5,4)=3$.

Claim 2 : For $n\geqslant 5$, $g(n,3)\geqslant n+1$.

---

Claim 1 : $g(5,4)=3$.

Proof :

According to the Happy ending problem (Wikipedia), one has $f(5)=9$ where $f(N)$ is the minimum $M$ for which any set of $M$ points in general position must contain a convex $N$-gon. Therefore, $g(5,4)=3$ follows.$\quad\blacksquare$

---

Claim 2 : For $n\geqslant 5$, $g(n,3)\geqslant n+1$.

Proof :

Using the first figure in Juan Moreno's answer, one can see that five triangles ($ABE$, $EFH$, $CGH$, $BFC$, $ACD$) do not guarantee the construction of some convex pentagon. This implies that $g(5,3)\geqslant 6$. Next, using the second figure, one can see that six triangles ($ABF$, $FGI$, $CHI$, $BGC$, $ACD$, $EDJ$) do not guarantee the construction of some convex hexagon where the way of the construction of the first five triangles is the same as the one used in the first figure. Using this idea inductively, one can see that for $n\geqslant 5$, $g(n,3)\geqslant n+1$.$\quad\blacksquare$

Answer 2

This is just a partial answer, to show that, if we denote as $g(n, n-k)$ the number of convex $(n−k)$-gons, with their vertices in general position and such that at most they pairwise intersect in one vertex, that guarantee that we can construct a convex $n$-gon using only the vertices of the convex $(n−k)$-gons, we can state that, for $n\geq 5$ $$3\leq g(n, n-1)$$

As stated in the OP, two triangles guarantee the construction of some quadrilateral. However, we can have two quadrilaterals that do not guarantee the construction of a convex pentagon as follows:

We can have two pentagons that do not guarantee the construction of a convex hexagon as follows:

It is easy to see that, generalizing this method of construction opposing the convex hulls of the two polygons for every convex $n$-gon, we can have two convex $n$-gons such that they do not guarantee the construction of a convex $(n+1)$-gon. Therefore, for $n\geq 5$ $$3\leq g(n, n-1)$$

Erdös-Szekeres conjecture, if true, would set the upper bound $g(n, n-1)\leq \lceil\frac{2^{n-2}+1}{n-1}\rceil$; however, I conjecture that the true upper bound must be much lower.

Answer 3

Working on the lower bounds, using the figures of my previous answer, I have the following

Conjecture: $g(n,4) \geq n-2$

Bases of the conjecture:

From two pentagons there can be drawn three quadrilaterals as showed in the picture, so $g(6,4)\geq 4$:

From two hexagons there can be drawn four quadrilaterals as showed in the picture, so $g(7,4) \geq 5$:

From two heptagons, there can be drawn five quadrilaterals as showed in the picture, so $g(8,4) \geq 6$:

From two octogons, there can be drawn six quadrilaterals as showed in the picture, so $g(9,4) \geq 7$:

From two nonagons, there can be drawn seven quadrilaterals as showed in the picture, so $g(10,4) \geq 8$:

There is enough evidence of a pattern of construction, but as it is not as clear as for the proof of the lower bound for $g(n,3)$ provided by mathlove, it is not so clear to me that we can inductively conclude that $g(n,4) \geq n-2$.