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.
Original language | English |
---|---|
Pages (from-to) | 499-514 |
Number of pages | 16 |
Journal | Random Structures and Algorithms |
Volume | 54 |
Issue number | 3 |
Early online date | 8 Sept 2018 |
DOIs | |
Publication status | Published - 1 May 2019 |
Keywords
- Hamilton cycles
- digraphs
- packing