On the number of points in general position in the plane

被引:13
作者
Balogh, Jozsef [1 ]
Solymosi, Jozsef [2 ]
机构
[1] Univ Illinois, Dept Math Sci, Urbana, IL 61801 USA
[2] Univ British Columbia, Dept Math, 1984 Math Rd, Vancouver, BC V6T 1Z4, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
General point sets in the plane; epsilon-nets; Hypergraph container method; DENSITY VERSION; EPSILON-NETS; SYSTEMS; BOUNDS; SIZE;
D O I
10.19086/da.4438
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
In this paper we study some Erdos type problems in discrete geometry. Our main result is that we show that there is a planar point set of n points such that no four are collinear but no matter how we choose a subset of size n(5/6 +o(1)) it contains a collinear triple. Another application studies epsilon-nets in a point-line system in the plane. We prove the existence of some geometric constructions with a new tool, the so-called Hypergraph Container Method.
引用
收藏
页数:20
相关论文
共 32 条
[1]  
Ackerman E, 2014, ELECTRON J COMB, V21
[2]   A non-linear lower bound for planar epsilon-nets [J].
Alon, Noga .
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :341-346
[3]  
[Anonymous], 2013, DISCRETE MATH THEOR
[4]  
[Anonymous], DECOMPOSITION UNPUB
[5]  
[Anonymous], 1994, BOLYAI SOC MATH STUD
[6]  
[Anonymous], COMBINATORIAL GEOMET
[7]  
[Anonymous], J EUROPEAN MATH SOC
[8]  
[Anonymous], 2010, BOLYAI SOC MATH STUD
[9]  
[Anonymous], 1998, Random graphs
[10]  
[Anonymous], APPL DISCRETE MATH