Paperlane

no. 5 · Friday 30 October 2026

Larger Crossing Families

Joachim Orthaber and Patrick Schnider

math.CO

Abstract

We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.

fields
Combinatorics
pdf ↗ page arXiv:2610.38658 ↗