论文标题
具有任意色数的常见图
Common graphs with arbitrary chromatic number
论文作者
论文摘要
Ramsey的定理可以保证每张图H的任何2边颜色的任何2边彩色的完整图包含H. H.的单色副本。1962年，Erdos猜想，随机的2边颜色最小化可以最大程度地减少K_K的单色副本的数量，并且Burr and Rosta扩展了所有图表。在1980年代后期，托马森（Thomason）和西多伦科（Sidorenko）分别驳斥了猜想。随机2边颜色将单色副本数量的分类最小化，该图被称为常见图，仍然是一个具有挑战性的开放问题。如果Sidorenko的猜想是极端图理论中最重要的开放问题之一，那么每个2个色谱图是常见的，实际上，对于Sidorenko的猜想，没有2个chrostic common Graph尚未确定。虽然长期以来已知3个色素公共图的示例，但4个色素公共图的存在是开放到2012年的，并且尚无具有较大色数的通用图。 我们为每个k构建了连接的k-chromatic共同图。这回答了Hatami，Hladky，Kral，Norine和Razborov [Combin。概率。计算。 21（2012），734-742]，以及Conlon，Fox和Sudakov [London Math。 Soc。讲座笔记Ser。 424（2015），49-118，问题2.28]。这也以更强的形式回答了Jagger，Stovicek和Thomason [Combinatorica 16，（1996），123-131]提出的问题。是否存在具有至少四个的常见图。
Ramsey's Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. In 1962, Erdos conjectured that the random 2-edge-coloring minimizes the number of monochromatic copies of K_k, and the conjecture was extended by Burr and Rosta to all graphs. In the late 1980s, the conjectures were disproved by Thomason and Sidorenko, respectively. A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. If Sidorenko's Conjecture, one of the most significant open problems in extremal graph theory, is true, then every 2-chromatic graph is common, and in fact, no 2-chromatic common graph unsettled for Sidorenko's Conjecture is known. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012, and no common graph with a larger chromatic number is known. We construct connected k-chromatic common graphs for every k. This answers a question posed by Hatami, Hladky, Kral, Norine and Razborov [Combin. Probab. Comput. 21 (2012), 734-742], and a problem listed by Conlon, Fox and Sudakov [London Math. Soc. Lecture Note Ser. 424 (2015), 49-118, Problem 2.28]. This also answers in a stronger form the question raised by Jagger, Stovicek and Thomason [Combinatorica 16, (1996), 123-131] whether there exists a common graph with chromatic number at least four.
