Packing and counting arbitrary Hamilton cycles in random digraphs

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • MIT

Abstract

We prove packing and counting theorems for arbitrarilyoriented Hamilton cycles in D(n, p) for nearly optimal p (up to a logcnfactor). In particular, we show that given t = (1−o(1))np Hamilton cycles C1,…,Ct, each of which is oriented arbitrarily, a digraph D ∼D(n, p) w.h.p. contains edge disjoint copies of C1,…,Ct, provided p = ω(log3n∕n). We also show that given anarbitrarily oriented n-vertex cycle C, a random digraph D ∼D(n, p) w.h.p. contains (1 ± o(1))n!pn copies of C,provided p ≥ log1+o(1)n∕n. 

Details

Original languageEnglish
Pages (from-to)499-514
Number of pages16
JournalRandom Structures and Algorithms
Volume54
Issue number3
Early online date8 Sep 2018
Publication statusPublished - 1 May 2019

Keywords

  • Hamilton cycles, digraphs, packing