ON VISIBILITY AND BLOCKERS

Abstract. This expository paper discusses some conjectures related to visibility and blockers for sets of points in the plane. 1. Visibility Graphs 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 vw. The visibility graph V(P) of P has vertex set P, where two distinct points v, w ∈ P are adjacent if and only if they are visible with respect to P. So V(P) is obtained by drawing lines through each pair of points in P, where two points are adjacent if they are consecutive on a such a line. Visibility graphs have many interesting properties. For example, they have diameter at most 2 (assuming P is not collinear). Consider the following Ramsey-theoretic conjecture by Kára et al. [18], which has recently received considerable attention [1, 2, 21]. Conjecture 1 (Big-Line-Big-Clique Conjecture [18]). For all positive integers k and ` there is an integer n such that for every finite set P of at least n points in the plane: • P contains ` collinear points, or • P contains k pairwise visible points (that is, V(P) contains a k-clique). Conjecture 1 is true for k ≤ 5 or ` ≤ 3 [1, 2, 18], and is open for k = 6 or ` = 4. Note that the natural approach for attacking the Big-Line-Big-Clique Conjecture using extremal graph theory fails. Turán [35] proved that every n-vertex graph with more edges than the Turán graph Tn,k contains Kk+1 as a subgraph1. Thus the Big-Line-Big-Clique Conjecture would be proved if every sufficiently large visibility graph with no ` collinear points has more edges than Tn,k−1. However, Burr et al. [5] and Füredi and Palásti [15] constructed sets P of n points with no four collinear, such that P determines n 2 6 −O(n) lines each containing three points. Thus V(P) has n23 + O(n) edges, which is less than the number of edges in Tn,k−1 for all k ≥ 5 and large n. These examples show that 2000 Mathematics Subject Classification. 52C10 Erdős problems and related topics of discrete geom-etry, 05D10 Ramsey theory. 1 Let Tn,k be the k-coloured graph with ni vertices in the i-th colour class, where two vertices are adjacent if and only if they have distinct colours, and n = P i ni and |ni − nj | ≤ 1 for all i, j ∈ [k]