论文标题
在三方公共图上
On tripartite common graphs
论文作者
论文摘要
如果随机着色最小化，则图H是常见的，如果在完整图的2边彩色中的单色拷贝数量最小。伯尔（Burr）和罗斯塔（Rosta）扩展了埃尔多斯（Erdos）的著名猜想，猜想每个图都是常见的。 Erdos和Burr和Rosta的猜想分别在1980年代后期被Thomason和Sidorenko驳回。从那以后，收集新的图表的新示例并没有看到太大的进步，尽管最近，通过FLAG代数法或Sidorenko猜想的最新进展验证了一些图表是常见的。 我们在这里做出的贡献是提供新的三方共同图。第一个示例课是所谓的三角形树，它概括了Sidorenko的两个定理，并回答了1996年从Jagger，Šťovíček和Thomason的一个问题。我们也有些令人惊讶地证明，鉴于任何树，有任何树木，都有一个triangle-tree，因此将图形添加出来的图形仍然是一个常见的the t t t he t t t he the the pordant pordant and pordant tee pordant and perdant and perdant teartant toverant pordant toverant pordant thow teartant toverant toverant toverant toverant tolant toverant。此外，我们表明，将任意的许多顶点顶点添加到最多五个顶点上的任何连接的两部分图形上，都会给出一个共同的图形。
A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph is minimised by the random colouring. Burr and Rosta, extending a famous conjecture by Erdos, conjectured that every graph is common. The conjectures by Erdos and by Burr and Rosta were disproved by Thomason and by Sidorenko, respectively, in the late 1980s. Collecting new examples for common graphs had not seen much progress since then, although very recently, a few more graphs are verified to be common by the flag algebra method or the recent progress on Sidorenko's conjecture. Our contribution here is to give a new class of tripartite common graphs. The first example class is so-called triangle-trees, which generalises two theorems by Sidorenko and answers a question by Jagger, Šťovíček, and Thomason from 1996. We also prove that, somewhat surprisingly, given any tree T, there exists a triangle-tree such that the graph obtained by adding T as a pendant tree is still common. Furthermore, we show that adding arbitrarily many apex vertices to any connected bipartite graph on at most five vertices give a common graph.
