Conjecture on rainbow perfect matching packings in random bipartite graphs

Let nn be a positive integer, let pp satisfy

p=ω(lognn),p=\omega\left(\frac{\log n}{n}\right),

and let Gc(Kn,n,p)\mathcal{G}_c(K_{n,n},p) denote the random graph on the complete bipartite graph Kn,nK_{n,n} whose present edges receive a random edge-coloring with cc colors. A matching is rainbow if all its edges have distinct colors. Rainbow perfect matching packing conjecture. There exists c=(1+o(1))nc=(1+o(1))n such that, with high probability, a graph HGc(Kn,n,p)H\sim\mathcal{G}_c(K_{n,n},p) contains (1o(1))np(1-o(1))np edge-disjoint rainbow perfect matchings. This conjecture proposes asymptotically optimal parameters for packing rainbow perfect matchings, improving the proved bound with c=3nc=3n and (1o(1))np/6(1-o(1))np/6 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.