An r-uniform hypergraph H is semi-algebraic of complexity t=(d,D,m) if the vertices of H correspond to points in Rd and the edges of H are determined by the sign-pattern of m degree-D polynomials. Semi-algebraic hypergraphs of bounded complexity provide a general framework for studying geometrically defined hypergraphs.
The much-studied semi-algebraic Ramsey number Rrt(s,n) denotes the smallest N such that every r-uniform semi-algebraic hypergraph of complexity t on N vertices contains either a clique of size s or an independent set of size n. Conlon, Fox, Pach, Sudakov and Suk proved that Rrt(n,n)<twr−1(nO(1)), where twk(x) is a tower of 2's of height k with an x on the top. This bound is also the best possible if min{d,D,m} is sufficiently large with respect to r. They conjectured that in the asymmetric case, we have R3t(s,n)<nO(1) for fixed s. We refute this conjecture by showing that R3t(4,n)>n(logn) for some complexity t.
In addition, motivated by results of Bukh and Matoušek and Basit, Chernikov, Starchenko, Tao and Tran, we study the complexity of the Ramsey problem when the defining polynomials are linear, that is, when D=1. In particular, we prove that Rrd,1,m(n,n)≤2O(n), while from below, we establish Rr1,1,1(n,n)≥2Ω(n).
Elsevier, 2023. Vol. 163, p. 54-82