2023/10/21 by Sanjana Das, Das, Sanjana
Engineering · #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2310.13999
openalex publication_date 2023/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the local properties problem for difference sets: we define g(n, k, ℓ) to be the minimum value of | A - A| over all n-element sets A ⊆ ℝ with the `local property' that | A' - A'| ≥ ℓ for all k-element subsets A' ⊆ A. We view k and ℓ as fixed, and study the asymptotic behavior of g(n, k, ℓ) as n → ∞. One of our main results concerns the quadratic threshold, i.e., the minimum value of ℓ such that g(n, k, ℓ) = Ω(n2); we determine this value exactly for even k, and we determine it up to an additive constant for odd k. We also show that for all 1 < c ≤ 2, the `threshold' for g(n, k, ℓ) = Ω(nc) is quadratic in k; conversely, for ℓ quadratic in k, we obtain upper and lower bounds of the form nc for (not necessarily equal) constants c > 1. In particular, this provides the first nontrivial upper bounds in the regime where ℓ is quadratic in k.