The Threshold for the Full Perfect Matching Color Profile in a Random Coloring of Random Graphs

Abstract

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, Frieze defined a notion of the perfect matching color profile denoted by $\mathrm{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 $\mathrm{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}$.