Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các bước ngẫu nhiên trên đồ thị có tính chất isoperimetric mạnh
Tóm tắt
Một bước ngẫu nhiên trên một đồ thị là một chuỗi Markov mà không gian trạng thái bao gồm các đỉnh của đồ thị, và các chuyển tiếp chỉ được phép dọc theo các cạnh. Chúng tôi nghiên cứu các bước ngẫu nhiên (đảo ngược) mạnh và đặc trưng hóa lớp đồ thị mà trong đó xác suất chuyển tiếp trong n bước có xu hướng tiến đến không với tốc độ nhanh theo hàm mũ ("đặc tính ergodicity hình học δ"). Những đặc trưng này liên quan đến một tính chất hình học, bất đẳng thức chuẩn đối với một số phép toán liên quan, và các giá trị riêng của toán tử Laplace. Có sự tương đồng (mạnh) với lý thuyết về các nhóm (không) chấp thuận.
Từ khóa
#bước ngẫu nhiên #chuỗi Markov #đồ thị #tính chất isoperimetric #ergodicity hình học #toán tử LaplaceTài liệu tham khảo
Biggs, N. L., Mohar, B., and Shawe-Taylor, J. (1986). The Spectral Radius of Infinite Graphs, Preprint 174 (Univ. Ljubljana).
Brooks, R. (1985). The spectral geometry of the Apollonian packing,Commun. Pure Appl. Math. 38, 357–366.
Dodziuk, J. (1984). Difference equations, isoperimetric inequality and transience of certain random walks,Trans. Am. Math. Soc. 284, 787–794.
Dunford, N., and Schwartz, J. T. (1967).Linear Operators, Part I, Interscience, New York.
Gerl, P. (1973). Probability measures on semigroups,Proc. Am. Math. Soc. 40, 527–532.
Gerl, P. (1986). Random walks on graphs. InProbability Measures on Groups VIII, Heyer, H. (ed.), Lecture Notes in Math. 1210, Springer-Verlag, Berlin, pp. 285–303.
Gerl, P. (1986) Eine isoperimetrische Eigenschaft von Bäumen,Sitzungsber.Österr. Akad. Wiss. 195, Abt. II, 49–52.
Gerl, P., and Woess, W. (1986). Simple random walks on trees.Eur. J. Combinatorics,7, 321–331.
Pier, J. P., (1984).Amenable Locally Compact Groups, Wiley, New York.
Seneta, E. (1981).Non-negative Matrices and Markov Chains, 2nd ed., Springer-Verlag, New York.
Varopoulos, N. Th. (1985). Isoperimetric inequalities and Markov chains,J. Funct. Anal. 63, 215–239.