A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929258727735296 |
|---|---|
| author | Kostochka, Alexandr Luo, Ruth McCourt, Grace |
| author_facet | Kostochka, Alexandr Luo, Ruth McCourt, Grace |
| contents | Dirac proved that each $n$-vertex $2$-connected graph with minimum degree at least $k$ contains a cycle of length at least $\min\{2k, n\}$. We consider a hypergraph version of this result. A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges $v_1,e_2,v_2, \ldots, e_c, v_1$ such that $\{v_i,v_{i+1}\} \subseteq e_i$ for all $i$ (with indices taken modulo $c$). We prove that for $n \geq k \geq r+2 \geq 5$, every $2$-connected $r$-uniform $n$-vertex hypergraph with minimum degree at least ${k-1 \choose r-1} + 1$ has a Berge cycle of length at least $\min\{2k, n\}$. The bound is exact for all $k\geq r+2\geq 5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_14516 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs Kostochka, Alexandr Luo, Ruth McCourt, Grace Combinatorics 05D05, 05C65, 05C38, 05C35 Dirac proved that each $n$-vertex $2$-connected graph with minimum degree at least $k$ contains a cycle of length at least $\min\{2k, n\}$. We consider a hypergraph version of this result. A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges $v_1,e_2,v_2, \ldots, e_c, v_1$ such that $\{v_i,v_{i+1}\} \subseteq e_i$ for all $i$ (with indices taken modulo $c$). We prove that for $n \geq k \geq r+2 \geq 5$, every $2$-connected $r$-uniform $n$-vertex hypergraph with minimum degree at least ${k-1 \choose r-1} + 1$ has a Berge cycle of length at least $\min\{2k, n\}$. The bound is exact for all $k\geq r+2\geq 5$. |
| title | A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs |
| topic | Combinatorics 05D05, 05C65, 05C38, 05C35 |
| url | https://arxiv.org/abs/2212.14516 |