The minimum vertex degree for an almost-spanning tight cycle in a 3-uniform hypergraph

DOI10.1016/J.DISC.2016.12.015zbMATH Open1369.05036arXiv1606.05616OpenAlexW2964098318MaRDI QIDQ2400547FDOQ2400547

Authors: Oliver Cooley, Richard Mycroft 

Publication date: 29 August 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: We prove that any $3$-uniform hypergraph whose minimum vertex degree is at least $$ admits an almost-spanning tight cycle, that is, a tight cycle leaving $o(n)$ vertices uncovered. The bound on the vertex degree is asymptotically best possible. Our proof uses the hypergraph regularity method, and in particular a recent version of the hypergraph regularity lemma proved by Allen, B"ottcher, Cooley and Mycroft.

Full work available at URL: https://arxiv.org/abs/1606.05616

Recommendations

• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• Tight minimum degree condition for the existence of loose cycle tilings in 3-graphs
• Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree

zbMATH Keywords

Hamilton cyclehypergraphvertex degree

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex degrees (05C07) Eulerian and Hamiltonian graphs (05C45) Hypergraphs (05C65)

Cites Work

• On maximal paths and circuits of graphs
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• Some Theorems on Abstract Graphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• Hamiltonian chains in hypergraphs
• Loose Hamilton cycles in 3-uniform hypergraphs of high minimum degree
• On extremal hypergraphs for Hamiltonian cycles
• Regular Partitions of Hypergraphs: Regularity Lemmas
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• An approximate Dirac-type theorem for \(k\)-uniform hypergraphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• Hamilton \(\ell \)-cycles in uniform hypergraphs
• Title not available (Why is that?)
• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Regular Partitions of Hypergraphs: Counting Lemmas
• Loose Hamilton cycles in hypergraphs
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Loose Hamiltonian cycles forced by \((k-2)\)-degree -- approximate version
• Families of triples with high minimum degree are Hamiltonian
• Recent advances on Dirac-type problems for hypergraphs
• Tight cycles and regular slices in dense hypergraphs
• Forbidding Hamilton cycles in uniform hypergraphs
• Tight Codegree Condition for the Existence of Loose Hamilton Cycles in 3-Graphs

Cited In (8)

• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Minimum degree conditions for tight Hamilton cycles
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• The size of minimum 3-trees
• Tight Hamilton cycles in cherry-quasirandom 3-uniform hypergraphs
• Minimum number of vertices of almost 3-regular graphs with given deficiency
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Tight cycles and regular slices in dense hypergraphs

This page was built for publication: The minimum vertex degree for an almost-spanning tight cycle in a 3-uniform hypergraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2400547)