Many collinear k-tuples with no k+1 collinear points

2011/07/01 by József Solymosi, Solymosi, József, Miloš Stojaković +1
Computer Science · Mathematics · #52C10 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #cs.CG #math.CO #msc:52C10

paper · pdf · doi:10.48550/arxiv.1107.0327

arxiv created 2013/09/24 · arxiv updated 2013/09/25

Abstract

For every k>3, we give a construction of planar point sets with many collinear k-tuples and no collinear (k+1)-tuples. We show that there are n₀=n₀(k) and c=c(k) such that if n≥ n₀, then there exists a set of n points in the plane that does not contain k+1 points on a line, but it contains at least n^{2-(c)/(√(log n))} collinear k-tuples of points. Thus, we significantly improve the previously best known lower bound for the largest number of collinear k-tuples in such a set, and get reasonably close to the trivial upper bound O(n²).

Related

• Planar point sets with forbidden 4-point patterns and few distinct distances
• The Big-Line-Big-Clique Conjecture is False for Infinite Point Sets
• Counting Triangulations of Planar Point Sets
• Lines induced by bichromatic point sets
• A better upper bound on the number of triangulations of a planar point set