Semi-algebraic Ramsey numbers

DOI10.1016/J.JCTB.2015.10.001MaRDI QIDQ896011zbMATH OpenOpenAlexFDO

Authors Andrew Suk

Publication date 11 December 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.6550

zbMATH Keywords

monochromatic trianglesone-sided hyperplanesRamsey theoryreal algebraic geometrysemi-algebraic relations

Mathematics Subject Classification ID

Ramsey theory (05D10)

Abstract: Given a finite point set $Psubsetmathbb{R}^d$, a $k$-ary semi-algebraic relation $E$ on $P$ is the set of $k$-tuples of points in $P$, which is determined by a finite number of polynomial equations and inequalities in $kd$ real variables. The description complexity of such a relation is at most $t$ if the number of polynomials and their degrees are all bounded by $t$. The Ramsey number $R_k^{d,t}(s,n)$ is the minimum $N$ such that any $N$-element point set $P$ in $mathbb{R}^d$ equipped with a $k$-ary semi-algebraic relation $E$, such that $E$ has complexity at most $t$, contains $s$ members such that every $k$-tuple induced by them is in $E$, or $n$ members such that every $k$-tuple induced by them is not in $E$. We give a new upper bound for $R_k^{d,t}(s,n)$ for $kgeq3$ and $s$ fixed. In particular, we show that for fixed integers $d,t,s$, $R_3^{d,t}(s,n)leq{2}^{n^{o(1)}},$ establishing a subexponential upper bound on $R_3^{d,t}(s,n)$. This improves the previous bound of $2^{n^C}$ due to Conlon, Fox, Pach, Sudakov, and Suk, where $C$ is a very large constant depending on $d,t,$ and $s$. As an application, we give new estimates for a recently studied Ramsey-type problem on hyperplane arrangements in $mathbb{R}^d$. We also study multi-color Ramsey numbers for triangles in our semi-algebraic setting, achieving some partial results.

Recommendations

• Semi-algebraic Ramsey numbers
• Ramsey-type results for semi-algebraic relations
• Ramsey-type results for semi-algebraic relations
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• Ramsey-Turán numbers for semi-algebraic graphs

Cites work

• A center transversal theorem for hyperplanes and applications to graph drawing
• A note on order-type homogeneous point sets
• A note on Ramsey numbers
• A problem of Schur and its generalizations
• A Ramsey-type result for geometric -hypergraphs
• A singly exponential stratification scheme for real semi-algebraic varieties and its applications
• Algorithms in real algebraic geometry
• Almost tight upper bounds for vertical decompositions in four dimensions
• Applications of random sampling in computational geometry. II
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Crossing patterns of semi-algebraic sets
• Density and regularity theorems for semi-algebraic hypergraphs
• Efficient partition trees
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Good splitters for counting points in triangles
• Higher-order Erdős-Szekeres theorems
• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 3223507 (Why is no real title available?)
• Hypergraph Ramsey numbers
• On the Betti Numbers of Real Varieties
• Optimal partition trees
• Partition relations for cardinal numbers
• Ramsey-type results for semi-algebraic relations
• Some remarks on the theory of graphs
• Sum-free sets of integers
• Symmetric sum-free partitions and lower bounds for Schur numbers
• The early evolution of the \(H\)-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The triangle-free process

Cited in

(13)

• Independent sets in algebraic hypergraphs
• The Schur-Erdős problem for semi-algebraic colorings
• Crossing patterns of semi-algebraic sets
• Ramsey-type results for semi-algebraic relations
• Semi-algebraic colorings of complete graphs
• Ramsey-type results for semi-algebraic relations
• Semi-algebraic Ramsey numbers
• Ramsey numbers of semi-algebraic and semi-linear hypergraphs
• A Borsuk-Ulam lower bound for sign-rank and its applications
• Ramsey-Turán numbers for semi-algebraic graphs
• Convex polytopes from fewer points
• Semi-algebraic and semi-linear Ramsey numbers (extended abstract)
• Compact representation of semilinear and terrain-like graphs

This page was built for publication: Semi-algebraic Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896011)