Stability for the Erdos-Rothschild problem
Stability for the Erdos-Rothschild problem
复制标题
鄂尔多斯-罗斯柴尔德问题的稳定性
DOI：
10.1017/fms.2023.12
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Pikhurko O
中科院分区：
文献类型：
--
作者：
Pikhurko O
给定一个自然数序列和一个图G，设G的边的着色数为，使得对任意的边，色c的边不含阶团。写来表示n个顶点上的所有图G的最大值。这个问题最早是由Erdens和Rothschild在1974年考虑的，但它只在极少数非平凡情况下得到了解决。在先前与Pikhurko和Yilma的工作中，（Math. Proc.剑桥Phil. 163（2017），341-356），我们构造了一个有限优化问题，当n趋于无穷大时，其最大值等于极限，并证明了完全多部图G的稳定性定理。在本文中，我们提供了一个充分条件，保证了一般的稳定性定理的任何图G，描述的渐近结构的G在n个顶点的最优化问题的解决方案。我们应用我们的定理系统地恢复现有的稳定性结果以及所有的情况下。该证明使用了边色加权多重图的对称化。
Given a sequence of natural numbers and a graph G, let denote the number of colourings of the edges of G with colours , such that, for every , the edges of colour c contain no clique of order . Write to denote the maximum of over all graphs G on n vertices. This problem was first considered by Erdős and Rothschild in 1974, but it has been solved only for a very small number of nontrivial cases. In previous work with Pikhurko and Yilma, (Math. Proc. Cambridge Phil. Soc. 163 (2017), 341–356), we constructed a finite optimisation problem whose maximum is equal to the limit of as n tends to infinity and proved a stability theorem for complete multipartite graphs G. In this paper, we provide a sufficient condition on which guarantees a general stability theorem for any graph G, describing the asymptotic structure of G on n vertices with in terms of solutions to the optimisation problem. We apply our theorem to systematically recover existing stability results as well as all cases with . The proof uses a version of symmetrisation on edge-coloured weighted multigraphs.