A note on randomly colored matchings in random bipartite graphs

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}, l d o t s, c_{q}

. Let

Q_{i} = s e t e i n E (G) : c (e) = c_{i}

, where

c (e)

denotes the color of

e

. The perfect matching color profile

m c p (G)

is defined to be the set of vectors

(m_{1}, m_{2}, l d o t s, m_{q}) i n [n]^{q}

such that there exists a perfect matching

M

such that

| M c a p Q_{i} | = m_{i}

. We give bounds on the matching color profile for a randomly colored random bipartite graph.

Recommendations

Cited In (6)

This page was built for publication: A note on randomly colored matchings in random bipartite graphs