The threshold for the full perfect matching color profile in a random coloring of random graphs (Q2223476)

Summary: Consider a graph \(G\) with a coloring of its edge set \(E(G)\) from a set \(Q = \{c_1,c_2, \ldots, c_q\}\). Let \(Q_i\) be the set of all edges colored with \(c_i\). Recently, \textit{A. M. Frieze} [``A note on randomly colored matchings in random graphs'', Discrete Mathematics and Applications, Springer Optim. Appl. 165, 199--205 (2020)] defined a notion of the perfect matching color profile denoted by \(\text{mcp}(G)\), which is the set of vectors \((m_1, m_2, \ldots, m_q)\) such that there exists a perfect matching \(M\) in \(G\) with \(|Q_i \cap M| = m_i\) for all \(i\). Let \(\alpha_1, \alpha_2, \ldots, \alpha_q\) be positive constants such that \(\sum_{i=1}^q \alpha_i = 1\). Let \(G\) be the random bipartite graph \(G_{n,n,p} \). Suppose the edges of \(G\) are independently colored with color \(c_i\) with probability \(\alpha_i\). We determine the threshold for the event \(\text{mcp}(G) = \{(m_1, \ldots, m_q) \in [0,n]^q : m_1 + \cdots + m_q = n\},\) answering a question posed by Frieze. We further extend our methods to find the threshold for the same event in a randomly colored random graph \(G_{n,p}\).