Semi-algebraic and semi-linear Ramsey numbers

EUROCOMB’23

Zhihan Jin István Tomon

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-087

PDF
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^{(\log n)^{1/3-o(1)}}$ for some complexity $\mathbf{t}$. In addition, motivated by the results of Bukh-Matoušek and Basit-Chernikov-Starchenko-Tao-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)\leq 2^{O(n^{4r^2m^2})}$, while from below, we establish $R^{1,1,1}_{r}(n,n)\geq 2^{\Omega(n^{\lfloor r/2\rfloor-1})}$.

Pages:
632–638
References

Noga Alon, János Pach, Rom Pinchasi, Radoš Radoičić, and Micha Sharir. Crossing patterns of semi-algebraic sets. Journal of Combinatorial Theory, Series A, 111(2):310-326, 2005.
https://doi.org/10.1016/j.jcta.2004.12.008

Edgar Asplund and B Grünbaum. On a coloring problem. Mathematica Scandinavica, 8(1):181-188, 1960.
https://doi.org/10.7146/math.scand.a-10607

Abdul Basit, Artem Chernikov, Sergei Starchenko, Terence Tao, and Chieu-Minh Tran. Zarankiewicz's problem for semilinear hypergraphs. Forum Math. Sigma, 9:Paper No. e59, 23, 2021.
https://doi.org/10.1017/fms.2021.52

Boris Bukh and Jiří Matoušek. Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1. Duke Mathematical Journal, 163(12):2243-2270, 2014.
https://doi.org/10.1215/00127094-2785915

Parinya Chalermsook and Bartosz Walczak. Coloring and maximum weight independent set of rectangles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 860-868. SIAM, 2021.
https://doi.org/10.1137/1.9781611976465.54

David Conlon, Jacob Fox, János Pach, Benny Sudakov, and Andrew Suk. Ramseytype results for semi-algebraic relations. Transactions of the American Mathematical Society, 366(9):5043-5065, 2014.
https://doi.org/10.1090/S0002-9947-2014-06179-5

David Conlon, Jacob Fox, and Benny Sudakov. Hypergraph ramsey numbers. Journal of the American Mathematical Society, 23(1):247-266, 2010.
https://doi.org/10.1090/S0894-0347-09-00645-6

James Davies and Rose McCarty. Circle graphs are quadratically χ- bounded. Bull. London Math. Society, 53(3):673-679, 2021.
https://doi.org/10.1112/blms.12447

Marek Eliáš, Jiří Matoušek, Edgardo Roldán-Pensado, and Zuzana Safernová. Lower bounds on geometric ramsey functions. SIAM Journal on Discrete Mathematics, 28(4):1960-1970, 2014.
https://doi.org/10.1137/140963716

Paul Erdős and András Hajnal. On ramsey like theorems. problems and results. In Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pages 123-140. Citeseer, 1972.

Paul Erdős and Richard Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London mathematical Society, 3(1):417-439, 1952.
https://doi.org/10.1112/plms/s3-2.1.417

Paul Erdős. Some remarks on the theory of graphs. Bulletin of the American Mathematical Society, 53(4):292-294, 1947.
https://doi.org/10.1090/S0002-9904-1947-08785-1

Paul Erdős and András Hajnal. Some remarks on set theory. ix. combinatorial problems in measure theory and set theory. Michigan Mathematical Journal, 11(2):107-127, 1964.
https://doi.org/10.1307/mmj/1028999083

Paul Erdős, András Hajnal, and Richard Rado. Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar, 16:93-196, 1965.
https://doi.org/10.1007/BF01886396

Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio mathematica, 2:463-470, 1935.

Ronald L Graham, Bruce L Rothschild, and Joel H Spencer. Ramsey theory, volume 20. John Wiley & Sons, 1991.

David Larman, Jiří Matoušek, János Pach, and Jenő Törőcsik. A Ramsey-type result for convex sets. Bull. London Math. Soc., 26(2):132-136, 1994.
https://doi.org/10.1112/blms/26.2.132

Dhruv Mubayi and Andrew Suk. New lower bounds for hypergraph ramsey numbers. Bulletin of the London Mathematical Society, 50(2):189-201, 2018.
https://doi.org/10.1112/blms.12133

Andrew Suk. Semi-algebraic ramsey numbers. Journal of Combinatorial Theory, Series B, 116:465-483, 2016.
https://doi.org/10.1016/j.jctb.2015.10.001

Andrew Suk and István Tomon. Hasse diagrams with large chromatic number. Bulletin of the London Mathematical Society, 53, 2021.
https://doi.org/10.1112/blms.12457

Endre Szemerédi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:381-392, 1983.
https://doi.org/10.1007/BF02579194

István Tomon. Ramsey properties of semilinear graphs. Israel Journal of Mathematics, pages 1-27, 2022.
https://doi.org/10.1007/s11856-022-2390-7

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Zhihan Jin, István Tomon

PDF