Geodesic
Rainbow common graphs must be forests
Yihang Sun1
1Massachusetts Institute of Technology
The electronic journal of combinatorics, Tome 32 (2025) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study the rainbow version of the graph commonness property: a graph $H$ is $r$-rainbow common if the number of rainbow copies of $H$ (where all edges have distinct colors) in an $r$-coloring of edges of $K_n$ is maximized asymptotically by independently coloring each edge uniformly at random. $H$ is $r$-rainbow uncommon otherwise. We show that if $H$ has a cycle, then it is $r$-rainbow uncommon for every $r$ at least the number of edges of $H$. This generalizes a result of Erdős and Hajnal, and proves a conjecture of De Silva, Si, Tait, Tunçbilek, Yang, and Young.
DOI : 10.37236/12594
Classification : 05C15, 05D10, 05C80, 05D40
Mots-clés : rainbow common, rainbow uncommon, extremal graph theory, probability method

Yihang Sun  1

1 Massachusetts Institute of Technology 
@article{10_37236_12594,
     author = {Yihang Sun},
     title = {Rainbow common graphs must be forests},
     journal = {The electronic journal of combinatorics},
     year = {2025},
     volume = {32},
     number = {3},
     doi = {10.37236/12594},
     zbl = {8097635},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/12594/}
}
TY  - JOUR
AU  - Yihang Sun
TI  - Rainbow common graphs must be forests
JO  - The electronic journal of combinatorics
PY  - 2025
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/12594/
DO  - 10.37236/12594
ID  - 10_37236_12594
ER  - 
%0 Journal Article
%A Yihang Sun
%T Rainbow common graphs must be forests
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/12594/
%R 10.37236/12594
%F 10_37236_12594
Yihang Sun. Rainbow common graphs must be forests. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/12594

Cité par Sources :