PARKING ON TRANSITIVE UNIMODULAR GRAPHS

被引：9

作者：

Damron, Michael ^{[1
]}

Gravner, Janko ^{[2
]}

Junge, Matthew ^{[3
]}

Lyu, Hanbaek ^{[4
]}

Sivakoff, David ^{[5
]}

机构：

[1] Georgia Inst Technol, Dept Math, Atlanta, GA 30332 USA

[2] Univ Calif Davis, Dept Math, Davis, CA 95616 USA

[3] Duke Univ, Dept Math, Durham, NC 27708 USA

[4] Univ Calif Los Angeles, Math Dept, Los Angeles, CA 90095 USA

[5] Ohio State Univ, Dept Stat & Math, Columbus, OH 43210 USA

来源：

ANNALS OF APPLIED PROBABILITY | 2019年 / 29卷 / 04期

基金：

芬兰科学院;

关键词：

Annihilating particle system; random walk; blockades; ANNIHILATING RANDOM-WALKS; SPATIAL STRUCTURE; RECURRENCE;

D O I：

10.1214/18-AAP1443

中图分类号：

O21 [概率论与数理统计]; C8 [统计学];

学科分类号：

020208 ; 070103 ; 0714 ;

摘要：

Place a car independently with probability p at each site of a graph. Each initially vacant site is a parking spot that can fit one car. Cars simultaneously perform independent random walks. When a car encounters an available parking spot it parks there. Other cars can still drive over the site, but cannot park there. For a large class of transitive and unimodular graphs, we show that the root is almost surely visited infinitely many times when p >= 1/2, and only finitely many times otherwise.

引用

页码：2089 / 2113

页数：25

共 50 条

[1] On unimodular graphs
Akbari, S.
Kirkland, S. J.
LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 421 (01) : 3 - 15
[2] UNIMODULAR EQUIVALENCE OF GRAPHS
MERRIS, R
LINEAR ALGEBRA AND ITS APPLICATIONS, 1992, 173 : 181 - 189
[3] TRANSITIVE GRAPHS
BRYANT, VW
HARRIS, KG
JOURNAL OF THE LONDON MATHEMATICAL SOCIETY-SECOND SERIES, 1975, 11 (SEP): : 123 - 128
[4] PERMUTATION GRAPHS AND TRANSITIVE GRAPHS
EVEN, S
LEMPEL, A
PNUELI, A
JOURNAL OF THE ACM, 1972, 19 (03) : 400 - &
[5] Restricted unimodular chordal graphs
Peled, UN
Wu, JL
JOURNAL OF GRAPH THEORY, 1999, 30 (02) : 121 - 136
[6] Distance unimodular equivalence of graphs
Hou, Yaoping
Woo, Chingwah
LINEAR & MULTILINEAR ALGEBRA, 2008, 56 (06): : 611 - 626
[7] Unimodular graphs and Eisenstein sums
Nica, Bogdan
JOURNAL OF ALGEBRAIC COMBINATORICS, 2017, 45 (02) : 423 - 454
[8] Unimodular graphs and Eisenstein sums
Bogdan Nica
Journal of Algebraic Combinatorics, 2017, 45 : 423 - 454
[9] A NOTE ON UNIMODULAR CONGRUENCE OF GRAPHS
MERRIS, R
LINEAR ALGEBRA AND ITS APPLICATIONS, 1994, 201 : 57 - 60
[10] MAINTENANCE OF TRANSITIVE CLOSURES AND TRANSITIVE REDUCTIONS OF GRAPHS
LAPOUTRE, JA
VANLEEUWEN, J
LECTURE NOTES IN COMPUTER SCIENCE, 1988, 314 : 106 - 120

← 1 2 3 4 5 →