IDEAS home Printed from https://ideas.repec.org/a/spr/jotpro/v23y2010i3d10.1007_s10959-010-0298-3.html
   My bibliography  Save this article

An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters

Author

Listed:
  • Florian Sobieczky

    (TU-Graz
    FSU-Jena)

Abstract

A comparison technique for random walks on finite graphs is introduced, using the well-known interlacing method. It yields improved return probability bounds. A key feature is the incorporation of parts of the spectrum of the transition matrix other than just the principal eigenvalue. As an application, an upper bound of the expected return probability of a random walk with symmetric transition probabilities is found. In this case, the state space is a random partial graph of a regular graph of bounded geometry and transitive automorphism group. The law of the random edge-set is assumed to be invariant with respect to some transitive subgroup of the automorphism group (‘invariant percolation’). Given that this subgroup is unimodular, it is shown that this invariance strengthens the upper bound of the expected return probability, compared with standard bounds such as those derived from the Cheeger inequality. The improvement is monotone in the degree of the underlying transitive graph.

Suggested Citation

  • Florian Sobieczky, 2010. "An Interlacing Technique for Spectra of Random Walks and Its Application to Finite Percolation Clusters," Journal of Theoretical Probability, Springer, vol. 23(3), pages 639-670, September.
    • Handle: RePEc:spr:jotpro:v:23:y:2010:i:3:d:10.1007_s10959-010-0298-3
    DOI: 10.1007/s10959-010-0298-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10959-010-0298-3
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10959-010-0298-3?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Haemers, W.H., 1995. "Interlacing eigenvalues and graphs," Other publications TiSEM 35c08207-2c5c-4387-aaf5-2, Tilburg University, School of Economics and Management.
    2. Mark Brown, 1999. "Interlacing Eigenvalues in Time Reversible Markov Chains," Mathematics of Operations Research, INFORMS, vol. 24(4), pages 847-864, November.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Haemers, W.H., 1996. "Disconnected Vertex Sets and Equidistant Code Pairs," Other publications TiSEM 88f23503-c117-4689-876b-1, Tilburg University, School of Economics and Management.
    2. Haemers, W.H. & Spence, E., 2000. "The Pseudo-Geometric Graphs for Generalised Quadrangles of Order (3,t)," Other publications TiSEM 5ff99d9d-636d-43b2-80ef-c, Tilburg University, School of Economics and Management.
    3. Etienne de Klerk & Monique Laurent, 2020. "Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 86-98, February.
    4. Haemers, W.H. & Spence, E., 2001. "The pseudo-geometric graphs for generalized quadrangles of order (3,t)," Other publications TiSEM 792e7c74-c02a-4bd4-a2d2-5, Tilburg University, School of Economics and Management.
    5. Bussemaker, F.C. & Haemers, W.H. & Spence, E., 1999. "The Search for Pseudo Orthogonal Latin Squares of Order Six," Other publications TiSEM eaa43e8f-0be1-4b54-a567-f, Tilburg University, School of Economics and Management.
    6. van Dam, E.R. & Haemers, W.H., 1998. "Graphs with constant mu and mu-bar," Other publications TiSEM 3cba5bf4-ad2f-465d-a9a2-a, Tilburg University, School of Economics and Management.
    7. Haemers, W.H., 1996. "Disconnected Vertex Sets and Equidistant Code Pairs," Research Memorandum 728, Tilburg University, School of Economics and Management.
    8. Fiala, N.C. & Haemers, W.H., 2003. "5-Chromatic Strongly Regular Graphs," Other publications TiSEM 16d4bde1-141a-428d-9633-b, Tilburg University, School of Economics and Management.
    9. Bussemaker, F.C. & Haemers, W.H. & Spence, E., 1999. "The Search for Pseudo Orthogonal Latin Squares of Order Six," Research Memorandum 780, Tilburg University, School of Economics and Management.
    10. van Dam, E.R., 1998. "Bounds on special subsets in graphs, eigenvalues and association schemes," Other publications TiSEM e9bcdd9f-2de0-4750-9ea2-c, Tilburg University, School of Economics and Management.
    11. Bussemaker, F.C. & Haemers, W.H. & Spence, E., 2000. "The search for pseudo orthogonal Latin squares of order six," Other publications TiSEM 860514f0-4ac6-4563-bf5c-b, Tilburg University, School of Economics and Management.
    12. Fiala, N.C. & Haemers, W.H., 2003. "5-Chromatic Strongly Regular Graphs," Discussion Paper 2003-45, Tilburg University, Center for Economic Research.
    13. Liu, Ruifang & Lai, Hong-Jian & Tian, Yingzhi & Wu, Yang, 2019. "Vertex-connectivity and eigenvalues of graphs with fixed girth," Applied Mathematics and Computation, Elsevier, vol. 344, pages 141-149.
    14. de Klerk, Etienne & Laurent, Monique, 2018. "Worst-case examples for Lasserre's measure-based hierarchy for polynomial optimization on the hypercube," Other publications TiSEM a939e3b3-0361-42c9-8263-0, Tilburg University, School of Economics and Management.
    15. Haemers, W.H. & Spence, E., 2000. "The Pseudo-Geometric Graphs for Generalised Quadrangles of Order (3,t)," Research Memorandum 794, Tilburg University, School of Economics and Management.
    16. Alazemi, Abdullah & Anđelić, Milica & Cvetković-Ilić, Dragana, 2021. "The Moore-Penrose inverse of symmetric matrices with nontrivial equitable partitions," Applied Mathematics and Computation, Elsevier, vol. 400(C).
    17. Brouwer, A.E. & Haemers, W.H., 2004. "Eigenvalues and Perfect Matchings," Discussion Paper 2004-58, Tilburg University, Center for Economic Research.
    18. Peeters, M.J.P., 1997. "Strongly regular graphs that are locally a disjoint union of hexagons," Other publications TiSEM 2691bb15-9a34-40cc-95ff-2, Tilburg University, School of Economics and Management.
    19. Jiang, Guisheng & Yu, Guidong & Sun, Wei & Ruan, Zheng, 2018. "The least eigenvalue of graphs whose complements have only two pendent vertices," Applied Mathematics and Computation, Elsevier, vol. 331(C), pages 112-119.
    20. van Dam, E.R. & Haemers, W.H., 1995. "A characterization of distance-regular graphs with diameter three," Research Memorandum FEW 695, Tilburg University, School of Economics and Management.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jotpro:v:23:y:2010:i:3:d:10.1007_s10959-010-0298-3. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.