A counterexample to a geometric Hales-Jewett type conjecture

Vytautas Gruslys


Pór and Wood conjectured that for all \(k,l \ge 2\) there exists \(n \ge 2\) with the following property: whenever \(n\) points, no \(l + 1\) of which are collinear, are chosen in the plane and each of them is assigned one of \(k\) colours, then there must be a line (that is, a maximal set of collinear points) all of whose points have the same colour. The conjecture is easily seen to be true for \(l = 2\) (by the pigeonhole principle) and in the case \(k = 2\) it is an immediate corollary of the Motzkin-Rabin theorem. In this note we show that the conjecture is false for \(k, l \ge 3\).

Full Text:


DOI: http://dx.doi.org/10.20382/jocg.v5i1a11

ISSN: 1920-180X