The expected degree of minimal spanning forests

DOI10.1007/S00493-014-3160-XMaRDI QIDQ5915869zbMATH OpenOpenAlexWikidataFDO

Authors Andreas Thom

Publication date 22 February 2018

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

minimal spanning forestspectral radiustransitive graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Algebraic ergodic theory, cocycles, orbit equivalence, ergodic equivalence relations (37A20) Probability theory on algebraic and topological structures (60B99)

Abstract: We give a lower bound on the expected degree of the free minimal spanning forest of a vertex transitive graph in terms of its spectral radius. This result answers a question of Lyons-Peres-Schramm and simplifies the Gaboriau-Lyons proof of the measurable-group-theoretic solution to von Neumann's problem. In the second part we study a relative version of the free minimal spanning forest. As a consequence of this study we can show that non-torsion unitarizable groups have fixed price one.

Recommendations

• On the difference of expected lengths of minimum spanning trees
• The expected value of random minimal length spanning tree of a complete graph
• Expected lengths of minimum spanning trees for non-identical edge distributions
• scientific article; zbMATH DE number 1984546
• On random minimum length spanning trees
• scientific article; zbMATH DE number 1123757
• The vertex degrees of minimum spanning trees
• Degree-bounded minimum spanning trees

Cites work

• ^2 invariants of equivalence relations and groups
• A measurable-group-theoretic solution to von Neumann's problem
• Bernoulli actions are weakly contained in any free action
• Cost of equivalence relations and groups
• Ends in free minimal spanning forests
• Ergodic subequivalence relations induced by a Bernoulli action
• Minimal spanning forests
• Nonunitarizable Representations and Random Forests
• Normal generation and \(\ell^2\)-Betti numbers of groups.
• On non-uniqueness of percolation on nonamenable Cayley graphs
• Random Walks on Infinite Graphs and Groups
• Symmetric Random Walks on Groups
• The Dixmier problem, lamplighters and Burnside groups
• Topics in orbit equivalence

Cited in

(2)

• Percolation on hyperbolic graphs
• The Expected Length of a Minimal Spanning Tree of a Cylinder Graph

This page was built for publication: The expected degree of minimal spanning forests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5915869)