The ACO Seminar (2023–2024)

The multicolored random graph $G_c(n,p)$ is obtained by coloring each edge in $G(n,p)$ independently uniformly at random by one of $c$ colors. A subgraph of $G_c(n,p)$ is called rainbow if no two edges in the subgraph have the same color. A major focus of probabilistic combinatorics is to find the threshold for particular subgraphs to appear in $G(n,p)$; analogously, in $G_c(n,p)$, we study the threshold for a rainbow copy of particular subgraphs to appear. In this talk, I will present some results regarding rainbow thresholds, including when the subgraph in question is a large tree or a power of a Hamiltonian cycle. Joint work with Alan Frieze.