Local Properties via Color Energy Graphs and Forbidden Configurations

Abstract

The local properties problem of Erdős 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,l) denote the minimum number of colors required to color the edges of K_n such that every k vertices span at least l colors. It can be easily shown that f(n,k,(k/2)–[k/2]+2 = Θ(n²). Erdős and Gyárfás asked what happens when l = (k/2)-[k/2]+1, one away from the easy case, and derived the bound f(n,k,l) = Ω(n^(4/3)). Our technique significantly improves this to f(n,k,(k/2))–[k/2]+1) = Ω(n^(2-8/k)).

Files

Additional details