---
author:
- Attila Pór
- 'David R. Wood'
title: |
    The Big-Line-Big-Clique Conjecture\
    is False for Infinite Point Sets
---

Let $P$ be a finite set of points in the plane. Two distinct points $v$ and $w$ in the plane are *visible* with respect to $P$ if no point in $P$ is in the open line segment $\overline{vw}$. @KPW-DCG05 made the following Ramsey-theoretic conjecture, which has recently received considerable attention [@KPW-DCG05; @Luigi; @EmptyPentagon-GC; @ABBCLPW; @PorWood-JoCG; @Matousek09].

[**Big-Line-Big-Clique Conjecture**]{} [@KPW-DCG05] For all $k\geq2$ and $\ell\geq2$ there is an integer $n$ such that every finite set of at least $n$ points in the plane:

-   contains $\ell$ collinear points, or

-   contains $k$ pairwise visible points.

This conjecture is true for $k\leq 5$ or $\ell\leq3$ [@KPW-DCG05; @Luigi; @EmptyPentagon-GC], and is open for $k=6$ or $\ell=4$. Note that the natural approach for attacking this conjecture using extremal graph theory fails [@PorWood-JoCG]. Another natural approach for attacking the Big-Line-Big-Clique Conjecture is to follow an infinitary compactness argument (which can be used to establish many results in Ramsey theory). The purpose of this note is to show that this conjecture is false for infinite point sets, which suggests that an infinitary compactness argument cannot work.

There is a countably infinite point set with no 4 collinear points and no 3 pairwise visible points.

Let $x_1,x_2,x_3$ be three non-collinear points in the plane. Given points $x_1,\dots,x_{n-1}$, define $x_n$ as follows. By the Sylvester-Gallai theorem, there is a line through exactly two of $x_1,\dots,x_{n-1}$. Choose such a line $\overleftrightarrow{x_ix_j}$ with $i<j$ such that $j$ is minimum and then $i$ is minimum. Insert $x_n$ on $\overline{x_ix_j}$, such that $\{x_i,x_n,x_j\}$ is the only collinear triple that contains $x_n$. This is possible, since there are only finitely many ($\leq\binom{n-3}{2}$) excluded locations for $x_n$.

Repeat this step to obtain a point set $\{x_i:i\in\mathbb{N}\}$, which by construction, contains no 4 collinear points. Moreover, if $x_i$ and $x_k$ are visible with $i<k$, then $x_i$ and $x_k$ are collinear with some other point $x_{i'}$ (otherwise some point would be added at a later stage in $\overline{x_ix_k}$). Since $i<k$ we have $x_k\in\overline{x_ix_{i'}}$ and $i'<k$.

Suppose on the contrary that three points $x_i,x_j,x_k$ are pairwise visible, where $i<j<k$. As proved above, $x_k\in\overline{x_ix_{i'}}$ and $x_k\in\overline{x_jx_{j'}}$, where $i',j'<k$. Since $x_k$ is in only one collinear triple amongst $x_1,\dots,x_k$, we have $i'=j$ and $j'=i$. Thus $x_i,x_k,x_j$ are collinear, and $x_i$ and $x_j$ are not visible. This contradiction proves that no 3 points are pairwise visible.

\#1[0=7=0 7 by-1ext\#1\#1T\#1 \#1 d\#1\#1 D\#1\#1 l\#1\#1 L\#1\#1\#1]{}

[6]{} \[1\][\#1]{} \[1\][`#1`]{} urlstyle \[1\][doi:\#1]{}

<span style="font-variant:small-caps;">Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Pór, and David R. Wood</span>. Every large point set contains many collinear points or an empty pentagon. *Proc. 21st Canadian Conference on Computational Geometry* (CCCG ’09), pp. 99–102, 2009. *Graphs and Combinatorics*, to appear. <http://arxiv.org/abs/0904.0262>.

<span style="font-variant:small-caps;">Louigi Addario-Berry, Cristina Fernandes, Yoshiharu Kohayakawa, Jos Coelho de Pina, and Yoshiko Wakabayashi</span>. On a geometric [R]{}amsey-style problem, 2007. <http://crm.umontreal.ca/cal/en/mois200708.html>.

<span style="font-variant:small-caps;">Greg Aloupis, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Stefan Langerman, Attila Pór, and David R. Wood</span>. Blocking coloured point sets. In *Proc. 26th European Workshop on Computational Geometry* (EuroCG ’10), pp. 29–32. 2010. <http://arxiv.org/abs/1002.0190>.

<span style="font-variant:small-caps;">Jan K[á]{}ra, Attila P[ó]{}r, and David R. Wood</span>. On the chromatic number of the visibility graph of a set of points in the plane. *Discrete Comput. Geom.*, 34(3):497–506, 2005. <http://dx.doi.org/10.1007/s00454-005-1177-z>.

<span style="font-variant:small-caps;">Ji[ř]{}[í]{} Matou[š]{}ek</span>. Blocking visibility for points in general position. *Discrete Comput. Geom.*, 42(2):219–223, 2009. <http://dx.doi.org/10.1007/s00454-009-9185-z>.

<span style="font-variant:small-caps;">Attila Pór and David R. Wood</span>. On visibility and blockers. *J. Comput. Geom.*, 1(1):29–40, 2010. <http://www.jocg.org/index.php/jocg/article/view/24>.
