Hyperfinite graphings and combinatorial optimization
A graphing is a Borel graph with bounded (finite) degree on a standard probability space \((I,A,\lambda)\), satisfying a ``measure-preserving condition for any two Borel subsets of \(I\). In this paper an analogy between the problem of pushing forward measurable sets under measure preserving maps and linear relaxations in combinatorial optimization was presented. The author shows how invariance of hyperfiniteness of graphings under local homomorphism can be reformulated as an infinite version of a natural combinatorial optimization problem, and how one can prove it by extending well-known proof techniques (linear relaxation, greedy algorithm, linear programming duality) from the finite case to the infinite. The paper concludes with four open problems.
- Amenability, hyperfiniteness, and isoperimetric inequalities
- Compact graphings
- Efficient testing of large graphs
- Every minor-closed property of sparse graphs is testable
- Finite graphs and amenability
- Harmonic functions on planar and almost planar graphs and manifolds, via circle packings
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- Hyperfinite graph limits
- Large networks and graph limits
- Limits of locally-globally convergent graph sequences
- Local Graph Partitions for Approximation and Testing
- On limits of finite graphs
- On sets of integers containing k elements in arithmetic progression
- On the ratio of optimal integral and fractional covers
- Processes on unimodular random networks
- Quick approximation to matrices and applications
- Szemerédi's regularity Lemma for matrices and sparse graphs
This page was built for publication: Hyperfinite graphings and combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2220974)
