Journal article
Packing and counting arbitrary Hamilton cycles in random digraphs
- Abstract:
- We prove packing and counting theorems for arbitrarily ori-ented Hamilton cycles in (n, p) for nearly optimal p (uptoalogcn factor). In particular, we show that given t =(1−o(1))npHamilton cycles C1, … , Ct, each of which is oriented arbi-trarily, a digraph D ∼ (n, p) w.h.p. contains edge disjointcopies of C1, … , Ct, provided p = (log3n∕n).Wealsoshowthat given an arbitrarily oriented n-vertex cycle C, a randomdigraph D ∼ (n, p) w.h.p. contains (1 ± o(1))n!pncopies ofC, provided p ≥ log1+o(1)n∕n.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 337.2KB, Terms of use)
-
- Publisher copy:
- 10.1002/rsa.20796
Authors
+ European Research Council
More from this funder
- Funding agency for:
- Long, E
- Grant:
- Starter Grant 633509
- Publisher:
- Wiley
- Journal:
- Random Structures and Algorithms More from this journal
- Volume:
- 54
- Issue:
- 3
- Pages:
- 499-514
- Publication date:
- 2018-09-08
- Acceptance date:
- 2018-02-27
- DOI:
- ISSN:
-
1098-2418
- Keywords:
- Pubs id:
-
pubs:827659
- UUID:
-
uuid:f4783349-a931-4449-a296-1f9811535e69
- Local pid:
-
pubs:827659
- Source identifiers:
-
827659
- Deposit date:
-
2018-03-03
Terms of use
- Copyright holder:
- Wiley Periodicals, Inc
- Copyright date:
- 2018
- Notes:
- Copyright © 2018 Wiley Periodicals, Inc. This is the accepted manuscript version of the article. The final version is available online from Wiley at: https://doi.org/10.1002/rsa.20796
If you are the owner of this record, you can report an update to it here: Report update to this record