
Discrepancy properties for random regular digraphs
For the uniform random regular directed graph we prove concentration inequalities for (1) codegrees and (2) the number of edges passing from one set of vertices to another. As a consequence, we can deduce discrepancy properties for the distribution of edges essentially matching results for Erdős–Rényi digraphs obtained from Chernoff-type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee in (Chatterjee, Probab Theory and Relat Fields 138 (2007), 305–321). Exchangeable pairs are constructed using two involutions on the set of regular digraphs: a well-known “simple switching” operation, as well as a novel “reflection” operation. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 23–58, 2017.
Duke Scholars
Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0104 Statistics
- 0101 Pure Mathematics
Citation

Published In
DOI
EISSN
ISSN
Publication Date
Volume
Issue
Start / End Page
Related Subject Headings
- Computation Theory & Mathematics
- 4904 Pure mathematics
- 4901 Applied mathematics
- 4613 Theory of computation
- 0802 Computation Theory and Mathematics
- 0104 Statistics
- 0101 Pure Mathematics