Ramsey Multiplicity of Apices of Trees
Abstract
Abstract. A graph [Formula: see text] is common if its Ramsey multiplicity, i.e., the minimum number of monochromatic copies of [Formula: see text] contained in any 2-edge-coloring of [Formula: see text], is asymptotically the same as the number of monochromatic copies in the random 2-edge-coloring of [Formula: see text]. Erdős conjectured that every complete graph is common, which was disproved by Thomason in the 1980s. Until today, a classification of common graphs remains a wide open and challenging problem. Grzesik et al. [ Combin. Probab. Comput., 31 (2022), 907–923] conjectured that every [Formula: see text]-apex of any connected Sidorenko graph is common. We prove for [Formula: see text] that the [Formula: see text]-apex of any tree is common.
Fields of Study & Subjects
Advanced Topology and Set Theory
Limits and Structures in Graph Theory
Publication details
- Journal / source
- SIAM Journal on Discrete Mathematics
- Publisher
- Society for Industrial & Applied Mathematics (SIAM)
- Volume
- 40
- Issue
- 2
- Pages
- 889–896
- Publication date
- 4 June 2026
- Language
- EN