Fixed-polynomial semi-algebraic Ramsey bounds and unbounded-degree universality

Definitions and mathematical statement

Fix an integer $k\geq2$ and a polynomial $f\in\mathbb R[x_1,y_1,\ldots,x_k,y_k]$. For an ordered sequence $P=(v_1,\ldots,v_N)$ of distinct points in $\mathbb R^2$, define a $k$-uniform hypergraph $H_f(P)$ on $[N]$ by \[ \{i_1,\ldots,i_k\}\in E(H_f(P)) \quad\Longleftrightarrow\quad f(v_{i_1},\ldots,v_{i_k})\geq0, \qquad i_1<\cdots<i_k. \] The order specifies how a potentially nonsymmetric polynomial is evaluated; zero values are edges. A vertex subset is homogeneous if all its $k$-element subsets are edges, or all are nonedges. Write $\omega(H)$ and $\alpha(H)$ for the largest sizes of these two kinds of subsets.

Define the guaranteed homogeneous-set size \[ h_f(N)=\min_P\max\{\omega(H_f(P)),\alpha(H_f(P))\}, \] where the minimum ranges over all ordered configurations of $N$ distinct planar points. The question is to determine sharp lower bounds for $h_f(N)$, and their dependence on $k$ and the defining polynomial, together with configurations showing sharpness. The polynomial is fixed as $N$ grows: letting its degree or coefficients be chosen anew for every configuration would change the problem. The source's unrestricted Ramsey lower bound is only a starting point; the objective is to exploit the planar algebraic description. A complete answer may distinguish polynomials whose induced hypergraphs have very different homogeneous-set growth.

Short English statement

How large a clique or independent set is forced when a planar point hypergraph is defined by one fixed polynomial sign condition?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000938 (AIM-COMBINATORICS-0063), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Graph Ramsey theory, item 16. Original workshop question underlying AIM-COMBINATORICS-0063. https://www.overleaf.com/read/mnvcscjjysvg.