If is the combinatorial Laplacian of a graph, 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 . 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.
Si est le laplacien combinatoire d’un graphe, 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 . 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.
Keywords: Laplacian, sum of graphs, spectrum, Kullback distance, cut-off
Mot 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}, pages = {2197--2208}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {57}, number = {7}, year = {2007}, doi = {10.5802/aif.2331}, zbl = {1135.05039}, mrnumber = {2394540}, language = {en}, url = {http://archive.numdam.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 - http://archive.numdam.org/articles/10.5802/aif.2331/ DO - 10.5802/aif.2331 LA - en ID - AIF_2007__57_7_2197_0 ER -
Ycart, Bernard. Cut-off for large sums of graphs. Annales de l'Institut Fourier, Volume 57 (2007) no. 7, pp. 2197-2208. doi : 10.5802/aif.2331. http://archive.numdam.org/articles/10.5802/aif.2331/
[1] Shuffling cards and stopping times, Amer. Math. Monthly, Volume 93 (1986) no. 5, pp. 333-348 | DOI | MR | Zbl
[2] Hamiltonian paths in Cartesian powers of directed cycles, Graphs and Combinatorics, Volume 19 (2003) no. 4, pp. 459-466 | DOI | MR | Zbl
[3] Cutoff for n-tuples of exponentially converging processes, Stoch. Proc. Appl., Volume 116 (2006) no. 10, pp. 1433-1446 | DOI | MR | Zbl
[4] Introduction to matrix analysis, McGraw-Hill, London, 1960 | MR | Zbl
[5] Edge-isoperimetric problems for Cartesian powers of regular graphs, Theor. Comput. Sci., Volume 307 (2003) no. 3, pp. 473-492 | DOI | MR | Zbl
[6] Weighted graph Laplacians and isoperimetric inequalities, Pacific J. of Math., Volume 192 (2000), pp. 257-274 | DOI | MR | Zbl
[7] Introduction to stochastic processes, Prentice Hall, New York, 1975 | MR | Zbl
[8] Spectres de graphes, Cours spécialisés, SMF, 1998 no. 4 | MR | Zbl
[9] Singular limits of Schrödinger operators and Markov processes, J. Operator Theory, Volume 41 (1999), pp. 151-173 | MR | Zbl
[10] Recent results in the theory of graph spectra, Ann. Discrete Math., North-Holland, Amsterdam, 1988 no. 36 | MR | Zbl
[11] Spectra of graphs – Theory and application, Academic Press, New York, 1980 | MR | Zbl
[12] Laplace eigenvalues of graphs – a survey, Discrete Math., Volume 109 (1992), pp. 171-183 | DOI | MR | Zbl
[13] User’s guide to measure theoretic probability, Cambridge University Press, 2001 | Zbl
[14] Random walks on finite groups, Probability on discrete structures (Encyclopaedia Math. Sci.), Springer, Berlin (2004) no. 110, pp. 263-346 | MR | Zbl
[15] Cutoff for samples of Markov chains, ESAIM Probab. Stat., Volume 3 (1999), pp. 89-107 | DOI | Numdam | MR | Zbl
Cited by Sources: