On the number of points in general position in the plane

DOI10.19086/DA.4438MaRDI QIDQ4645041zbMATH OpenOpenAlexWikidataFDO

Authors József Balogh, József Solymosi

Publication date 9 January 2019

Published in Discrete Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)