Dirac's theorem states that any n-vertex graph G with even integer n satisfying δ(G) ≥ n/2 contains a perfect matching. We generalize this to k-uniform linear hypergraphs by proving the following. Any n-vertex k-uniform linear hypergraph H with minimum degree at least n/k + Ω(1) contains a matching that covers at least $(1-o(1))n$ vertices. This minimum degree condition is asymptotically tight and obtaining perfect matching is impossible with any degree condition. Furthermore, we show that if δ(H) ≥ (1/k+o(1))n, then H contains almost spanning linear cycles, almost spanning hypertrees with $o(n)$ leaves, and ``long subdivisions'' of any o(√n)-vertex graphs.
No takes yet. Share an insight, caveat, or question.
Im et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: