DMS Combinatorics Seminar

Speaker: Grace McCourt (Iowa State University)

Title: Dirac-type results for Berge cycles in uniform hypergraphs  

Abstract: The famous Dirac Theorem gives an exact bound on the minimum degree of an $n$-vertex graph guaranteeing the existence of a hamiltonian cycle. Dirac also gave a minimum degree bound on the circumference of a graph. Furthermore, he 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 versions of these results in hypergraphs.

 A Berge cycle in a hypergraph is an alternating sequence of distinct vertices and edges $v_1, e_1, 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 bounds on the minimum degree needed to guarantee a Berge cycle of a given length in an $n$-vertex, $r$-uniform hypergraph, and in 2-connected such hypergraphs. The bounds differ depending on the uniformity of the edges and the length of the desired cycle.

This work is joint with Alexandr Kostochka and Ruth Luo.