Three-monotone interpolation (Q2354672)

Inspired by the classical results on \(k\)-monotone interpolability for \(k = 1\) and \(k = 2\) due to \textit{P. Erdős} and \textit{G. Szekeres} from [Compos. Math. 2, 463--470 (1935; JFM 61.0651.04)], the authors investigate the \(3\)-monotone interpolability, showing for instance that it is very nonlocal, by providing an arbitrarily large and finite two-dimensional set \(P\) which is not \(3\)-monotone interpolable, but all its proper subsets are. Moreover, a Ramsey-type result is also proven, namely that for every positive integer \(n\) there exists another positive integer \(N\) such that every \(N\)-point with distinct \(x\)-coordinates contains an \(n\)-point that is \(3\)-monotone interpolable or its vertical mirror reflection has this property. The computational complexity of the problem of deciding the \(3\)-monotone interpolability of a given point set, stated as an instance of polynomial optimization and reformulated as a semidefinite program, is discussed, too. An example where this semidefinite program has only doubly exponentially large feasible solutions and thus known algorithms cannot solve it in polynomial time is provided, being arguably the first of its kind in polynomial optimization in the literature.