Cut-off for large sums of graphs

Bernard Ycart[1]

  • [1] Université Joseph Fourier LJK, CNRS UMR 5224 38041 Grenoble cedex 9 (France)

Annales de l’institut Fourier (2007)

  • Volume: 57, Issue: 7, page 2197-2208
  • ISSN: 0373-0956

Abstract

top
If L is the combinatorial Laplacian of a graph, exp ( - L t ) 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.

How to cite

top

Ycart, Bernard. "Cut-off for large sums of graphs." Annales de l’institut Fourier 57.7 (2007): 2197-2208. <http://eudml.org/doc/10295>.

@article{Ycart2007,
abstract = {If $L$ is the combinatorial Laplacian of a graph, $\exp (-L\,t)$ 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.},
affiliation = {Université Joseph Fourier LJK, CNRS UMR 5224 38041 Grenoble cedex 9 (France)},
author = {Ycart, Bernard},
journal = {Annales de l’institut Fourier},
keywords = {Laplacian; sum of graphs; spectrum; Kullback distance; cut-off},
language = {eng},
number = {7},
pages = {2197-2208},
publisher = {Association des Annales de l’institut Fourier},
title = {Cut-off for large sums of graphs},
url = {http://eudml.org/doc/10295},
volume = {57},
year = {2007},
}

TY - JOUR
AU - Ycart, Bernard
TI - Cut-off for large sums of graphs
JO - Annales de l’institut Fourier
PY - 2007
PB - Association des Annales de l’institut Fourier
VL - 57
IS - 7
SP - 2197
EP - 2208
AB - If $L$ is the combinatorial Laplacian of a graph, $\exp (-L\,t)$ 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.
LA - eng
KW - Laplacian; sum of graphs; spectrum; Kullback distance; cut-off
UR - http://eudml.org/doc/10295
ER -

References

top
  1. D. Aldous, P. Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), 333-348 Zbl0603.60006MR841111
  2. D. Austin, H. Gavlas, D. Witte, Hamiltonian paths in Cartesian powers of directed cycles, Graphs and Combinatorics 19 (2003), 459-466 Zbl1032.05069MR2031001
  3. J. Barrera, B. Lachaud, B. Ycart, Cutoff for n-tuples of exponentially converging processes, Stoch. Proc. Appl. 116 (2006), 1433-1446 Zbl1103.60023MR2260742
  4. R. Bellman, Introduction to matrix analysis, (1960), McGraw-Hill, London Zbl0124.01001MR122820
  5. S.L. Bezrukov, R. Elsässer, Edge-isoperimetric problems for Cartesian powers of regular graphs, Theor. Comput. Sci. 307 (2003), 473-492 Zbl1070.68114MR2021742
  6. F. Chung, K. Oden, Weighted graph Laplacians and isoperimetric inequalities, Pacific J. of Math. 192 (2000), 257-274 Zbl1009.05095MR1744568
  7. E. Çinlar, Introduction to stochastic processes, (1975), Prentice Hall, New York Zbl0341.60019MR380912
  8. Y. Colin de Verdière, Spectres de graphes, (1998), SMF Zbl0913.05071MR1652692
  9. Y. Colin de Verdière, Y. Pan, B. Ycart, Singular limits of Schrödinger operators and Markov processes, J. Operator Theory 41 (1999), 151-173 Zbl0990.47013MR1675188
  10. D. Cvetković, M. Doob, I. Gutman, A. Torgašev, Recent results in the theory of graph spectra, (1988), North-Holland, Amsterdam Zbl0634.05054MR926481
  11. D. Cvetković, M. Doob, H. Sachs, Spectra of graphs – Theory and application, (1980), Academic Press, New York Zbl0458.05042MR572262
  12. B. Mohar, Laplace eigenvalues of graphs – a survey, Discrete Math. 109 (1992), 171-183 Zbl0783.05073MR1192380
  13. D. Pollard, User’s guide to measure theoretic probability, (2001), Cambridge University Press Zbl0992.60001
  14. L. Saloff-Coste, Random walks on finite groups, Probability on discrete structures (2004), 263-346, Springer, Berlin Zbl1049.60006MR2023654
  15. B. Ycart, Cutoff for samples of Markov chains, ESAIM Probab. Stat. 3 (1999), 89-107 Zbl0932.60077MR1716128

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.