Finite graphs and amenability
Author:
Preprint
Abstract
Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph properties. In this paper we propose a unified approach to hyperfiniteness. We establish some new results and give new proofs of theorems of Schramm, Lov\'asz, Newman-Sohler and Ornstein-Weiss.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Weak equivalence and non-classifiability of measure preserving actionsErgodic Theory and Dynamical Systems, 2013
- Sparse graphs: Metrics and random modelsRandom Structures & Algorithms, 2011
- Parameter testing in bounded degree graphs of subexponential growthRandom Structures & Algorithms, 2010
- Every minor-closed property of sparse graphs is testableAdvances in Mathematics, 2010
- Local Graph Partitions for Approximation and Testing2009
- -spectral invariants and convergent sequences of finite graphsJournal of Functional Analysis, 2008
- Note on limits of finite graphsCombinatorica, 2007
- Borel Chromatic NumbersAdvances in Mathematics, 1999
- Amenability, hyperfiniteness, and isoperimetric inequalitiesComptes Rendus de l'Académie des Sciences - Series I - Mathematics, 1997
- Entropy and isomorphism theorems for actions of amenable groupsJournal d'Analyse Mathématique, 1987