Invariant Gaussian processes and independent sets on regular graphs of large girth

DOI10.1002/rsa.20547zbMath1322.05106arXiv1305.3977OpenAlexW3098551378MaRDI QIDQ3192382

Viktor Harangi, Endre Csóka, Balázs Gerencsér, Bálint Virág

Publication date: 12 October 2015

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

independent setregular graphregular treerandom regular graphlarge girthindependence ratiofactor of i.i.d.invariant Gaussian process

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Percolation with small clusters on random graphs, Factor of IID Percolation on Trees, Properties of regular graphs with large girth via local algorithms, Independence ratio and random eigenvectors in transitive graphs, Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree, On the almost eigenvectors of random regular graphs, On the minimum bisection of random 3-regular graphs, Uniform even subgraphs and graphical representations of Ising as factors of i.i.d., Improved replica bounds for the independence ratio of random regular graphs, 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, Cubic graphs with small independence ratio, Entropy and expansion, Local approximation of the maximum cut in regular graphs, Mutual information decay for factors of i.i.d., Ising model on trees and factors of IID, Entropy inequalities for factors of IID, The Ising Antiferromagnet and Max Cut on Random Regular Graphs, Distributed algorithms for fractional coloring

Cites Work

• Unnamed Item
• Unnamed Item
• A note on the independence number of triangle-free graphs
• On the independence and chromatic numbers of random regular graphs
• A note on the independence number of triangle-free graphs. II
• Large independent sets in regular graphs of large girth
• Fractional colorings of cubic graphs with large girth
• Percolation
• The Independence Ratio of Regular Graphs
• Limits of local algorithms over sparse random graphs