# A new polygon forcing theorem

I have found a way to enlarged the Erdos-Szekeres Conjecture. I have computationally confirmed what might be the simplest unknown case for some small values, and was reaching out for how to prove this case in general.

Definitions Given a set of points in the general position on the plane, a subset is a "convex polygon" if each point is a vertex of the subset's convex hull. A cap is a sequence of points with increasing $x$-coordinate such that the slope of consecutive pairs is decreasing. A cup is defined similarly but the slopes are increasing. A $n$-polygon (size $n$ convex polygon) can be decomposed into a $k$-cap and an $k'$-cup where $k' = n + 2 - k$. We refer to this as a $(k, k')$-polygon.

For example in the image below, the yellow and red points form a $4$-cap, the yellow and green form $6$-cup, collectively the red, yellow, and green points form both a $(4, 6)$-polygon and a $8$-polygon.

Erdos-Szekeres Conjecture The tooling in the next section are used to generalize the following famous conjecture. If a set contains $2^{n-2}+1$ points in the general position on the plane, does it contain an $n$-polygon?

Polygon Forcing Theorems Define $C(X; k, k')$ to be true if and only the set of points $X$ contain a $(k, k')$-polygon. We define a forced polygon theorem is one of the form $$|X| > N \implies \bigcup_i C(X; k_i, k_i')$$ We now show some results and problems that are forced polygon theorems. If the Erdos-Szekeres Conjecture is correct then $$|X| > 2^{n-2} \implies \bigcup_{i = 2}^{n} C(X; i, n+2-i)$$ Another example, Erdos and Szekeres show that $$|X| > \binom{k + k' - 4}{k - 2} \implies C(X; 2, k') \cup C(X; k, 2)$$ which they use to provide an upper bound to their problem. See "A Combinatorial Problem in Geometry" by Erdos and Szekeres. And in "Ramsey-remainder", by Erdos, Tuza, and Valtr showed that the Erdos-Szekeres conjecture is equivalent to $$|X| > \sum_{i = n - k'}^{k-2} \binom{n - 2}{i} \implies C(X; k, 2) \cup C(X; 2, k') \cup \bigcup_{i = n+2 - (k'-1)}^{k-1} C(X; i, n+2-i)$$ And when $k, k' = n$ they are equal.

My Problem I have found a computational technique for creating polygon forcing theorems. Using it I have observed for all $k$ and $k'$ in cases when the program halts:

$$|X| > \frac{(k-1) (k'-1)}{2} \implies C(X; 2, k') \cup C(X; 3, 3) \cup C(X; k, 2)$$

I suspect there is a labeling argument similar to another related problem but I haven't be able to find it and was wondering if I could have help. Thank you for reading this post, as it is quite long.

Edit

Here are all the cases I can compute, in case someone can come up with a comprehensive conjecture. Note that these are upper bounds: If 21 -> [(2, 7), (3, 3), (8, 2)] it is still possible that 20 -> [(2, 7), (3, 3), (8, 2)]. I am curious if there are better bounds for any of these cases.

2 -> [(2, 3), (3, 2)]
3 -> [(2, 3), (4, 2)]
4 -> [(2, 3), (5, 2)]
5 -> [(2, 3), (6, 2)]
3 -> [(2, 4), (3, 2)]
6 -> [(2, 4), (4, 2)]
10 -> [(2, 4), (5, 2)]
15 -> [(2, 4), (6, 2)]
4 -> [(2, 5), (3, 2)]
10 -> [(2, 5), (4, 2)]
20 -> [(2, 5), (5, 2)]
5 -> [(2, 6), (3, 2)]
15 -> [(2, 6), (4, 2)]
4 -> [(2, 4), (3, 3), (4, 2)]
6 -> [(2, 4), (3, 3), (5, 2)]
7 -> [(2, 4), (3, 3), (6, 2)]
7 -> [(2, 4), (4, 3), (5, 2)]
9 -> [(2, 4), (4, 3), (6, 2)]
11 -> [(2, 4), (5, 3), (6, 2)]
6 -> [(2, 5), (3, 3), (4, 2)]
8 -> [(2, 5), (3, 3), (5, 2)]
10 -> [(2, 5), (3, 3), (6, 2)]
7 -> [(2, 5), (3, 4), (4, 2)]
12 -> [(2, 5), (3, 4), (5, 2)]
17 -> [(2, 5), (3, 4), (6, 2)]
12 -> [(2, 5), (4, 3), (5, 2)]
14 -> [(2, 5), (4, 3), (6, 2)]
14 -> [(2, 5), (4, 4), (5, 2)]
7 -> [(2, 6), (3, 3), (4, 2)]
10 -> [(2, 6), (3, 3), (5, 2)]
12 -> [(2, 6), (3, 3), (6, 2)]
9 -> [(2, 6), (3, 4), (4, 2)]
14 -> [(2, 6), (3, 4), (5, 2)]
11 -> [(2, 6), (3, 5), (4, 2)]
15 -> [(2, 7), (3, 3), (6, 2)]
21 -> [(2, 7), (3, 3), (8, 2)]
8 -> [(2, 5), (3, 4), (4, 3), (5, 2)]
11 -> [(2, 5), (3, 4), (4, 3), (6, 2)]
13 -> [(2, 5), (3, 4), (5, 3), (6, 2)]
11 -> [(2, 6), (3, 4), (4, 3), (5, 2)]
14 -> [(2, 6), (3, 4), (4, 3), (6, 2)]
13 -> [(2, 6), (3, 5), (4, 3), (5, 2)]


Explaining the notation 12 -> [(2, 6), (3, 3), (6, 2)] means $$|X| > 12 \implies C(X;2,6) \cup C(X;3,3) \cup C(X;6,2)$$

• @domotorp edit two allows for all $k$ and $k'$ where as I originally thought it worked with opposite parity. But yes the floor is not needed. I'm not sure if it would be proper etiquette to simply replace the original claim. Edit: removed floor as you suggested, and removed parity statement, deleting "Edit 2" – yberman Jul 25 '17 at 5:04

Similar questions are studied by Martin Balko and Pavel Valtr in their recent paper: http://www.sciencedirect.com/science/article/pii/S0195669817300847

They use SAT solvers to obtain counterexamples to a few related conjectures.

• I disproved Peters and Szkeres's conjecture no later than September 2009 using Minisat. I sent a message to Bill GASARCH, a former professor, but that's it. I wish I knew it was publishable. – yberman Jul 25 '17 at 13:48