Discrepancy properties for random regular digraphs
From MaRDI portal
Abstract: 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 ErdH{o}s-R'enyi digraphs obtained from Chernoff-type bounds. The proofs make use of the method of exchangeable pairs, developed for concentration of measure by Chatterjee. 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.
Recommendations
- Discrepancy of random graphs and hypergraphs
- Properties of random difference graphs
- Matrix and discrepancy view of generalized random and quasirandom graphs
- The Phase Transition of Discrepancy in Random Hypergraphs
- The spectral gap of random regular graphs
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Dirac's theorem for random regular graphs
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- The diameter of randomly perturbed digraphs and some applications
- Discrepancy in graphs and hypergraphs
Cites work
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Asymptotic enumeration by degree sequence of graphs of high degree
- Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
- Asymptotic enumeration of 0-1 matrices with equal row sums and equal column sums
- Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums
- Expander graphs and their applications
- Functional limit theorems for random regular graphs
- scientific article; zbMATH DE number 1033851 (Why is no real title available?)
- scientific article; zbMATH DE number 3249395 (Why is no real title available?)
- List coloring of random and pseudo-random graphs
- On the singularity of adjacency matrices for random regular digraphs
- Optimal Construction of Edge-Disjoint Paths in Random Graphs
- Quasi-random graphs
- Random regular graphs of high degree
- Random Regular Graphs: Asymptotic Distributions and Contiguity
- Some problems in the enumeration of labelled graphs
- Sparse random graphs: eigenvalues and eigenvectors
- Sparse regular random graphs: spectral density and eigenvectors
- Stein's method for concentration inequalities
- The asymptotic number of labeled graphs with given degree sequences
- The expected eigenvalue distribution of a large regular graph
Cited in
(12)- The spectral gap of dense random regular graphs
- The smallest singular value of a shifted d-regular random square matrix
- Size biased couplings and the spectral gap for random regular graphs
- Circular law for the sum of random permutation matrices
- Exchangeable pairs, switchings, and random regular graphs
- The circular law for random regular digraphs
- The sparse circular law under minimal assumptions
- Discrepancy inequalities for directed graphs
- On the counting problem in inverse Littlewood-Offord theory
- The circular law for random regular digraphs with random edge weights
- Structure of eigenvectors of random regular digraphs
- On the second eigenvalue of random bipartite biregular graphs
This page was built for publication: Discrepancy properties for random regular digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2951882)
