New bounds for the same-type lemma

2023/09/19 by Bukh, Boris, Vasileuski, Alexey · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2309.10731

Abstract

Given finite sets X₁,\dotsc,X_m in ℝ^d (with d fixed), we prove that there are respective subsets Y₁,\dotsc,Y_m with |Y_i|≥ (1)/(poly(m))|X_i| such that, for y₁∈ Y₁,\dotsc,y_m∈ Y_m, the orientations of the (d+1)-tuples from y₁,\dotsc,y_m do not depend on the actual choices of points y₁,\dotsc,y_m. This generalizes previously known case when all the sets X_i are equal. Furthermore, we give a construction showing that polynomial dependence on m is unavoidable, as well as an algorithm that approximates the best-possible constants in this result.

Cited by

• Crossing and non-crossing families

Related

• Forbidding just one intersection for short integer sequences
• A Proof of Grünbaum's Lower Bound Conjecture for general polytopes
• Projective Equivalences of k-neighbourly Polytopes
• A weak reduction of the Erd "os-Szekeres conjecture into a constraint\n unsatisfiability problem regarding certain multisets
• The Elekes-Szabó Problem and the Uniformity Conjecture