Discrepancy Properties for Random Regular Digraphs

作者：Cook Nicholas A^*

来源：Random Structures and Algorithms, 2017, 50(1): 23-58.

DOI：10.1002/rsa.20643

• random regular graph
• discrepancy property
• concentration of measure
• method of exchangeable pairs

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 Erdos-Renyi 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.

• 出版日期2017-1