Independence ratio and random eigenvectors in transitive graphs

DOI10.1214/14-AOP952zbMath1323.05101arXiv1308.5173OpenAlexW1784387483MaRDI QIDQ888543

Bálint Virág, Viktor Harangi

Publication date: 30 October 2015

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1308.5173

zbMATH Keywords

adjacency matrixindependent setregular graphminimum eigenvaluetransitive graphindependence ratiofactor of i.i.d.invariant Gaussian process

Mathematics Subject Classification ID

Gaussian processes (60G15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Factor of IID Percolation on Trees ⋮ Suboptimality of local algorithms for a class of max-cut problems ⋮ On the almost eigenvectors of random regular graphs ⋮ Uniform even subgraphs and graphical representations of Ising as factors of i.i.d. ⋮ Correlation Bounds for Distant Parts of Factor of IID Processes ⋮ Spectral measures of factor of i.i.d. processes on vertex-transitive graphs ⋮ Factors of IID on Trees ⋮ Entropy and expansion ⋮ Mutual information decay for factors of i.i.d. ⋮ Entropy inequalities for factors of IID

Cites Work

• Unnamed Item
• Unnamed Item
• Perfect matchings as IID factors on non-amenable groups
• Differential equations driven by rough paths. Ecole d'Eté de Probabilités de Saint-Flour XXXIV -- 2004. Lectures given at the 34th probability summer school, July 6--24, 2004.
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Large independent sets in regular graphs of large girth
• Invariant Gaussian processes and independent sets on regular graphs of large girth
• Fractional colorings of cubic graphs with large girth
• Ramanujan graphings and correlation decay in local algorithms
• The Independence Ratio of Regular Graphs
• Random Walks on Infinite Graphs and Groups
• Amenable actions and almost invariant sets
• The Isepiphan Problem for n-Hedra
• Intersecting families of permutations

This page was built for publication: Independence ratio and random eigenvectors in transitive graphs