Anti-concentration property for random digraphs and invertibility of their adjacency matrices

Soit Dn,d l'ensemble des graphes orientés d-réguliers à n sommets. Soit G un élément choisi uniformément au hasard dans Dn,d et M sa matrice d'adjacente. On montre que M est inversible avec probabilité supérieure à 1−Cln3⁡d/d pour C≤d≤cn/ln2⁡n, où c,C sont des constantes universelles positives. Afin d'établir ce résultat, nous montrons certaines propriétés des graphes orientés d-réguliers. Parmi celles-ci, une propriété d'anti-concentration de type Littlewood-Offord. Soit J un sous-ensemble de sommets de G de taille |J|≤cn/d. Soit δi l'indicateur du fait que le sommet i est connecté à J ; on note δ=(δ1,δ2,…,δn)∈{0,1}n. On montre alors que δ n'est concentré autour d'aucun sommet du cube. Cette propriété reste vraie si une partie du graphe est fixée.