|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Lower bounds on geometric Ramsey functions | | Marek Elias
; Jiri Matousek
; Edgardo Roldan-Pensado
; Zuzana Safernova
; | | Date: |
19 Jul 2013 | | Abstract: | 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 in R^d. A sequence P=(p_1,...,
p_n) of points in R^d is called Phi-homogeneous if either
Phi(p_{i_1},...,p_{i_k}) 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, Fox, Pach, Sudakov, and Suk constructed the first examples of
semialgebraic predicates with the Ramsey function bounded from below by a tower
function of arbitrary height: for every k, they exhibit a k-ary Phi in
dimension 2^{k+1} with R_Phi bounded below by a tower of height k-1. We reduce
the dimension in their construction, obtaining a (d+3)-ary semialgebraic
predicate Phi on R^d with R_Phi bounded below by a tower of height d+2.
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, and we call P super-order-type
homogeneous if, for each i=1, 2,..., d, the projection of P on the first i
coordinates is order-type homogeneous. Every sufficiently long point sequence
in general position in R^d contains a super-order-type homogeneous subsequence
of length n; we show that "sufficiently long" has to be at least a tower
function of height d in n. | | Source: | arXiv, 1307.5157 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER