Comptes Rendus
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]
Comptes Rendus. Mathématique, Volume 354 (2016) no. 2, pp. 121-124.

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 à 1Cln3d/d pour Cdcn/ln2n, 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.

Let Dn,d be the set of all directed d-regular graphs on n vertices. Let G be a graph chosen uniformly at random from Dn,d and M be its adjacency matrix. We show that M is invertible with probability at least 1Cln3d/d for Cdcn/ln2n, 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|cn/d. Let δi be the indicator of the event that the vertex i is connected to J and δ=(δ1,δ2,,δn){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 :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2015.12.002

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

1 Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, Alberta, T6G 2G1 Canada
2 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/

[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