Local Properties in Colored Graphs, Distinct Distances, and Difference Sets
Local Properties in Colored Graphs, Distinct Distances, and Difference Sets
复制标题
DOI：
10.1007/s00493-018-3890-2
复制
发表时间：
2018-06
期刊：
影响因子：
1.1
通讯作者：
C. Pohoata;Adam Sheffer
中科院分区：
文献类型：
--
作者：
C. Pohoata;Adam Sheffer
我们研究了用局部性质来导出全局性质的极值组合问题。也就是说，我们考虑一个给定的配置，其中配置的每一小部分都满足一些限制，并使用这个局部属性来导出整个配置的全局属性。我们研究了一个这样的Ramsey问题Erdős和Shelah，其中构型是带彩色边的完全图，并且每个小诱导子图包含许多不同的颜色。Ramsey问题的边界表明，已知的概率结构在各种情况下都是紧的。我们研究了一个离散几何的变体，也是通过Erdős，我们在平面上有一组点，每个小子集都跨越了许多不同的距离。最后，我们考虑一个可加组合问题，其中我们给定实数集，其中每个小子集都有一个大的差集。我们为上述所有问题导出了新的界。我们的证明技术是基于引入一种基于图中边缘颜色的加性能量的变体。
We study Extremal Combinatorics problems where local properties are used to derive global properties. That is, we consider a given configuration where every small piece of the configuration satisfies some restriction, and use this local property to derive global properties of the entire configuration. We study one such Ramsey problem of Erdős and Shelah, where the configurations are complete graphs with colored edges and every small induced subgraph contains many distinct colors. Our bounds for this Ramsey problem show that the known probabilistic construction is tight in various cases. We study one Discrete Geometry variant, also by Erdős, where we have a set of points in the plane such that every small subset spans many distinct distances. Finally, we consider an Additive Combinatorics problem, where we are given sets of real numbers such that every small subset has a large difference set.We derive new bounds for all of the above problems. Our proof technique is based on introducing a variant of additive energy, which is based on edge colors in graphs.