A note on randomly colored matchings in random bipartite graphs

Alan Frieze

paper

A note on randomly colored matchings in random bipartite graphs

arXiv:1907.09405

Abstract

We are given a bipartite graph that contains at least one perfect matching and where each edge is colored from a set $Q=\{c_1,c_2,\ldots,c_q}\$. Let $Q_i=\set{e\in E(G):c(e)=c_i} $, w h er e$ c(e) $d e n o t es t h eco l or o f$ e $. T h e p er f ec t ma t c hin g co l or p r o f i l e$ mcp(G) $i s d e f in e d t o b e t h ese t o f v ec t or s$ (m_1,m_2,\ldots,m_q)\in [n]^q $s u c h t ha tt h er ee x i s t s a p er f ec t ma t c hin g$ M $s u c h t ha t$ |M\cap Q_i|=m_i$. We give bounds on the matching color profile for a randomly colored random bipartite graph.