A graph H is common if its Ramsey multiplicity, i.e., the minimum number of monochromatic copies of H contained in any $2$-edge-coloring of Kₙ, is asymptotically the same as the number of monochromatic copies in the random $2$-edge-coloring of Kₙ. Erd{o}s conjectured that every complete graph is common, which was disproved by Thomason in the 1980s. Till today, a classification of common graphs remains a widely open challenging problem. Grzesik, Lee, Lidick\'y and Volec [Combin. Prob. Comput. 31 (2022), 907--923] conjectured that every k-apex of any connected Sidorenko graph is common. We prove for k≤ 5 that the k-apex of any tree is common.
No takes yet. Share an insight, caveat, or question.
Král͏̌ et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: