Hostname: page-component-f554764f5-qhdkw Total loading time: 0 Render date: 2025-04-12T04:46:38.088Z Has data issue: false hasContentIssue false
  • English
  • Français

A Dirac-Type Theorem for 3-Uniform Hypergraphs

Published online by Cambridge University Press: 03 January 2006

VOJTĚCH RÖDL
Affiliation:
Emory University, Atlanta, GA, USA (e-mail: rodl@mathcs.emory.edu)
ANDRZEJ RUCIŃSKI
Affiliation:
A. Mickiewicz University, Poznań, Poland (e-mail: rucinski@amu.edu.pl)
ENDRE SZEMERÉDI
Affiliation:
Rutgers University, New Brunswick, USA (e-mail: szemered@cs.rutgers.edu)

Abstract

A Hamiltonian cycle in a 3-uniform hypergraph is a cyclic ordering of the vertices in which every three consecutive vertices form an edge. In this paper we prove an approximate and asymptotic version of an analogue of Dirac's celebrated theorem for graphs: for each γ>0 there existsn0 such that every 3-uniform hypergraph on$n\geq n_0$ vertices, in which each pair of vertices belongs to at least$(1/2+\gamma)n$ edges, contains a Hamiltonian cycle.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable