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,\dots ,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 $\mcp(G)$, which is the set of vectors $(m_1,m_2,\dots ,m_q)\in [n{]}^q$ such that there exists a perfect matching $M$ in $G$ with $|Q_i\cap M|=m_i$ for all $i$. Let $\a_1, \a_2, \ldots, \a_q$ be positive constants such that $\sum_{i=1}^q \a_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 $\mcp(G) = \set{(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}$.

Minor corrections