2016/11/01 by Han, Jie, Zang, Chuanyun, Zhao, Yi
#05C65 #05C70 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1611.00290
For k≥ 3 and ε>0, let H be a k-partite k-graph with parts V1,…, Vk each of size n, where n is sufficiently large. Assume that for each i∈ [k], every (k-1)-set in ∏_j∈ [k]∖ \i\ Vi lies in at least ai edges, and a1≥ a2≥ ⋯ ≥ ak. We show that if a1, a2≥ εn, then H contains a matching of size min\n-1, ∑i∈ [k]ai\. In particular, H contains a matching of size n-1 if each crossing (k-1)-set lies in at least \lceil n/k \rceil edges, or each crossing (k-1)-set lies in at least \lfloor n/k \rfloor edges and n≡ 1\bmod k. This special case answers a question of Rödl and Ruciński and was independently obtained by Lu, Wang, and Yu. The proof of Lu, Wang, and Yu closely follows the approach of Han [Combin. Probab. Comput. 24 (2015), 723--732] by using the absorbing method and considering an extremal case. In contrast, our result is more general and its proof is thus more involved: it uses a more complex absorbing method and deals with two extremal cases.