This HTML5 document contains 48 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n12http://localhost/temp/predkladatel/
n18http://linked.opendata.cz/resource/domain/vavai/projekt/
n15http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n4http://linked.opendata.cz/ontology/domain/vavai/
n14http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216208%3A11320%2F14%3A10286487%21RIV15-MSM-11320___/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
rdfshttp://www.w3.org/2000/01/rdf-schema#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n20http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n6http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n8http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n19http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n9http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216208%3A11320%2F14%3A10286487%21RIV15-MSM-11320___
rdf:type
n4:Vysledek skos:Concept
rdfs:seeAlso
http://dx.doi.org/10.1137/140963716
dcterms: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.
dcterms:title
LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS
skos:prefLabel
LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS LOWER BOUNDS ON GEOMETRIC RAMSEY FUNCTIONS
skos:notation
RIV/00216208:11320/14:10286487!RIV15-MSM-11320___
n3:aktivita
n5:S n5:P
n3:aktivity
P(GBP202/12/G061), S
n3:cisloPeriodika
4
n3:dodaniDat
n9:2015
n3:domaciTvurceVysledku
n15:3374041 n15:2414767 n15:9921745
n3:druhVysledku
n19:J
n3:duvernostUdaju
n17:S
n3:entitaPredkladatele
n14:predkladatel
n3:idSjednocenehoVysledku
26694
n3:idVysledku
RIV/00216208:11320/14:10286487
n3:jazykVysledku
n8:eng
n3:klicovaSlova
superorder-type; order type; semialgebraic predicate; Ramsey function; Ramsey theory
n3:klicoveSlovo
n6:order%20type n6:semialgebraic%20predicate n6:Ramsey%20theory n6:superorder-type n6:Ramsey%20function
n3:kodStatuVydavatele
US - Spojené státy americké
n3:kontrolniKodProRIV
[9877D02069C0]
n3:nazevZdroje
SIAM Journal on Discrete Mathematics
n3:obor
n13:BA
n3:pocetDomacichTvurcuVysledku
3
n3:pocetTvurcuVysledku
4
n3:projekt
n18:GBP202%2F12%2FG061
n3:rokUplatneniVysledku
n9:2014
n3:svazekPeriodika
28
n3:tvurceVysledku
Eliáš, Marek Roldan-Pensado, Edgardo Patáková, Zuzana Matoušek, Jiří
n3:wos
000346844200020
s:issn
0895-4801
s:numberOfPages
11
n20:doi
10.1137/140963716
n12:organizacniJednotka
11320