## Abstract

Let D_{n,d} be the set of all d-regular directed graphs on n vertices. Let G be a graph chosen uniformly at random from D_{n,d} and M be its adjacency matrix. We show that M is invertible with probability at least 1−Cln^{3}d/d for C≤d≤cn/ln^{2}n, where c,C are positive absolute constants. To this end, we establish a few properties of d-regular directed graphs. One of them, a Littlewood–Offord type anti-concentration property, is of independent interest. Let J be a subset of vertices of G with |J|≈n/d. Let δ_{i} be the indicator of the event that the vertex i is connected to J and define δ=(δ_{1},δ_{2},…,δ_{n})∈{0,1}^{n}. Then for every v∈{0,1}^{n} the probability that δ=v is exponentially small. This property holds even if a part of the graph is “frozen.”

Original language | English (US) |
---|---|

Pages (from-to) | 1447-1491 |

Number of pages | 45 |

Journal | Journal of Mathematical Analysis and Applications |

Volume | 445 |

Issue number | 2 |

DOIs | |

State | Published - Jan 15 2017 |

## All Science Journal Classification (ASJC) codes

- Analysis
- Applied Mathematics

## Keywords

- Adjacency matrices
- Anti-concentration
- Invertibility of random matrices
- Littlewood–Offord theory
- Random regular graphs
- Singular probability