Hyperfinite graphings and combinatorial optimization (Q2220974)

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.