Large Convex sets in Difference sets

2023/09/14 by Krishnendu Bhowmick, Bhowmick, Krishnendu, Ben Lund +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2309.07527

openalex publication_date 2023/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a construction of a convex set A ⊂ \mathbb R with cardinality n such that A-A contains a convex subset with cardinality Ω(n²). We also consider the following variant of this problem: given a convex set A, what is the size of the largest matching M ⊂ A × A such that the set \ a-b : (a,b) ∈ M \ is convex? We prove that there always exists such an M with |M| ≥ √ n, and that this lower bound is best possible, up a multiplicative constant.

Cited by

• Additive structure in convex sets

Related

• A convex set with a rich difference
• Quantitative combinatorial geometry for concave functions
• Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set
• On the number of unit-area triangles spanned by convex grids in the plane
• On sumsets of convex sets