Search

The local properties problem of ErdH os and Shelah generalizes many Ramsey problems and some distinct distances problems. In this work, we derive a variety of new bounds for the local properties problem and its variants, by extending the color energy technique---a variant of the additive energy technique from additive combinatorics (color energy was originally introduced by the last two authors [C. Pohoata and A. Sheffer, Combinatorica, 39 (2019), pp. 705--714]). We generalize the concept of color energy to higher color energies and combine these with bounds on the extremal numbers of even cycles. Let f(n, k, ell) denote the minimum number of colors required to color the edges of Kn such that every k vertices span at least ell colors. It can be easily shown that f(n, k, bigl(k 2 bigr) lfloor k 2 rfloor +2) = Theta (n2). ErdH os and Gyarfas asked what happens when ell = bigl(k 2 bigr) lfloor k/2rfloor +1, one away from the easy case, and derived the bound f (n, k, ell) = Omega (n4/3). Our technique significantly improves this to f(n, k, bigl(k 2 bigr) lfloor k/2rfloor + 1) = Omega (n2 8/k). [ABSTRACT FROM AUTHOR]

We construct finite sets of real numbers that have a small difference set and strong local properties. In particular, we construct a set A of n real numbers such that | A − A | = n log 2 3 and that every subset A ′ ⊆ A of size k satisfies | A ′ − A ′ | ≥ k log 2 3. This construction leads to the first non-trivial upper bound for the problem of distinct distances with local properties. [ABSTRACT FROM AUTHOR]