PreprintarXiv licencearXiv
General-position sets and linear hypergraphs
Abstract
We prove that every linear hypergraph on N vertices with edge sizes O(√N) and O(N2log N) triples contained in its edges has a subset of size Ω(√N) meeting each edge in at most two vertices. As an application, every set of N planar points with at most √N collinear points contains Ω(√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.
Related
- Random independent sets in triangle-free and linear Berge-C4-free hypergraphs
- Follow the Perturbed Leader for Linear Bandits: √T Regret over General Action Sets
- On Counting Independent Sets in Regular Hypergraphs
- Random independent sets in uncrowded hypergraphs
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
BibTeX
@misc{pham2026generalposition,
title = {{General-position sets and linear hypergraphs}},
author = {Thang Pham and Le Quang-Ham and Boqing Xue},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34254},
eprint = {2610.34254},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34254},
}
RIS
TY - UNPB
TI - General-position sets and linear hypergraphs
AU - Thang Pham
AU - Le Quang-Ham
AU - Boqing Xue
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34254
UR - https://arxiv.org/abs/2610.34254
AB - We prove that every linear hypergraph on N vertices with edge sizes O(√N) and O(N^2log N) triples contained in its edges has a subset of size Ω(√N) meeting each edge in at most two vertices. As an application, every set of N planar points with at most √N collinear points contains Ω(√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.
ER -