Pinnable rainbow matching conjecture

About 3 years old · traced to

Let H=(H1,…,Hm)\mathcal{H}=(H_1,\ldots,H_m) be a family of rr-uniform hypergraphs. A rainbow matching is a matching containing at most one edge from each HiH_i, and νR(H)\nu_R(\mathcal{H}) is its maximum size. Assume that ⋃i=1mHi\bigcup_{i=1}^mH_i is pinnable, meaning that some set meets every edge of the union in exactly one vertex.

Pinnable rainbow matching conjecture. If

τ(⋃i∈IHi)>(2r−2)(∣I∣−1)\tau\left(\bigcup_{i\in I}H_i\right)>(2r-2)(|I|-1)

for every I⊆[m]I\subseteq[m], then H\mathcal{H} has a full rainbow matching:

νR(H)=m.\nu_R(\mathcal{H})=m.

This strengthens the earlier rainbow matching conjecture by replacing the common partite structure with pinnability. It remains open.

References

Primary source

Ron Aharoni, Eli Berger, Joseph Briggs, He Guo and Shira Zerbib, “Looms”, arXiv:2309.03735 (2024).

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.