Skip to main content
Journal cover image

Discrepancy properties for random regular digraphs

Publication ,  Journal Article
Cook, NA
Published in: Random Structures and Algorithms
January 1, 2017

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

Random Structures and Algorithms

DOI

EISSN

1098-2418

ISSN

1042-9832

Publication Date

January 1, 2017

Volume

50

Issue

1

Start / End Page

23 / 58

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

APA
Chicago
ICMJE
MLA
NLM
Cook, N. A. (2017). Discrepancy properties for random regular digraphs. Random Structures and Algorithms, 50(1), 23–58. https://doi.org/10.1002/rsa.20643
Cook, N. A. “Discrepancy properties for random regular digraphs.” Random Structures and Algorithms 50, no. 1 (January 1, 2017): 23–58. https://doi.org/10.1002/rsa.20643.
Cook NA. Discrepancy properties for random regular digraphs. Random Structures and Algorithms. 2017 Jan 1;50(1):23–58.
Cook, N. A. “Discrepancy properties for random regular digraphs.” Random Structures and Algorithms, vol. 50, no. 1, Jan. 2017, pp. 23–58. Scopus, doi:10.1002/rsa.20643.
Cook NA. Discrepancy properties for random regular digraphs. Random Structures and Algorithms. 2017 Jan 1;50(1):23–58.
Journal cover image

Published In

Random Structures and Algorithms

DOI

EISSN

1098-2418

ISSN

1042-9832

Publication Date

January 1, 2017

Volume

50

Issue

1

Start / End Page

23 / 58

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