Local Properties via Color Energy Graphs and Forbidden Configurations
- Creators
- Fish, Sara
- Pohoata, Cosmin
- Sheffer, Adam
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)).
Additional Information
© 2020 Society for Industrial and Applied Mathematics. Received by the editors November 12, 2018; accepted for publication (in revised form) November 12, 2019; published electronically January 9, 2020. Funding: This research project was done as part of the 2018 CUNY Combinatorics REU, supported by NSF grant DMS-1710305. The third author was supported by NSF award DMS-1802059 and PSC-CUNY award 61666-00-49. We would like to thank Yufei Zhao for a discussion that led to Proposition 1.5. We would like to thank Robert Krueger and Rados Radoicic for several helpful discussions. We are grateful to the anonymous referee who helped us improve this paper.Attached Files
Published - 18m1225987.pdf
Submitted - 1810.09019.pdf
Files
Name | Size | Download all |
---|---|---|
md5:fd0e0bdc2478ef7241c7bda1f5451fa0
|
379.4 kB | Preview Download |
md5:7c0ed9742338b35dccb43e5da3ac5072
|
189.6 kB | Preview Download |
Additional details
- Eprint ID
- 100646
- Resolver ID
- CaltechAUTHORS:20200110-153219739
- DMS-1710305
- NSF
- DMS-1802059
- NSF
- 61666-00-49
- City University of New York
- Created
-
2020-01-11Created from EPrint's datestamp field
- Updated
-
2021-11-16Created from EPrint's last_modified field