Anti-concentration property for random digraphs and invertibility of their adjacency matrices - 06/02/16
pages | 4 |
Iconographies | 0 |
Vidéos | 0 |
Autres | 0 |
Abstract |
Let be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from and M be its adjacency matrix. We show that M is invertible with probability at least for , where 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 . Let be the indicator of the event that the vertex i is connected to J and . Then δ is not concentrated around any vertex of the cube. This property holds even if a part of the graph is fixed.
Le texte complet de cet article est disponible en PDF.Résumé |
Soit l'ensemble des graphes orientés d-réguliers à n sommets. Soit G un élément choisi uniformément au hasard dans et M sa matrice d'adjacente. On montre que M est inversible avec probabilité supérieure à pour , où 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 . Soit l'indicateur du fait que le sommet i est connecté à J ; on note . 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.
Le texte complet de cet article est disponible en PDF.Plan
Vol 354 - N° 2
P. 121-124 - février 2016 Retour au numéroBienvenue sur EM-consulte, la référence des professionnels de santé.
L’accès au texte intégral de cet article nécessite un abonnement.
Bienvenue sur EM-consulte, la référence des professionnels de santé.
L’achat d’article à l’unité est indisponible à l’heure actuelle.
Déjà abonné à cette revue ?