| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:seeAlso
| |
| Description
| - Let P = (p(1), p(2),...,p(N)) be a sequence of points in the plane, where p(i) = (x(i), y(i)) and x(1) < x(2) < ... < x(N). A famous 1935 Erdos-Szekeres theorem asserts that every such P contains a monotone subsequence S of inverted right perpendicular root N inverted left perpendicular points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Omega(log N) points. Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a (k + 1)-tuple K subset of P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S subset of P is kth-order monotone if its (k + 1)-tuples are all positive or all negative. We investigate a quantitative bound for the corresponding Ramsey-type result (i.e., how large kth-order monotone subsequence can be guaranteed in every N-point P). We obtain an Omega(log((k-1)) N) lower bound ((k - 1)-times iterated logarithm). This is based on a quantitative Ramsey-type theorem for transitive colorings of the complete (k + 1)-uniform hypergraph (these were recently considered by Pach, Fox, Sudakov, and Suk). For k = 3, we construct a geometric example providing an O(log log N) upper bound, tight up to a multiplicative constant. As a consequence, we obtain similar upper bounds for a Ramsey-type theorem for order-type homogeneous subsets in R-3, as well as for a Ramsey-type theorem for hyperplanes in R-4 recently used by Dujmovic and Langerman.
- Let P = (p(1), p(2),...,p(N)) be a sequence of points in the plane, where p(i) = (x(i), y(i)) and x(1) < x(2) < ... < x(N). A famous 1935 Erdos-Szekeres theorem asserts that every such P contains a monotone subsequence S of inverted right perpendicular root N inverted left perpendicular points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Omega(log N) points. Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a (k + 1)-tuple K subset of P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S subset of P is kth-order monotone if its (k + 1)-tuples are all positive or all negative. We investigate a quantitative bound for the corresponding Ramsey-type result (i.e., how large kth-order monotone subsequence can be guaranteed in every N-point P). We obtain an Omega(log((k-1)) N) lower bound ((k - 1)-times iterated logarithm). This is based on a quantitative Ramsey-type theorem for transitive colorings of the complete (k + 1)-uniform hypergraph (these were recently considered by Pach, Fox, Sudakov, and Suk). For k = 3, we construct a geometric example providing an O(log log N) upper bound, tight up to a multiplicative constant. As a consequence, we obtain similar upper bounds for a Ramsey-type theorem for order-type homogeneous subsets in R-3, as well as for a Ramsey-type theorem for hyperplanes in R-4 recently used by Dujmovic and Langerman. (en)
|
| Title
| - Higher-order Erdos-Szekeres theorems
- Higher-order Erdos-Szekeres theorems (en)
|
| skos:prefLabel
| - Higher-order Erdos-Szekeres theorems
- Higher-order Erdos-Szekeres theorems (en)
|
| skos:notation
| - RIV/00216208:11320/13:10145705!RIV14-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/13:10145705
|
| http://linked.open...riv/jazykVysledku
| |
| http://linked.open.../riv/klicovaSlova
| - kth-order monotone subset; Divided difference; Order type; Hypergraph; Ramsey theory; Erdos-Szekeres theorem (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
| |
| http://linked.open...in/vavai/riv/obor
| |
| http://linked.open...ichTvurcuVysledku
| |
| http://linked.open...cetTvurcuVysledku
| |
| http://linked.open...UplatneniVysledku
| |
| http://linked.open...v/svazekPeriodika
| |
| http://linked.open...iv/tvurceVysledku
| - Eliáš, Marek
- Matoušek, Jiří
|
| http://linked.open...ain/vavai/riv/wos
| |
| issn
| |
| number of pages
| |
| http://bibframe.org/vocab/doi
| - 10.1016/j.aim.2013.04.020
|
| 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)