Premium
The union of two random permutations does not have a directed Hamilton cycle
Author(s) -
Cooper Colin
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/1098-2418(200101)18:1<95::aid-rsa7>3.0.co;2-8
Subject(s) - struct , mathematics , frieze , combinatorics , discrete mathematics , computer science , history , art history , programming language
We prove that the union of two random permutations does not usually contain a directed Hamilton cycle. This answers a question posed by Frieze [Random Struct 11 (2000), 000–000]. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 95–98, 2001