no. 7
Cut-off for large sums of graphs
[Convergence abrupte pour de grandes sommes de graphes]
Ycart, Bernard1
1 Université Joseph Fourier LJK, CNRS UMR 5224 38041 Grenoble cedex 9 (France)
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.

DOI : 10.5802/aif.2331
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

Ycart, Bernard 1

1 Université Joseph Fourier LJK, CNRS UMR 5224 38041 Grenoble cedex 9 (France) 
@article{AIF_2007__57_7_2197_0,
     author = {Ycart, Bernard},
     title = {Cut-off for large sums of graphs},
     journal = {Annales de l'Institut Fourier},
     pages = {2197--2208},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {57},
     number = {7},
     year = {2007},
     doi = {10.5802/aif.2331},
     mrnumber = {2394540},
     zbl = {1135.05039},
     language = {en},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.2331/}
}
TY  - JOUR
AU  - Ycart, Bernard
TI  - Cut-off for large sums of graphs
JO  - Annales de l'Institut Fourier
PY  - 2007
SP  - 2197
EP  - 2208
VL  - 57
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.2331/
DO  - 10.5802/aif.2331
LA  - en
ID  - AIF_2007__57_7_2197_0
ER  - 
%0 Journal Article
%A Ycart, Bernard
%T Cut-off for large sums of graphs
%J Annales de l'Institut Fourier
%D 2007
%P 2197-2208
%V 57
%N 7
%I Association des Annales de l’institut Fourier
%U https://aif.centre-mersenne.org/articles/10.5802/aif.2331/
%R 10.5802/aif.2331
%G en
%F AIF_2007__57_7_2197_0
Ycart, Bernard. Cut-off for large sums of graphs. Annales de l'Institut Fourier, Tome 57 (2007) no. 7, pp. 2197-2208. doi : 10.5802/aif.2331. https://aif.centre-mersenne.org/articles/10.5802/aif.2331/

[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.) (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

Cité par Sources :