### Abstract

Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,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 directed d-regular 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|≤cn/d. Let δ_{i} be the indicator of the event that the vertex i is connected to J and δ=(δ_{1}, δ_{2}, . ., δ_{n})∈[0, 1]^{n}. Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.

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

Pages (from-to) | 121-124 |

Number of pages | 4 |

Journal | Comptes Rendus Mathematique |

Volume | 354 |

Issue number | 2 |

DOIs | |

State | Published - Feb 1 2016 |

### All Science Journal Classification (ASJC) codes

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Anti-concentration property for random digraphs and invertibility of their adjacency matrices'. Together they form a unique fingerprint.

## Cite this

*Comptes Rendus Mathematique*,

*354*(2), 121-124. https://doi.org/10.1016/j.crma.2015.12.002