On the number of points in general position in the plane

DOI10.19086/DA.4438zbMATH Open1404.52016arXiv1704.05089OpenAlexW3098403304WikidataQ129141879 ScholiaQ129141879MaRDI QIDQ4645041FDOQ4645041

Authors: József Balogh, József Solymosi 

Publication date: 9 January 2019

Published in: Discrete Analysis (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1704.05089

Recommendations

• On the General Position Subset Selection Problem
• On the Erdös-Szekeres problem
• Sets in almost general position
• General position subsets and independent hyperplanes in \(d\)-space
• On the Erdős-Szekeres convex polygon problem

Mathematics Subject Classification ID

Hypergraphs (05C65) Erd?s problems and related topics of discrete geometry (52C10)

Cites Work

• Title not available (Why is that?)
• \(\epsilon\)-nets and simplex range queries
• Almost tight bounds for \(\epsilon\)-nets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Szemerédi-Trotter-type theorems in dimension 3
• Independent sets in hypergraphs
• Maximum-size antichains in random set-systems
• Title not available (Why is that?)
• On some metric and combinatorial geometric problems
• Title not available (Why is that?)
• A new proof of the density Hales-Jewett theorem
• Indecomposable Coverings
• A non-linear lower bound for planar epsilon-nets
• Sharp bound on the number of maximal sum-free subsets of integers
• A density version of the Hales-Jewett theorem
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• A random version of Sperner's theorem
• Small-size \(\varepsilon\)-nets for axis-parallel rectangles and boxes
• A note on coloring line arrangements
• Density Hales-Jewett and Moser numbers
• A density version of the Hales-Jewett theorem for \(k=3\)
• Tight lower bounds for the size of epsilon-nets
• Title not available (Why is that?)
• A short proof of the random Ramsey theorem
• An exponential-type upper bound for Folkman numbers
• Title not available (Why is that?)
• The number of subsets of integers with no \(k\)-term arithmetic progression

Cited In (12)

• An efficient container lemma
• Probabilistic hypergraph containers
• Integer colorings with forbidden rainbow sums
• On higher-dimensional point sets in general position
• Sets in almost general position
• General position subsets and independent hyperplanes in \(d\)-space
• The Typical Structure of Gallai Colorings and Their Extremal Graphs
• Counting arcs in \(\mathbb{F}_q^2\)
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Arcs in \(\mathbb{F}_q^2\)
• A new lower bound on Hadwiger-Debrunner numbers in the plane
• Four‐term progression free sets with three‐term progressions in all large subsets

This page was built for publication: On the number of points in general position in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4645041)