Packing and counting arbitrary Hamilton cycles in random digraphs

Asaf Ferber, Eoin Long

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
86 Downloads (Pure)

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 languageEnglish
Pages (from-to)499-514
Number of pages16
JournalRandom Structures and Algorithms
Volume54
Issue number3
Early online date8 Sep 2018
DOIs
Publication statusPublished - 1 May 2019

Keywords

  • Hamilton cycles
  • digraphs
  • packing

Fingerprint

Dive into the research topics of 'Packing and counting arbitrary Hamilton cycles in random digraphs'. Together they form a unique fingerprint.

Cite this