Grinblat's conjecture on rainbow matchings in (n,v)(n,v)-multigraphs

An (n,v)(n,v)-multigraph is an nn-edge-coloured multigraph in which the edges of each colour span a disjoint union of non-trivial cliques whose total number of vertices is at least vv. Let v(n)v(n) be the minimum integer vv such that every (n,v)(n,v)-multigraph contains a rainbow matching of size nn. Grinblat's conjecture. For all n4n\geq 4,

v(n)=3n2.v(n)=3n-2.

This problem generalises rainbow matching questions such as the bipartite Aharoni–Berger conjecture and arose from Grinblat's study of algebras of sets; the conjecture remains open here.

Sources & referencesView supporting material

Primary source

David Munhá Correia, Alexey Pokrovskiy and Benny Sudakov, “Short proofs of rainbow matching results”, arXiv:2108.07734 (2021).

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.