Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Loose Hamilton Cycles in Random Uniform Hypergraphs. | Loose Hamilton Cycles in Random Uniform Hypergraphs Andrzej Dudek and Alan Frieze Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA 15213 Submitted Jun 9 2010 Accepted Jan 29 2011 Published Feb 21 2011 Mathematics Subject Classifications 05C80 05C65 Abstract In the random k-uniform hypergraph Hn p k of order n each possible k-tuple appears independently with probability p. A loose Hamilton cycle is a cycle of order n in which every pair of adjacent edges intersects in a single vertex. We prove that if pnk-1 log n tends to infinity with n then hm Fr Hra p fc contains a loose Hamilton cycle 1. 2 fc-1 n This is asymptotically best possible. 1 Introduction The threshold for the existence of Hamilton cycles in the random graph Gn p has been known for many years see . 1 3 and 9 . There have been many generalizations of these results over the years and the problem is well understood. It is natural to try to extend these results to hypergraphs and this has proven to be difficult. The famous Posa lemma fails to provide any comfort and we must seek new tools. In the graphical case Hamilton cycles and perfect matchings go together and our approach will be to build on the deep and difficult result of Johansson Kahn and Vu 8 as well as what we have learned from the graphical case. A k-uniform hypergraph is a pair V E where E c p . In the random k-uniform hypergraph Hn p k of order n each possible k-tuple appears independently with probability p. We say that a k-uniform hypergraph V E is a loose Hamilton cycle if there exists a cyclic ordering of the vertices V such that every edge consists of k consecutive Supported in part by NSF grant CCF0502793. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P48 1 vertices and every pair of consecutive edges intersects in a single vertex. In other words a loose Hamilton cycle has the minimum possible number of edges among all cycles on V vertices. In a recent paper the second author proved the following Theorem
