Induced Ramsey-type results and binary predicates for point sets (Q5915805): Difference between revisions

Summary: 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 \(\binom{P}{p}\) there is a subset \(Q'\) of \(P\) such that \(Q'\) and \(Q\) have the same order type and \(\binom{Q'}{p}\) is monochromatic in \(c\). Nešetřil and Valtr proved that for every \(k \in \mathbb{N}\), all point sets are \((k,1)\)-Ramsey. They also proved that for every \(k \geq 2\) and \(p \geq 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 \(\Gamma\) that maps ordered pairs of distinct points from \(P\) to a set of size \(k\) can satisfy the following ``local consistency'' property: if \(\Gamma\) 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.