# 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

## Access Full Article

top## Abstract

top## How to cite

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

## NotesEmbed ?

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