Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

12-3-2020

Journal or Book Title

arXiv

Abstract

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.

Comments

This preprint is made available through arXiv: https://arxiv.org/abs/2012.02057.

Creative Commons License

Creative Commons Attribution 4.0 License
This work is licensed under a Creative Commons Attribution 4.0 License.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Download

Share

COinS