Ramsey numbers of semi-algebraic and semi-linear hypergraphs

Abstract

An $r$-uniform hypergraph $H$ is semi-algebraic of complexity $\mathbf{t}=(d,D,m)$ if the vertices of $H$ correspond to points in ${\mathbb{R}}^d$, 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 $R_r^{\mathbf{t}}(s,n)$ denotes the smallest $N$ such that every $r$-uniform semi-algebraic hypergraph of complexity $\mathbf{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 $R_{r}^{\mathbf{t}}(n,n)<\mbox{tw}_{r-1}(n^{O(1)})$, where $\mbox{tw}_{k}(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 $R_3^{\mathbf{t}}(s,n)<n^{O(1)}$ for fixed $s$. We refute this conjecture by showing that $R_3^{\mathbf{t}}(4,n)>n^{(\log n{)}^{1/3-o(1)}}$ for some complexity $\mathbf{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 $R_r^{d,1,m}(n,n)\le 2^{O(n^{4r^2{m}^2})}$, while from below, we establish $R_r^{1,1,1}(n,n)\ge 2^{\Omega (n^{\lfloor r/2\rfloor -1})}$.

24 pages, 1 figure, published in JCTB

References in corpus (2)

• Circle graphs are quadratically $\chi$-bounded
• Erdos-Szekeres-type statements: Ramsey function and decidability in dimension 1