Induced Ramsey-type results and binary predicates for point sets

Martin Balko¹ ; Jan Kynčl² ; Stefan Langerman³ ; Alexander Pilz⁴

¹Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic Department of Computer Science, Faculty of Natural Sciences, Ben-Gurion University of the Negev, Beer Sheva, Israel
²Department of Applied Mathematics and Institute for Theoretical Computer Science, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic
³Département d'Informatique, Université Libre de Bruxelles, Brussels, Belgium
⁴Department of Computer Science, ETH Zürich, Zurich, Switzerland

The electronic journal of combinatorics, Tome 24 (2017) no. 4

Résumé

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 \ge 2$ and $p \ge 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.

Détail

DOI : 10.37236/7039

Classification : 05C55, 05D10
Mots-clés : order type, point set, induced Ramsey theorem, point-set predicate