Conjecture on rainbow perfect matching packings in random bipartite graphs
Conjecture on rainbow perfect matching packings in random bipartite graphs
Let be a positive integer, let satisfy
and let denote the random graph on the complete bipartite graph whose present edges receive a random edge-coloring with colors. A matching is rainbow if all its edges have distinct colors. Rainbow perfect matching packing conjecture. There exists such that, with high probability, a graph contains edge-disjoint rainbow perfect matchings. This conjecture proposes asymptotically optimal parameters for packing rainbow perfect matchings, improving the proved bound with and matchings; its status is not resolved in the supplied source.
Sources & referencesView supporting material
Primary source
Asaf Ferber, Gal Kronenberg, Frank Mousset and Clara Shikhelman, “Packing a randomly edge-colored random graph with rainbow k-outs”, arXiv:1410.1803 (2014).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.