The solution and applications of a combinatorial problem

In this paper, we solve the following combinatorial problem. Let A1,A2,…,ApA1,A2,…,Ap be given sets and B1,B2,…,BqB1,B2,…,Bq be mm-sets. We lower bound the number qq of sets B1,B2,…,BqB1,B2,…,Bq such that ⋃i=1pAi⊆⋃i=1qBi and, for each i∈{1,2,…,q}i∈{1,2,…,q}, the set BiBi does not contain two distinct elements xx and yy with x∈Ajx∈Aj, y∈Aky∈Ak and j≠kj≠k. Our result directly implies the theorems proved by Bessy et al. [S. Bessy, N. Lichiardopol, J.-S. Sereni, Two proofs of the Bermond–Thomassen conjecture for tournaments with bounded minimum in-degree, Discrete Math. 310 (3) (2010) 557–560].