×

zbMATH — the first resource for mathematics

Cut-off for large sums of graphs. (English) Zbl 1135.05039
Summary: If \(L\) is the combinatorial Laplacian of a graph, \(\exp(-Lt)\) converges to a matrix with identical coefficients. The speed of convergence is measured by the maximal entropy distance. When the graph is the sum of a large number of components, a cut-off phenomenon may occur: before some instant the distance to equilibrium tends to infinity; after that instant it tends to 0. A sufficient condition for cut-off is given, and the cut-off instant is expressed as a function of the gap and eigenvectors of components. Examples include sums of cliques, stars and lines.

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
60J27 Continuous-time Markov processes on discrete state spaces
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] Aldous, D.; Diaconis, P., Shuffling cards and stopping times, Amer. Math. Monthly, 93, 5, 333-348, (1986) · Zbl 0603.60006
[2] Austin, D.; Gavlas, H.; Witte, D., Hamiltonian paths in Cartesian powers of directed cycles, Graphs and Combinatorics, 19, 4, 459-466, (2003) · Zbl 1032.05069
[3] Barrera, J.; Lachaud, B.; Ycart, B., Cutoff for n-tuples of exponentially converging processes, Stoch. Proc. Appl., 116, 10, 1433-1446, (2006) · Zbl 1103.60023
[4] Bellman, R., Introduction to matrix analysis, (1960), McGraw-Hill, London · Zbl 0124.01001
[5] Bezrukov, S. L.; Elsässer, R., Edge-isoperimetric problems for Cartesian powers of regular graphs, Theor. Comput. Sci., 307, 3, 473-492, (2003) · Zbl 1070.68114
[6] Chung, F.; Oden, K., Weighted graph Laplacians and isoperimetric inequalities, Pacific J. of Math., 192, 257-274, (2000) · Zbl 1009.05095
[7] Çinlar, E., Introduction to stochastic processes, (1975), Prentice Hall, New York · Zbl 0341.60019
[8] Colin de Verdière, Y., Spectres de graphes, 4, (1998), SMF · Zbl 0913.05071
[9] Colin de Verdière, Y.; Pan, Y.; Ycart, B., Singular limits of Schrödinger operators and Markov processes, J. Operator Theory, 41, 151-173, (1999) · Zbl 0990.47013
[10] Cvetković, D.; Doob, M.; Gutman, I.; Torgašev, A., Recent results in the theory of graph spectra, 36, (1988), North-Holland, Amsterdam · Zbl 0634.05054
[11] Cvetković, D.; Doob, M.; Sachs, H., Spectra of graphs - Theory and application, (1980), Academic Press, New York · Zbl 0458.05042
[12] Mohar, B., Laplace eigenvalues of graphs - a survey, Discrete Math., 109, 171-183, (1992) · Zbl 0783.05073
[13] Pollard, D., User’s guide to measure theoretic probability, (2001), Cambridge University Press · Zbl 0992.60001
[14] Saloff-Coste, L.; Kesten, H., Random walks on finite groups, Probability on discrete structures, 110, 263-346, (2004), Springer, Berlin · Zbl 1049.60006
[15] Ycart, B., Cutoff for samples of Markov chains, ESAIM Probab. Stat., 3, 89-107, (1999) · Zbl 0932.60077
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.