← All problems

Rainbow Erdős matching conjecture

5 years old · traced to

Let [n]={1,2,…,n}[n]=\{1,2,\dots,n\} and let ([n]k)\binom{[n]}{k} denote the collection of all kk-subsets of [n][n]. Let F1,F2,…,Fs⊆([n]k)\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 Fi∈FiF_i\in\mathcal{F}_i for all 1≤i≤s1\leq i\leq s. Rainbow Erdős matching conjecture. If

∣Fi∣>max⁡{(ks−1k),(nk)−(n−s+1k)}|\mathcal{F}_i|>\max\left\{\binom{ks-1}{k},\binom{n}{k}-\binom{n-s+1}{k}\right\}

for all 1≤i≤s1\leq i\leq s, then F1,F2,…,Fs\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
  1. Let ([n]k)\binom{[n]}{k} denote the family of kk-subsets of [n][n]. Rainbow Erdős Matching Conjecture. If n≥(s+1)kn\geq(s+1)k and F1,…,Fs+1⊆([n]k)\mathcal{F}_1,\dots,\mathcal{F}_{s+1}\subseteq\binom{[n]}{k} have no pairwise disjoint F1,…,Fs+1F_1,\dots,F_{s+1} with Fi∈FiF_i\in\mathcal{F}_i for every ii, then

    min⁡i∈[s+1]∣Fi∣≤max⁡{((s+1)k−1k),(nk)−(n−sk)}.\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
  1. Jian Wang and Jie You, “Extremal Problem for Matchings and Rainbow Matchings on Direct Products”, arXiv:2111.04423 (2021).

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.