Toward characterizing locally common graphs期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Toward characterizing locally common graphs

Authors:	Robert Hancock Daniel Král' Matjaž Krnc Jan Volec

Institution:	1. Institut für Informatik, University of Heidelberg, Heidelberg, Germany Faculty of Informatics, Masaryk University, Brno, Czech Republic;2. Faculty of Informatics, Masaryk University, Brno, Czech Republic Mathematics Institute, DIMAP and Department of Computer Science, University of Warwick, Coventry, UK;3. Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Koper, Slovenia;4. Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Prague, Czech Republic

Abstract:	A graph $H $$ H $$$ is common if the number of monochromatic copies of $H $$ 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 $$ H $$$ in such perturbations and classify graphs $H $$ 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. 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.

Keywords:	common graphs graph limits Ramsey theory

设为首页 | 免责声明 | 关于勤云 | 加入收藏