Aharoni–Howard conjecture on rainbow matchings

About 10 years old · traced to

For a positive integer nn, write [n]={1,…,n}[n]=\{1,\ldots,n\}, and let ([n]k)\binom{[n]}{k} be the family of kk-subsets of [n][n]. Let F={F1,…,Ft}\mathcal F=\{F_1,\ldots,F_t\} be a family of subsets of ([n]k)\binom{[n]}{k}, and call a set of pairwise disjoint edges, one from each FiF_i, a rainbow matching. Aharoni–Howard conjecture. If

e(Fi)>max⁡{(nk)−(n−t+1k),(kt−1k)}e(F_i)>\max\left\{\binom{n}{k}-\binom{n-t+1}{k},\binom{kt-1}{k}\right\}

for every 1≤i≤t1\le i\le t, then F\mathcal F admits a rainbow matching. This is the family version of the Erdős matching conjecture and seeks a sharp edge-density condition guaranteeing a rainbow matching; the source provides no evidence of resolution.

References

Primary source

Hongliang Lu, Yan Wang and Xingxing Yu, “A better bound on the size of rainbow matchings”, arXiv:2004.12561 (2021).

Additional references

2 papers in this index state this conjecture (2016–2020). The statement above is taken from the most recent of them; the others are arXiv:1611.01735.

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.