Tight cycles in hypergraphs

Allen, PeterORCID logo; Böttcher, JuliaORCID logo; Cooley, Oliver; and Mycroft, Richard (2015) Tight cycles in hypergraphs. In: European Conference on Combinatorics, Graph Theory and Applications, 2015-08-31 - 2015-09-04, Bergen,Norway,NOR. (Submitted)
Copy

We apply a recent version of the Strong Hypergraph Regularity Lemma(see [1], [2]) to prove two new results on tight cycles in k-uniform hypergraphs. The first result is an extension of the Erdos-Gallai Theorem for graphs: For every > 0, every sufficiently large k-uniform hypergraph on n vertices with at least edges contains a tight cycle of length @n for any @ 2 [0; 1]. Our second result concerns k-partite k-uniform hypergraphs with partition classes of size n and for each @ 2 (0; 1) provides an asymptotically optimal minimum codegree requirement for the hypergraph to contain a cycle of length @kn.


picture_as_pdf

Download

Atom BibTeX OpenURL ContextObject in Span OpenURL ContextObject Dublin Core MPEG-21 DIDL Data Cite XML EndNote HTML Citation METS MODS RIOXX2 XML Reference Manager Refer ASCII Citation
Export

Downloads