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

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

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

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

¹ 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, Tome 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 :

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

@article{CRMATH_2016__354_2_121_0,
     author = {Litvak, Alexander E. and Lytova, Anna and Tikhomirov, Konstantin and Tomczak-Jaegermann, Nicole and Youssef, Pierre},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2015.12.002/}
}

TY  - JOUR
AU  - Litvak, Alexander E.
AU  - Lytova, Anna
AU  - Tikhomirov, Konstantin
AU  - Tomczak-Jaegermann, Nicole
AU  - Youssef, Pierre
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2015.12.002/
DO  - 10.1016/j.crma.2015.12.002
LA  - en
ID  - CRMATH_2016__354_2_121_0
ER  -

%0 Journal Article
%A Litvak, Alexander E.
%A Lytova, Anna
%A Tikhomirov, Konstantin
%A Tomczak-Jaegermann, Nicole
%A Youssef, Pierre
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2015.12.002/
%R 10.1016/j.crma.2015.12.002
%G en
%F CRMATH_2016__354_2_121_0

Litvak, Alexander E.; Lytova, Anna; Tikhomirov, Konstantin; Tomczak-Jaegermann, Nicole; Youssef, Pierre. Anti-concentration property for random digraphs and invertibility of their adjacency matrices. Comptes Rendus. Mathématique, Tome 354 (2016) no. 2, pp. 121-124. doi : 10.1016/j.crma.2015.12.002. http://www.numdam.org/articles/10.1016/j.crma.2015.12.002/

Bibliographie
Cité par

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

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

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

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

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

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

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

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

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

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

[11] Tao, T.; Vu, V. 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] Vu, V. Random discrete matrices, Horizons of combinatorics, Bolyai Soc. Math. Stud., Volume 17 (2008), pp. 257-280

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

Cité par Sources :