Cut-off for large sums of graphs

Ycart, Bernard

Annales de l'Institut Fourier, Tome 57 (2007) no. 7, pp. 2197-2208.

Si $L$ est le laplacien combinatoire d’un graphe, $exp(-Lt)$ converge vers une matrice dont tous les coefficients sont égaux. La vitesse de convergence est mesurée par la distance d’entropie maximale. Quand le graphe est la somme d’un grand nombre de composantes, un phénomène de convergence abrupte peut survenir : avant un certain instant la distance à l’équilibre tend vers l’infini  ; après cet instant elle tend vers $0$. Une condition suffisante de convergence abrupte est donnée, et l’instant de convergence est exprimé en fonction du trou spectral et des vecteurs propres des composantes. Les sommes de cliques, d’étoiles et de lignes sont traitées en exemple.

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.

Classification : 05C50, 60J27
Keywords: Laplacian, sum of graphs, spectrum, Kullback distance, cut-off
Mot clés : Laplacien, somme de graphes, spectre, distance de Kullback, convergence abrupte

[1] Aldous, D.; Diaconis, P. Shuffling cards and stopping times, Amer. Math. Monthly, Volume 93 (1986) no. 5, pp. 333-348 | DOI | MR | Zbl

[2] Austin, D.; Gavlas, H.; Witte, D. Hamiltonian paths in Cartesian powers of directed cycles, Graphs and Combinatorics, Volume 19 (2003) no. 4, pp. 459-466 | DOI | MR | Zbl

[3] Barrera, J.; Lachaud, B.; Ycart, B. Cutoff for n-tuples of exponentially converging processes, Stoch. Proc. Appl., Volume 116 (2006) no. 10, pp. 1433-1446 | DOI | MR | Zbl

[4] Bellman, R. Introduction to matrix analysis, McGraw-Hill, London, 1960 | MR | Zbl

[5] Bezrukov, S.L.; Elsässer, R. Edge-isoperimetric problems for Cartesian powers of regular graphs, Theor. Comput. Sci., Volume 307 (2003) no. 3, pp. 473-492 | DOI | MR | Zbl

[6] Chung, F.; Oden, K. Weighted graph Laplacians and isoperimetric inequalities, Pacific J. of Math., Volume 192 (2000), pp. 257-274 | DOI | MR | Zbl

[7] Çinlar, E. Introduction to stochastic processes, Prentice Hall, New York, 1975 | MR | Zbl

[8] Colin de Verdière, Y. Spectres de graphes, Cours spécialisés, SMF, 1998 no. 4 | MR | Zbl

[9] Colin de Verdière, Y.; Pan, Y.; Ycart, B. Singular limits of Schrödinger operators and Markov processes, J. Operator Theory, Volume 41 (1999), pp. 151-173 | MR | Zbl

[10] Cvetković, D.; Doob, M.; Gutman, I.; Torgašev, A. Recent results in the theory of graph spectra, Ann. Discrete Math., North-Holland, Amsterdam, 1988 no. 36 | MR | Zbl

[11] Cvetković, D.; Doob, M.; Sachs, H. Spectra of graphs – Theory and application, Academic Press, New York, 1980 | MR | Zbl

[12] Mohar, B. Laplace eigenvalues of graphs – a survey, Discrete Math., Volume 109 (1992), pp. 171-183 | DOI | MR | Zbl

[13] Pollard, D. User’s guide to measure theoretic probability, Cambridge University Press, 2001 | Zbl

[14] Saloff-Coste, L.; Kesten, H. Random walks on finite groups, Probability on discrete structures (Encyclopaedia Math. Sci.), Springer, Berlin (2004) no. 110, pp. 263-346 | MR | Zbl

[15] Ycart, B. Cutoff for samples of Markov chains, ESAIM Probab. Stat., Volume 3 (1999), pp. 89-107 | DOI | Numdam | MR | Zbl