Médecine

Paramédical

Autres domaines


S'abonner

Anti-concentration property for random digraphs and invertibility of their adjacency matrices - 06/02/16

Doi : 10.1016/j.crma.2015.12.002 
Alexander E. Litvak a , Anna Lytova a , Konstantin Tikhomirov a , Nicole Tomczak-Jaegermann a , Pierre Youssef b
a Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada 
b Université Paris Diderot, Laboratoire de probabilités et de modèles aléatoires, 75013 Paris, France 

Bienvenue 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.

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


© 2015  Académie des sciences. Publié par Elsevier Masson SAS. Tous droits réservés.
Ajouter à ma bibliothèque Retirer de ma bibliothèque Imprimer
Export

    Export citations

  • Fichier

  • Contenu

Vol 354 - N° 2

P. 121-124 - février 2016 Retour au numéro
Article précédent Article précédent
  • Trimness of closed intervals in Cambrian semilattices
  • Henri Mühle
| Article suivant Article suivant
  • Tropical curves in sandpiles
  • Nikita Kalinin, Mikhail Shkolnikov

Bienvenue 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 ?

Mon compte


Plateformes Elsevier Masson

Déclaration CNIL

EM-CONSULTE.COM est déclaré à la CNIL, déclaration n° 1286925.

En application de la loi nº78-17 du 6 janvier 1978 relative à l'informatique, aux fichiers et aux libertés, vous disposez des droits d'opposition (art.26 de la loi), d'accès (art.34 à 38 de la loi), et de rectification (art.36 de la loi) des données vous concernant. Ainsi, vous pouvez exiger que soient rectifiées, complétées, clarifiées, mises à jour ou effacées les informations vous concernant qui sont inexactes, incomplètes, équivoques, périmées ou dont la collecte ou l'utilisation ou la conservation est interdite.
Les informations personnelles concernant les visiteurs de notre site, y compris leur identité, sont confidentielles.
Le responsable du site s'engage sur l'honneur à respecter les conditions légales de confidentialité applicables en France et à ne pas divulguer ces informations à des tiers.