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 3-Uniform Hypergraphs. | Loose Hamilton Cycles in Random 3-Uniform Hypergraphs Alan Frieze Submitted Mar 30 2010 Accepted May 19 2010 Published May 25 2010 Mathematics Subject Classification 05C65 05C80 Abstract In the random hypergraph H Hn p 3 each possible triple appears independently with probability p. A loose Hamilton cycle can be described as a sequence of edges xi yi Xi i for i 1 2 . n 2 where X1 X2 . Xn 2 yi y2 . yn 2 are all distinct. We prove that there exists an absolute constant K 0 such that if p KJ -n then n2 lirn Fr Hn p 3 contains a loose Hamilton cycle 1. 4 n 1 Introduction The threshold for the existence of Hamilton cycles in the random graph Gn p has been known for many years see 7 1 and 3 . There have been many generalisations 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 6 as well as what we have learned from the graphical case. A k-uniform Hypergraph is a pair H V E where E c Q . We say that a k-uniform sub-hypergraph C of H is a Hamilton cycle of type Ế for some 1 I k if there exists a cyclic ordering of the vertices V such that every edge consists of k consecutive vertices Department of Mathematical Sciences Carnegie Mellon University Pittsburgh PA15213 . Supported in part by NSF grant DMS-0753472. THE ELECTRONIC JOURNAL OF COMBINATORICS 17 2010 N28 1 and for every pair of consecutive edges Ei-1 iEi in C in the natural ordering of the edges we have Ei-1 Ei . When I k 1 we say that C is a loose Hamilton cycle and in this paper we will restrict our attention to loose Hamilton cycles in the random 3-uniform hypergraph H Hnp .3. In this hypergraph V n and each of the n possible edges triples appears .
