betaFeedback

WorksMathematics

General-position sets and linear hypergraphs

Abstract

We prove that every linear hypergraph on NN vertices with edge sizes O(N)O(\sqrt N) and O(N2log⁡N)O(N^2\log N) triples contained in its edges has a subset of size Ω(N)Ω(\sqrt N) meeting each edge in at most two vertices. As an application, every set of NN planar points with at most N\sqrt N collinear points contains Ω(N)Ω(\sqrt N) points in general position. This proves a conjecture of Payne and Wood and gives the optimal quadratic bound for a geometric Ramsey problem posed by Gowers.

Paper details

vlnc:W_m5nvrepg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…