Compatible Hamilton cycles in random graphs1. Issue 3 (15th February 2016)

• Record Type: Journal Article
• Authors: Krivelevich, Michael; Lee, Choongbum; Sudakov, Benny
• Is Part Of: Random structures & algorithms. Volume 49:Issue 3(2016)
• Page Start: 533
• Page End: 557
• Publication Date: 2016-02-15
• Subjects: random graphs -- Hamilton cycles -- incomparability systems -- rainbow cycles; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20636
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: A graph is Hamiltonian if it contains a cycle passing through every vertex. One of the cornerstone results in the theory of random graphs asserts that for edge probability p ≫ log n n, the random graph G ( n, p ) is asymptotically almost surely Hamiltonian. We obtain the following strengthening of this result. Given a graph G = ( V, E ), an incompatibility system ℱ over G is a family ℱ = { F v } v ∈ V where for every v ∈ V, the set F v is a set of unordered pairs F v ⊆ { { e, e ′ } : e ≠ e ′ ∈ E, e ∩ e ′ = { v } } . An incompatibility system is Δ‐bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F v containing e . We say that a cycle C in G is compatible with ℱ if every pair of incident edges e, e ′ of C satisfies { e, e ′ } ∉ F v . This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be used as a quantitative measure of robustness of graph properties. We prove that there is a constant μ > 0 such that the random graph G = G ( n, p ) with p ( n ) ≫ log n n is asymptotically almost surely such that for any μnp ‐bounded incompatibility system ℱ over G, there is a Hamilton cycle in G compatible with ℱ . We also prove that for larger edge probabilities p ( n ) ≫ log 8 n n, the parameter μ can be taken to be any constant smaller than 1 − 1 2 . These results imply in particular that typically in G ( n, p ) for p ≫ log n n, for any edge‐coloring in which each color appears at most μnp times at each vertex, there exists a properly colored Hamilton cycle. Furthermore, our proof can be easily modified to show that for any edge‐coloring of such a random graph in which each color appears on at most μnp edges, there exists a Hamilton cycle in which all edges have distinct colors (i.e., a rainbow Hamilton cycle). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 533–557, 2016