| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:seeAlso
| |
| Description
| - We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in R-d. A k-ary semialgebraic predicate Phi(x(1), ..., x(k)) on R-d is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x(1), ..., x(k) is an element of R-d. A sequence P = (p(1), ..., p(n)) of points in R-d is called Phi-homogeneous if either Phi(p(i1), ..., p(ik)) holds for all choices 1 {= i(1) < ... < i(k) {= n, or it holds for no such choice. The Ramsey function R-Phi(n) is the smallest N such that every point sequence of length N contains a Phi-homogeneous subsequence of length n. Conlon et al. [Trans. Amer. Math. Soc., 366 (2013), pp. 5043-5065] constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every k }= 4, they exhibit a k-ary Phi in dimension 2(k-4) with R-Phi bounded below by a tower of height k - 1. We reduce the dimension in their construction, obtaining a k-ary semialgebraic predicate Phi on Rk-3 with R-Phi bounded below by a tower of height k - 1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence P in R-d order-type homogeneous if all (d + 1)-tuples in P have the same orientation. Every sufficiently long point sequence in general position in R-d contains an order-type homogeneous subsequence of length n, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Barany, Matousek, and Por [Curves in R-d Intersecting Every Hyperplane at Most d + 1 Times, preprint, arXiv:1309.1147; extended abstract in Proceedings of the 30th Annual Symposium on Computational Geometry, 2014], our results imply a tower function of Omega(n) of height d as a lower bound, matching an upper bound by Suk up to the constant in front of n.
- We continue a sequence of recent works studying Ramsey functions for semialgebraic predicates in R-d. A k-ary semialgebraic predicate Phi(x(1), ..., x(k)) on R-d is a Boolean combination of polynomial equations and inequalities in the kd coordinates of k points x(1), ..., x(k) is an element of R-d. A sequence P = (p(1), ..., p(n)) of points in R-d is called Phi-homogeneous if either Phi(p(i1), ..., p(ik)) holds for all choices 1 {= i(1) < ... < i(k) {= n, or it holds for no such choice. The Ramsey function R-Phi(n) is the smallest N such that every point sequence of length N contains a Phi-homogeneous subsequence of length n. Conlon et al. [Trans. Amer. Math. Soc., 366 (2013), pp. 5043-5065] constructed the first examples of semialgebraic predicates with the Ramsey function bounded from below by a tower function of arbitrary height: for every k }= 4, they exhibit a k-ary Phi in dimension 2(k-4) with R-Phi bounded below by a tower of height k - 1. We reduce the dimension in their construction, obtaining a k-ary semialgebraic predicate Phi on Rk-3 with R-Phi bounded below by a tower of height k - 1. We also provide a natural geometric Ramsey-type theorem with a large Ramsey function. We call a point sequence P in R-d order-type homogeneous if all (d + 1)-tuples in P have the same orientation. Every sufficiently long point sequence in general position in R-d contains an order-type homogeneous subsequence of length n, and the corresponding Ramsey function has recently been studied in several papers. Together with a recent work of Barany, Matousek, and Por [Curves in R-d Intersecting Every Hyperplane at Most d + 1 Times, preprint, arXiv:1309.1147; extended abstract in Proceedings of the 30th Annual Symposium on Computational Geometry, 2014], our results imply a tower function of Omega(n) of height d as a lower bound, matching an upper bound by Suk up to the constant in front of n. (en)
|
| Title
| - LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS
- LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS (en)
|
| skos:prefLabel
| - LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS
- LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS (en)
|
| skos:notation
| - RIV/00216208:11320/14:10286487!RIV15-MSM-11320___
|
| http://linked.open...avai/riv/aktivita
| |
| http://linked.open...avai/riv/aktivity
| |
| http://linked.open...iv/cisloPeriodika
| |
| http://linked.open...vai/riv/dodaniDat
| |
| http://linked.open...aciTvurceVysledku
| |
| http://linked.open.../riv/druhVysledku
| |
| http://linked.open...iv/duvernostUdaju
| |
| http://linked.open...titaPredkladatele
| |
| http://linked.open...dnocenehoVysledku
| |
| http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/14:10286487
|
| http://linked.open...riv/jazykVysledku
| |
| http://linked.open.../riv/klicovaSlova
| - superorder-type; order type; semialgebraic predicate; Ramsey function; Ramsey theory (en)
|
| http://linked.open.../riv/klicoveSlovo
| |
| http://linked.open...odStatuVydavatele
| - US - Spojené státy americké
|
| http://linked.open...ontrolniKodProRIV
| |
| http://linked.open...i/riv/nazevZdroje
| - SIAM Journal on Discrete Mathematics
|
| http://linked.open...in/vavai/riv/obor
| |
| http://linked.open...ichTvurcuVysledku
| |
| http://linked.open...cetTvurcuVysledku
| |
| http://linked.open...vavai/riv/projekt
| |
| http://linked.open...UplatneniVysledku
| |
| http://linked.open...v/svazekPeriodika
| |
| http://linked.open...iv/tvurceVysledku
| - Eliáš, Marek
- Matoušek, Jiří
- Patáková, Zuzana
- Roldan-Pensado, Edgardo
|
| http://linked.open...ain/vavai/riv/wos
| |
| issn
| |
| number of pages
| |
| http://bibframe.org/vocab/doi
| |
| http://localhost/t...ganizacniJednotka
| |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)