###### László Lovász

Decomposition of graphs is an important tool for the design ofalgorithms as well as for understanding their structure.Hyperfiniteness means that the graph can be decomposed into pieces ofbounded size by removing an arbitrarily small fraction of the edges.This property, which can be defined for a family of finite graphs,but also for graph-limits with bounded degree called "graphings", isvery useful in designing local algorithms for such graphs. But theoptimal decomposition is difficult to compute. We show how methodsfrom combinatorial optimization, namely linear relaxation, can beused to prove basic properties of hyperfiniteness, and also to obtaina decomposition that is almost optimal.

## Want to be notified about upcoming NetSI events? Sign up for our email list below!

Thank you! You have been added to our email list.

Oops! Something went wrong while submitting the form

###### László Lovász

****

Decomposition of graphs is an important tool for the design ofalgorithms as well as for understanding their structure.Hyperfiniteness means that the graph can be decomposed into pieces ofbounded size by removing an arbitrarily small fraction of the edges.This property, which can be defined for a family of finite graphs,but also for graph-limits with bounded degree called "graphings", isvery useful in designing local algorithms for such graphs. But theoptimal decomposition is difficult to compute. We show how methodsfrom combinatorial optimization, namely linear relaxation, can beused to prove basic properties of hyperfiniteness, and also to obtaina decomposition that is almost optimal.