Hyperfinite graphings and combinatorial optimization

DOI10.1007/S10474-020-01065-YMaRDI QIDQ2220974zbMATH OpenOpenAlexFDO

Authors László Lovász

Publication date 25 January 2021

Published in Acta Mathematica Hungarica (Search for Journal in Brave)

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

zbMATH Keywords

greedy algorithmsplitting sethyperfinite graphing

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Infinite graphs (05C63) Fractional graph theory, fuzzy graph theory (05C72)

Abstract: We exhibit an analogy between the problem of pushing forward measurable sets under measure preserving maps and linear relaxations in combinatorialoptimization. We show how invariance of hyperfiniteness of graphings under local isomorphism 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.

Recommendations

• Hyperfiniteness and Borel combinatorics
• Compact graphings
• Finite graphs and amenability
• Borel combinatorics of locally finite graphs
• Kőnig's line coloring and Vizing's theorems for graphings

Cites work

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• 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
• 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

Cited in

(5)

• Hyperfiniteness and Borel combinatorics
• scientific article; zbMATH DE number 3910116 (Why is no real title available?)
• Uniform hyperfiniteness
• Flows on measurable spaces
• Compressions, graphs, and hyperreflexivity

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)