Dirac's theorem for linear hypergraphs
| Autor: | Im, Seonghyuk, Lee, Hyunwoo |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Dirac's theorem states that any $n$-vertex graph $G$ with even integer $n$ satisfying $\delta(G) \geq 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 $\frac{n}{k} + \Omega(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 $\delta(H) \geq (\frac{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(\sqrt{n})$-vertex graphs. Comment: 13 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|