5
$\begingroup$

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.

8-gon

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)$$

$\endgroup$
  • $\begingroup$ @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" $\endgroup$ – yberman Jul 25 '17 at 5:04
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – yberman Jul 25 '17 at 13:48

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.