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.