Aharoni–Howard rainbow matching conjecture

Let H1,,HkH_1,\dots,H_k be rr-uniform hypergraphs on the same set of nn vertices. Define f(n,r,k)f(n,r,k) to be the smallest mm such that every rr-uniform hypergraph on nn vertices with mm edges has a matching of size kk.

Aharoni–Howard's conjecture. If each HiH_i has f(n,r,k)f(n,r,k) hyperedges, then there is a rainbow matching

{e1,,ek},eiE(Hi) for i=1,,k.\{e_1,\dots,e_k\},\qquad e_i\in E(H_i)\text{ for }i=1,\dots,k.

This is a rainbow version of the Erdős–Ko–Rado matching threshold. It is proved for balanced rr-partite hypergraphs when r=3r=3, while the general statement remains open.

Sources & referencesView supporting material

Primary source

Ron Aharoni, Matt DeVos, Sebastián González Hermosillo de la Maza, Amanda Montejano and Robert Šámal, “A rainbow version of Mantel's Theorem”, arXiv:1812.11872 (2020).

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.