The Erdos-Szekeres problem and an induced Ramsey question

Abstract

Motivated by the Erdos-Szekeres convex polytope conjecture in $R^d$, we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers $n>k\ge 5$, what is the minimum integer $g_k(n)$ such that any $k$-uniform hypergraph on $g_k(n)$ vertices with the property that any set of $k+1$ vertices induces 0, 2, or 4 edges, contains an independent set of size $n$. Our main result shows that $g_k(n)>2^{c{n}^{k-4}}$, where $c=c(k)$.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1707.04229