tailieunhanh - Báo cáo toán học: "Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold"

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í toán học quốc tế đề tài: Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold. | Multicoloured Hamilton cycles in random graphs an anti-Ramsey threshold. Colin Cooper School of Mathematical Sciences University of North London London N7 8DB . Alan Frieze Department of Mathematics Carnegie Mellon University PittsbUrgh PA15213 . Submitted August 25 1995 Accepted October 1 1995 Abstract Let the edges of a graph G be coloured so that no colour is used more than k times. We refer to this as a k-bounded colouring. We say that a subset of the edges of G is multicoloured if each edge is of a different colour. We say that the colouring is H-good if a multicoloured Hamilton cycle exists . one with a multicoloured edge-set. Let ARk G every k-bounded colouring of G is H-good . We establish the threshold for the random graph Gn m to be in ARk. Research carried out whilst visiting Carnegie Mellon University tSupported by NSF grant CCR-9225008 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 2 1995 R19 2 1 Introduction As usual let Gn m be the random graph with vertex set V n and m random edges. Let m n log n log log n Cn 2. Komlos and Szemeredi 14 proved that if A e c then lim Pr Gnmis Hamiltonian nu v 7 0 Cn - 1 e x Cn - c 1 cn - 1 which is limn 1 Pr Gnm 2 where s refers to minimum degree. This result has been generalised in a number of directions. Bollobás 3 proved a hitting time version see also Ajtai Komlos and Szemeredi 1 Bollobás Fenner and Frieze 6 proved an algorithmic version Bollobás and Frieze 5 found the threshold for k 2 edge disjoint Hamilton cycles Bollobás Fenner and Frieze 7 found a threshold when there is a minimum degree condition Cooper and Frieze 9 Luczak 15 and Cooper 8 discussed pancyclic versions Cooper and Frieze 10 estimated the number of distinct Hamilton cycles at the threshold. In quite unrelated work various researchers have considered the following problem Let the edges of a graph G be coloured so that no colour is used more than k times. We refer to this as a k-bounded colouring. We say that a subset of the edges of G is .