A note on randomly colored matchings in random bipartite graphs

2019/07/22 by Alan Frieze, Frieze, Alan
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1907.09405

openalex publication_date 2019/07/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁,c₂,…,c_q$. Let Q_i=\sete∈ E(G):c(e)=c_i, where c(e) denotes the color of e. The perfect matching color profile mcp(G) is defined to be the set of vectors (m₁,m₂,…,m_q)∈ [n]^q such that there exists a perfect matching M such that |M∩ Q_i|=m_i. We give bounds on the matching color profile for a randomly colored random bipartite graph.

Related

• Matchings with Prescribed Color Counts
• Perfect Matchings in Inhomogeneous Random Bipartite Graphs in Random Environment
• Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs
• Rainbow Matchings: existence and counting
• Coloured and Dependent Planar Matchings of Random Bipartite Graphs