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

Alexander E. Litvak; Anna Lytova; Konstantin Tikhomirov; Nicole Tomczak-Jaegermann; Pierre Youssef

doi:10.1016/j.crma.2015.12.002

Combinatorics/Probability theory

Anti-concentration property for random digraphs and invertibility of their adjacency matrices
[Propriété d'anti-concentration pour les digraphes aléatoires et invertibilité de leur matrice d'adjacence]

Présenté par : the Editorial Board

Alexander E. Litvak ¹ ; Anna Lytova ¹ ; Konstantin Tikhomirov ¹ ; Nicole Tomczak-Jaegermann ¹ ; Pierre Youssef ²

¹ Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada
² Université Paris Diderot, Laboratoire de probabilités et de modèles aléatoires, 75013 Paris, France

Comptes Rendus. Mathématique, Volume 354 (2016) no. 2, pp. 121-124.

Résumé
Abstract

Soit $D_{n, d}$ l'ensemble des graphes orientés d-réguliers à n sommets. Soit G un élément choisi uniformément au hasard dans $D_{n, d}$ et M sa matrice d'adjacente. On montre que M est inversible avec probabilité supérieure à $1 - C \ln^{3} d / \sqrt{d}$ pour $C \leq d \leq c n / \ln^{2} 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 | \leq c n / d$ . Soit $δ_{i}$ l'indicateur du fait que le sommet i est connecté à J ; on note $δ = (δ_{1}, δ_{2}, \dots, δ_{n}) \in {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.

Let $D_{n, d}$ be the set of all directed d-regular 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 - C \ln^{3} d / \sqrt{d}$ for $C \leq d \leq c n / \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 | \leq c n / d$ . Let $δ_{i}$ be the indicator of the event that the vertex i is connected to J and $δ = (δ_{1}, δ_{2}, \dots, δ_{n}) \in {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.

Reçu le : 2015-09-16
Accepté le : 2015-12-02
Publié le : 2016-01-22

DOI : 10.1016/j.crma.2015.12.002

Affiliations des auteurs :

Alexander E. Litvak ¹ ; Anna Lytova ¹ ; Konstantin Tikhomirov ¹ ; Nicole Tomczak-Jaegermann ¹ ; Pierre Youssef ²

¹ Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada
² Université Paris Diderot, Laboratoire de probabilités et de modèles aléatoires, 75013 Paris, France

@article{CRMATH_2016__354_2_121_0,
     author = {Alexander E. Litvak and Anna Lytova and Konstantin Tikhomirov and Nicole Tomczak-Jaegermann and Pierre Youssef},
     title = {Anti-concentration property for random digraphs and invertibility of their adjacency matrices},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {121--124},
     publisher = {Elsevier},
     volume = {354},
     number = {2},
     year = {2016},
     doi = {10.1016/j.crma.2015.12.002},
     language = {en},
}

TY  - JOUR
AU  - Alexander E. Litvak
AU  - Anna Lytova
AU  - Konstantin Tikhomirov
AU  - Nicole Tomczak-Jaegermann
AU  - Pierre Youssef
TI  - Anti-concentration property for random digraphs and invertibility of their adjacency matrices
JO  - Comptes Rendus. Mathématique
PY  - 2016
SP  - 121
EP  - 124
VL  - 354
IS  - 2
PB  - Elsevier
DO  - 10.1016/j.crma.2015.12.002
LA  - en
ID  - CRMATH_2016__354_2_121_0
ER  -

%0 Journal Article
%A Alexander E. Litvak
%A Anna Lytova
%A Konstantin Tikhomirov
%A Nicole Tomczak-Jaegermann
%A Pierre Youssef
%T Anti-concentration property for random digraphs and invertibility of their adjacency matrices
%J Comptes Rendus. Mathématique
%D 2016
%P 121-124
%V 354
%N 2
%I Elsevier
%R 10.1016/j.crma.2015.12.002
%G en
%F CRMATH_2016__354_2_121_0

Alexander E. Litvak; Anna Lytova; Konstantin Tikhomirov; Nicole Tomczak-Jaegermann; Pierre Youssef. Anti-concentration property for random digraphs and invertibility of their adjacency matrices. Comptes Rendus. Mathématique, Volume 354 (2016) no. 2, pp. 121-124. doi : 10.1016/j.crma.2015.12.002. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2015.12.002/

Bibliographie
Cité par

[1] S. Chatterjee A short survey of Stein's method, Proceedings ICM, vol. 4, 2014, pp. 1-24

[2] N.A. Cook Discrepancy properties for random regular digraphs, Random Struct. Algorithms (2016) (in press)

[3] N.A. Cook On the singularity of adjacency matrices for random regular digraphs, Probab. Theory Related Fields (2016) | DOI

[4] P. Erdös On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc., Volume 51 (1945), pp. 898-902

[5] A. Frieze Random structures and algorithms, Proceedings ICM, vol. 1, 2014, pp. 311-340

[6] M. Krivelevich; B. Sudakov; V.H. Vu; N.C. Wormald Random regular graphs of high degree, Random Struct. Algorithms, Volume 18 (2001), pp. 346-363

[7] A.E. Litvak; A. Lytova; K. Tikhomirov; N. Tomczak-Jaegermann; P. Youssef Adjacency matrices of random digraphs: singularity and anti-concentration | arXiv

[8] B.D. McKay Subgraphs of random graphs with specified degrees, Congr. Numer., Volume 33 (1981), pp. 213-223

[9] M. Rudelson; R. Vershynin Non-asymptotic theory of random matrices: extreme singular values, Proceedings ICM, vol. 3, 2010, pp. 1576-1602

[10] J.K. Senior Partitions and their representative graphs, Amer. J. Math., Volume 73 (1951), pp. 663-689

[11] T. Tao; V. Vu From the Littlewood–Offord problem to the circular law: universality of the spectral distribution of random matrices, Bull. Amer. Math. Soc. (N. S.), Volume 46 (2009), pp. 377-396

[12] V. Vu Random discrete matrices, Horizons of combinatorics, Bolyai Soc. Math. Stud., Volume 17 (2008), pp. 257-280

[13] V.H. Vu Combinatorial problems in random matrix theory, Proceedings ICM, vol. 4, 2014, pp. 489-508

Cité par Sources :

Commentaires - Politique