Cut-off for large sums of graphs
[Convergence abrupte pour de grandes sommes de graphes]
Ycart, Bernard
Annales de l'Institut Fourier, Tome 57 (2007), p. 2197-2208 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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.

Publié le : 2007-01-01
DOI : https://doi.org/10.5802/aif.2331
Classification:  05C50,  60J27
Mots clés: Laplacien, somme de graphes, spectre, distance de Kullback, convergence abrupte 
@article{AIF_2007__57_7_2197_0,
     author = {Ycart, Bernard},
     title = {Cut-off for large sums of graphs},
     journal = {Annales de l'Institut Fourier},
     volume = {57},
     year = {2007},
     pages = {2197-2208},
     doi = {10.5802/aif.2331},
     zbl = {1135.05039},
     mrnumber = {2394540},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_2007__57_7_2197_0}
}

Ycart, Bernard. Cut-off for large sums of graphs. Annales de l'Institut Fourier, Tome 57 (2007) pp. 2197-2208. doi : 10.5802/aif.2331. http://gdmltest.u-ga.fr/item/AIF_2007__57_7_2197_0/

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

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

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

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

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

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

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

[8] Colin De Verdière, Y. Spectres de graphes, SMF, Cours spécialisés (1998) no. 4 | MR 1652692 | 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, Tome 41 (1999), pp. 151-173 | MR 1675188 | Zbl 0990.47013

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

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

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

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

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

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