A positive fraction mutually avoiding sets theorem

DOI10.1016/J.DISC.2019.111730MaRDI QIDQ2286590zbMATH OpenOpenAlexWikidataFDO

Authors Mozhgan Mirzaei, Andrew Suk

Publication date 22 January 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

crossing familiesmutually avoiding setpositive fraction mutually avoiding sets

Mathematics Subject Classification ID

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

Abstract: Two sets $A$ and $B$ of points in the plane are emph{mutually avoiding} if no line generated by any two points in $A$ intersects the convex hull of $B$, and vice versa. In 1994, Aronov, ErdH os, Goddard, Kleitman, Klugerman, Pach, and Schulman showed that every set of $n$ points in the plane in general position contains a pair of mutually avoiding sets each of size at least $sqrtn/12$. As a corollary, their result implies that for every set of $n$ points in the plane in general position one can find at least $sqrtn/12$ segments, each joining two of the points, such that these segments are pairwise crossing. In this note, we prove a fractional version of their theorem: for every $k>0$ there is a constant $varepsilo{n}_k>0$ such that any sufficiently large point set $P$ in the plane contains $2k$ subsets $A_1,ldots,A_k,B_1,ldots,B_k$, each of size at least $varepsilo{n}_k|P|$, such that every pair of sets $A=a_1,ldots,a_k$ and $B=b_1,ldots,b_k$, with $a_{i}in{A}_i$ and $b_{i}in{B}_i$, are mutually avoiding. Moreover, we show that $varepsilo{n}_k=Omega(1/k^4)$. Similar results are obtained in higher dimensions

Recommendations

• scientific article; zbMATH DE number 970816
• A positive fraction Erdős-Szekeres theorem
• Complete positivity and distance-avoiding sets
• On the positive fraction Erdős-Szekeres theorem for convex sets
• On positive total sets
• scientific article; zbMATH DE number 966840
• Sum-avoiding subsets
• A proof of the fundamental theorem on the density of sums of sets of positive integers
• A Marstrand theorem for subsets of integers
• An Erdős-Ko-Rado theorem for signed sets

Cites work

• A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
• A positive fraction Erdős-Szekeres theorem
• Crossing families
• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• scientific article; zbMATH DE number 3843786 (Why is no real title available?)
• scientific article; zbMATH DE number 1241844 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 970816 (Why is no real title available?)
• On disjoint crossing families in geometric graphs
• Research Problems in Discrete Geometry
• The partitioned version of the Erdős-Szekeres theorem

Cited in

(5)

• scientific article; zbMATH DE number 970816 (Why is no real title available?)
• A positive fraction Erdős-Szekeres theorem and its applications
• New bounds for the same-type lemma
• On the structure of pointsets with many collinear triples
• On distinct angles in the plane

This page was built for publication: A positive fraction mutually avoiding sets theorem

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