Induced Ramsey-Type Results and Binary Predicates for Point Sets
Result description
Let k and p be positive integers and let Q be a finite point set in general position in the plane. We say that Q is (k,p)-Ramsey if there is a finite point set P such that for every k-coloring c of (P choose p) there is a subset Q' of P such that Q' and Q have the same order type and (Q' choose p) is monochromatic in c. Nešetřil and Valtr proved that for every k ELEMENT OF N, all point sets are (k,1)-Ramsey. They also proved that for every k GREATER-THAN OR EQUAL TO 2 and p GREATER-THAN OR EQUAL TO 2, there are point sets that are not (k,p)-Ramsey. As our main result, we introduce a new family of (k,2)-Ramsey point sets, extending a result of Nešetřil and Valtr. We then use this new result to show that for every k there is a point set P such that no function Γ that maps ordered pairs of distinct points from P to a set of size k can satisfy the following "local consistency" property: if Γ attains the same values on two ordered triples of points from P, then these triples have the same orientation. Intuitively, this implies that there cannot be such a function that is defined locally and determines the orientation of point triples.
Keywords
The result's identifiers
Result code in IS VaVaI
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Induced Ramsey-Type Results and Binary Predicates for Point Sets
Original language description
Let k and p be positive integers and let Q be a finite point set in general position in the plane. We say that Q is (k,p)-Ramsey if there is a finite point set P such that for every k-coloring c of (P choose p) there is a subset Q' of P such that Q' and Q have the same order type and (Q' choose p) is monochromatic in c. Nešetřil and Valtr proved that for every k ELEMENT OF N, all point sets are (k,1)-Ramsey. They also proved that for every k GREATER-THAN OR EQUAL TO 2 and p GREATER-THAN OR EQUAL TO 2, there are point sets that are not (k,p)-Ramsey. As our main result, we introduce a new family of (k,2)-Ramsey point sets, extending a result of Nešetřil and Valtr. We then use this new result to show that for every k there is a point set P such that no function Γ that maps ordered pairs of distinct points from P to a set of size k can satisfy the following "local consistency" property: if Γ attains the same values on two ordered triples of points from P, then these triples have the same orientation. Intuitively, this implies that there cannot be such a function that is defined locally and determines the orientation of point triples.
Czech name
—
Czech description
—
Classification
Type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1077-8926
e-ISSN
—
Volume of the periodical
2017
Issue of the periodical within the volume
24
Country of publishing house
US - UNITED STATES
Number of pages
22
Pages from-to
1-22
UT code for WoS article
000414866500003
EID of the result in the Scopus database
—
Basic information
Result type
Jimp - Article in a specialist periodical, which is included in the Web of Science database
OECD FORD
Pure mathematics
Year of implementation
2017