Matching problems in hypergraphs
Abstract
Kühn, Osthus, and Treglown and, independently, Khan proved that if H is a 3uniform hypergraph on n vertices, where n is a multiple of 3 and large, and the minimum vertex degree of H is greater than {(n1) choose 2}  {2n/3 choose 2}, then H contains a perfect matching.
We show that for sufficiently large n divisible by 3, if F_1, ..., F_{n/3} are 3uniform hypergraphs with a common vertex set and the minimum vertex degree in each F_i is greater than {(n1) choose 2}  {2n/3 choose 2} for i = 1, ..., n/3, then the family {F_1, ..., F_{n/3}} admits a rainbow matching, i.e., a matching consisting of one edge from each F_i. This is done by converting the rainbow matching problem to a perfect matching problem in a special class of uniform hypergraphs.
We also prove that, for any integers k, l with k >= 3 and k/2 < l <= k1, there exists a positive real μ such that, for all sufficiently large integers m, n satisfying n/k  μn <= m <= n/k  1  (1  l/k){ceil of (k  l)/(2l  k)}, if H is a kuniform hypergraph on n vertices and the minimum ldegree of H is greater than {(nl) choose (kl)}  {(nlm) choose (kl)}, then H has a matching of size m+1. This improves upon an earlier result of Hàn, Person, and Schacht for the range k/2 < l <= k1. In many cases, our result gives tight bound on the minimum ldegree of H for near perfect matchings. For example, when l >= 2k/3, n ≡ r (mod k), 0 <= r < k, and r + l >= k, we can take m to be the minimum integer at least n/k  2.
Collections
Related items
Showing items related by title, author, creator and subject.

Broadband matching between arbitrary load and source impedances
Fielder, Daniel Curtis (Georgia Institute of Technology, 195708) 
Distributive lattices, stable matchings, and robust solutions
Mai, Tung (Georgia Institute of Technology, 20180518)The stable matching problem, first presented by mathematical economists Gale and Shapley, has been studied extensively since its introduction. As a result, a remarkably rich literature on the problem has accumulated in ... 
Probabilistic Structure Matching for Visual SLAM with a MultiCamera Rig
Kaess, Michael; Dellaert, Frank (Georgia Institute of TechnologyElsevier, 201002)We propose to use a multicamera rig for simultaneous localization and mapping (SLAM), providing flexibility in sensor placement on mobile robot platforms while exploiting the stronger localization constraints provided ...