← All problems

Aharoni–Howard rainbow matching conjecture

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
  1. 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.