2018/06/30 by Cosmin Pohoata, Pohoata, Cosmin, Adam Sheffer +1
Mathematics · #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1807.00201
openalex publication_date 2018/06/30 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
We study Extremal Combinatorics problems where local properties are used to\nderive global properties. That is, we consider a given configuration where\nevery small piece of the configuration satisfies some restriction, and use this\nlocal property to derive global properties of the entire configuration. We\nstudy one such Ramsey problem of Erd Hos and Shelah, where the configurations\nare complete graphs with colored edges and every small induced subgraph\ncontains many distinct colors. Our bounds for this Ramsey problem show that the\nknown probabilistic construction is tight in various cases. We study one\nDiscrete Geometry variant, also by Erd Hos, where we have a set of points in\nthe plane such that every small subset spans many distinct distances. Finally,\nwe consider an Additive Combinatorics problem, where we are given sets of real\nnumbers such that every small subset has a large difference set.\n We derive new bounds for all of the above problems. Our proof technique is\nbased on introducing an non-algebraic variant of additive energies. This\nabstract energy variant is based on edge colors in graphs.\n