论文标题
要表征本地常见的图
Towards characterizing locally common graphs
论文作者
论文摘要
如果在完整图的2边彩色中h的单色拷贝数的数量渐近地通过随机着色来最小化，则图H是常见的。共同图的分类是极端图理论中最有趣的问题之一。我们研究了CSóka，Hubai和Lovász[Arxiv：1912.02926]考虑的局部弱常见图的概念，其中需要该图作为随机2边颜色的扰动而成为最小化器。我们对Taylor系列中的12个初始术语进行了完整的分析，该术语确定了此类扰动中H单色副本的数量，并基于此分析分为三类h的图形H分类H：I类的图在本地是弱的，II类的图在本地较弱并不是本地常见的，并且III类的图不能确定为局部的图表，不能确定基于本地III的图表，也不是基于本地常见的，也不是基于12个初始的12个术语。作为推论，我们在图表上获得了新的必要条件是常见的，并且图表上的新条件并不常见。
A graph H is common if the number of monochromatic copies of H in a 2-edge-coloring of the complete graph is asymptotically minimized by the random coloring. The classification of common graphs is one of the most intriguing problems in extremal graph theory. We study the notion of weakly locally common graphs considered by Csóka, Hubai and Lovász [arXiv:1912.02926], where the graph is required to be the minimizer with respect to perturbations of the random 2-edge-coloring. We give a complete analysis of the 12 initial terms in the Taylor series determining the number of monochromatic copies of H in such perturbations and classify graphs H based on this analysis into three categories: graphs of Class I are weakly locally common, graphs of Class II are not weakly locally common, and graphs of Class III cannot be determined to be weakly locally common or not based on the initial 12 terms. As a corollary, we obtain new necessary conditions on a graph to be common and new sufficient conditions on a graph to be not common.
