Extremal Problem for Matchings and Rainbow Matchings on Direct Products

Jian Wang; Jie You

paper

Extremal Problem for Matchings and Rainbow Matchings on Direct Products

arXiv:2111.04423

Abstract

Let $n_{1}, \dots, n_{ℓ}, k_{1}, \dots, k_{ℓ}$ be integers and let $V_{1}, \dots, V_{ℓ}$ be disjoint sets with $∣ V_{i} ∣ = n_{i}$ for $i = 1, \dots, ℓ$ . Define $⊔_{i = 1}^{ℓ} (k _{i} V _{i})$ as the collection of all subsets $F$ of $\cup_{i = 1}^{ℓ} V_{i}$ with $∣ F \cap V_{i} ∣ = k_{i}$ for each $i = 1, \dots, ℓ$ . In this paper, we show that if the matching number of $F \subseteq ⊔_{i = 1}^{ℓ} (k _{i} V _{i})$ is at most $s$ and $n_{i} \geq 4 ℓ^{2} k_{i}^{2} s$ for all $i$ , then $∣ F ∣ \leq max_{1 \leq i \leq ℓ} [(k _{i} n _{i}) - (k _{i} n _{i} - s)] \prod_{j \neq = i} (k _{j} n _{j})$ . Let $F_{1}, F_{2}, \dots, F_{s} \subseteq ⊔_{i = 1}^{ℓ} (k _{i} V _{i})$ with $n_{i} \geq 8 ℓ^{2} k_{i}^{2} s$ for all $i$ . We also prove that if $F_{1}, F_{2}, \dots, F_{s}$ are rainbow matching free, then there exists $t$ in $[s]$ such that $∣ F_{t} ∣ \leq max_{1 \leq i \leq ℓ} [(k _{i} n _{i}) - (k _{i} n _{i} - s + 1)] \prod_{j \neq = i} (k _{j} n _{j}) .$