The jamming constant of uniform random graphs

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:127

Article

Bermolen, Paola¹  Jonckheere, Matthieu²  Moyal, Pascal^3,4 

[1] Univ La Republ, Fac Ingn, Julio Herrera & Reissig 565, Montevideo, Uruguay

[2] Univ Buenos Aires, CONICET, Fac Ciencas Exactas & Nat, Math Dept, 1482 Pabellon I,Ciudad Univ Buenos Aires, Buenos Aires, DF, Argentina

[3] Univ Technol Compiegne, Lab Math Appl LMAC, Rue Dr Schweitzer,CS 60319, F-60203 Compiegne, France

[4] Northwestern Univ, Mc Cormick Sch Engn, IEMS Dept, 2145 Sheridan Rd, Evanston, IL 60208 USA

关键词: Random graph;    Configuration model;    Parking process;    Measure-valued Markov process;    Hydrodynamic limit;   

DOI  :  10.1016/j.spa.2016.10.005

来源: Elsevier

【 摘 要 】

By constructing jointly a random graph and an associated exploration process, we define the dynamics of a parking process on a class of uniform random graphs as a measure-valued Markov process, representing the empirical degree distribution of non-explored nodes. We then establish a functional law of large numbers for this process as the number of vertices grows to infinity, allowing us to assess the jamming constant of the considered random graphs, i.e. the size of the maximal independent set discovered by the exploration algorithm. This technique, which can be applied to any uniform random graph with a given possibly unbounded degree distribution, can be seen as a generalization in the space of measures, of the differential equation method introduced by Wormald. (C) 2016 Elsevier B.V. All rights reserved.

【 授权许可】

Free