Let [n]=1,2,…,n and let binom[n]k denote the collection of all k-subsets of [n]. Let F_1,F_2,…,F_s⊆binom[n]k. They contain a rainbow matching if there exist pairwise disjoint sets F_i∈F_i for all 1≤ i≤ s. Rainbow Erdős matching conjecture. If |F_i|>maxbinomks-1k,binomnk-binomn-s+1k for all 1≤ i≤ s, then F_1,F_2,…,F_s contain a rainbow matching. This is a proposed rainbow analogue of the Erdős matching conjecture; the general assertion is not established by the context provided.

Rainbow Erdős matching conjecture

About 5 years old · traced to 2021

Let $[n]=\{1,2,\dots,n\}$ and let $\binom{[n]}{k}$ denote the collection of all $k$ -subsets of $[n]$ . Let $\mathcal{F}_1,\mathcal{F}_2,\dots,\mathcal{F}_s\subseteq\binom{[n]}{k}$ . They contain a rainbow matching if there exist pairwise disjoint sets $F_i\in\mathcal{F}_i$ for all $1\leq i\leq s$ . Rainbow Erdős matching conjecture. If

|\mathcal{F}_i|>\max\left\{\binom{ks-1}{k},\binom{n}{k}-\binom{n-s+1}{k}\right\}

for all $1\leq i\leq s$ , then $\mathcal{F}_1,\mathcal{F}_2,\dots,\mathcal{F}_s$ contain a rainbow matching. This is a proposed rainbow analogue of the Erdős matching conjecture; the general assertion is not established by the context provided.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

Rainbow Erdős Matching Conjecture
Let $\binom{[n]}{k}$ denote the family of $k$ -subsets of $[n]$ . Rainbow Erdős Matching Conjecture. If $n\geq(s+1)k$ and $\mathcal{F}_1,\dots,\mathcal{F}_{s+1}\subseteq\binom{[n]}{k}$ have no pairwise disjoint $F_1,\dots,F_{s+1}$ with $F_i\in\mathcal{F}_i$ for every $i$ , then
$\min_{i\in[s+1]}|\mathcal{F}_i|\leq\max\left\{\binom{(s+1)k-1}{k},\binom{n}{k}-\binom{n-s}{k}\right\}.$
This is the multipartite, or rainbow, extension of the Erdős Matching Conjecture; the source gives no resolution status.
source: Jiuqiang Liu, Guihai Yu, Lihua Feng and Yongtao Li, “L-intersecting or Configuration Forbidden Families on Set Systems and Vector Spaces over Finite Fields”, arXiv:2403.04289 (2024).

References

Primary source

Jian Wang and Jie You, “Extremal Problem for Matchings and Rainbow Matchings on Direct Products”, arXiv:2111.04423 (2021).

extremal-set-theory rainbow-matchings

Posted 1 month ago

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.

No solutions have been posted yet.

Rainbow Erdős Matching Conjecture

Primary source

Progress summary