2024/03/23 by Kráľ, Daniel, Krnc, Matjaž, Lamaison, Ander
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.15808
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 Kn, is asymptotically the same as the number of monochromatic copies in the random 2-edge-coloring of Kn. Erdő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ý 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.