On the anti-Ramsey threshold for non-balanced graphs

DOI10.37236/11449arXiv2201.05106MaRDI QIDQ6131744FDOQ6131744

Authors: Pedro Araújo, Taísa L. Martins, Letícia Mattos, Walner Mendonça, Luiz Moreira, G. O. Mota 

Publication date: 18 April 2024

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For graphs $G$ and $H$, we write $GoversetmathrmrblongrightarrowH$ if any proper edge-coloring of $G$ contains 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)oversetmathrmrblongrightarrowH$ 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 and more complex family of such graphs that includes all the previously known examples.

Full work available at URL: https://arxiv.org/abs/2201.05106

zbMATH Keywords

rainbow copyanti-Ramsey threshold for cycles

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Generalized Ramsey theory (05C55) Structural characterization of families of graphs (05C75)

Cited In (1)

• Monochromatic graph decompositions inspired by anti-Ramsey colorings

This page was built for publication: On the anti-Ramsey threshold for non-balanced graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131744)