Cut-off for large sums of graphs

[Convergence abrupte pour de grandes sommes de graphes]

Ycart, Bernard¹

¹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

Abstract (VO)

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.

Résumé

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.

Détail

DOI : 10.5802/aif.2331

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