Aharoni–Howard rainbow matching conjecture

About 8 years old · traced to

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},ei∈E(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.

References

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.