Geodesic
On the anti-Ramsey threshold for non-balanced graphs
Pedro Araújo1 ; Taísa Martins2 ; Letícia Mattos3 ; Walner Mendonça4 ; Luiz Moreira5 ; Guilherme O. Mota6
1Institute of Computer Science of the Czech Academy of Sciences
2Instituto de Matemática, Universidade Federal Fluminense
3Freie Universität Berlin and Berlin Mathematical School (BMS/MATH+)
4IST Austria
5Departamento de Matemática, Universidade Federal de Pernambuco
6Universidade de São Paulo - USP
The electronic journal of combinatorics, Tome 31 (2024) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

For graphs $G,H$, we write $G \overset{\mathrm{rb}}{\longrightarrow} H $ if for every proper edge-coloring of $G$ there is a rainbow copy of $H$, i.e., a copy where no color appears more than once. Kohayakawa, Konstadinidis and the last author proved that the threshold for $G(n,p) \overset{\mathrm{rb}}{\longrightarrow} H$ is at most $n^{-1/m_2(H)}$. Previous results have matched the lower bound for this anti-Ramsey threshold for cycles and complete graphs with at least 5 vertices. Kohayakawa, Konstadinidis and the last author also presented an infinite family of graphs $H$ for which the anti-Ramsey threshold is asymptotically smaller than $n^{-1/m_2(H)}$. In this paper, we devise a framework that provides a richer family of such graphs.
DOI : 10.37236/11449
Classification : 05C80, 05C55, 05C75
Mots-clés : anti-Ramsey threshold for cycles, rainbow copy

Pedro Araújo  1   ; Taísa Martins  2   ; Letícia Mattos  3   ; Walner Mendonça  4   ; Luiz Moreira  5   ; Guilherme O. Mota  6

1 Institute of Computer Science of the Czech Academy of Sciences
2 Instituto de Matemática, Universidade Federal Fluminense
3 Freie Universität Berlin and Berlin Mathematical School (BMS/MATH+)
4 IST Austria
5 Departamento de Matemática, Universidade Federal de Pernambuco
6 Universidade de São Paulo - USP 
@article{10_37236_11449,
     author = {Pedro Ara\'ujo and Ta{\'\i}sa Martins and Let{\'\i}cia Mattos and Walner Mendon\c{c}a and Luiz Moreira and Guilherme O. Mota},
     title = {On the {anti-Ramsey} threshold for non-balanced graphs},
     journal = {The electronic journal of combinatorics},
     year = {2024},
     volume = {31},
     number = {1},
     doi = {10.37236/11449},
     zbl = {1536.05407},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11449/}
}
TY  - JOUR
AU  - Pedro Araújo
AU  - Taísa Martins
AU  - Letícia Mattos
AU  - Walner Mendonça
AU  - Luiz Moreira
AU  - Guilherme O. Mota
TI  - On the anti-Ramsey threshold for non-balanced graphs
JO  - The electronic journal of combinatorics
PY  - 2024
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11449/
DO  - 10.37236/11449
ID  - 10_37236_11449
ER  - 
%0 Journal Article
%A Pedro Araújo
%A Taísa Martins
%A Letícia Mattos
%A Walner Mendonça
%A Luiz Moreira
%A Guilherme O. Mota
%T On the anti-Ramsey threshold for non-balanced graphs
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/11449/
%R 10.37236/11449
%F 10_37236_11449
Pedro Araújo; Taísa Martins; Letícia Mattos; Walner Mendonça; Luiz Moreira; Guilherme O. Mota. On the anti-Ramsey threshold for non-balanced graphs. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/11449

Cité par Sources :