Degree Conditions for Matchability in 3‐Partite Hypergraphs. Issue 1 (28th February 2017)

• Record Type: Journal Article
• Authors: Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran
• Is Part Of: Journal of graph theory. Volume 87:Issue 1(2018)
• Page Start: 61
• Page End: 71
• Publication Date: 2017-02-28
• Subjects: matchings -- 3‐partite hypergraphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22140
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: We study conjectures relating degree conditions in 3‐partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of 2 n − 1 matchings of size n in a bipartite graph has a partial rainbow matching of size n . We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every n × n Latin square has a generalized diagonal (set of n entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row‐Latin.