Quantifier-resolved off-diagonal semi-algebraic graph Ramsey numbers

Definitions and mathematical statement

Fix a polynomial $f\in\mathbb R[x_1,y_1,x_2,y_2]$. For an ordered sequence $P=(v_1,\ldots,v_N)$ of distinct points in $\mathbb R^2$, define a simple undirected graph on $[N]$ by declaring $ij$ an edge, for $i<j$, exactly when $f(v_i,v_j)\geq0$. The order of indices removes any need to assume symmetry of $f$. A triangle is a set of three pairwise adjacent vertices, and an independent set contains no adjacent pair.

Let $R_f(3,n)$ be the least $N$ such that every graph obtained in this way has either a triangle or an independent set of size $n$. The off-diagonal Ramsey question asks whether, for every fixed $f$ and every $\varepsilon>0$, there exists a constant $C(f,\varepsilon)$ such that \[ R_f(3,n)\leq C(f,\varepsilon)n^{1+\varepsilon} \qquad\text{for every integer }n\geq2. \] Equivalently, triangle-free members of this fixed polynomial family should have independent sets of size $N^{1-o(1)}$ as $N$ grows, with the error allowed to depend on $f$. The displayed formulation specifies the upper-bound content of the workshop shorthand $n^{1+o(1)}$. Literal asymptotic equality cannot hold for every individual polynomial, since some polynomials define complete graphs for every configuration and therefore give a bounded threshold. No bound uniform over polynomials of unbounded complexity is demanded.

Short English statement

Do triangle-free planar graphs defined by a fixed polynomial sign condition have independent sets of almost linear size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000941 (AIM-COMBINATORICS-0066), 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 19. Original workshop question underlying AIM-COMBINATORICS-0066. https://www.overleaf.com/read/mnvcscjjysvg.