6 papers
Choquet extension of non-monotone submodular setfunctions
László Lovász
In a seminal paper, Choquet introduced an integral formula to extend a monotone increasing setfunction on a sigma-algebra to a (nonlinear) functional on bounded measurable function…
Matroid products via submodular coupling
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the…
Quotient-convergence of Submodular Setfunctions
Kristóf Bérczi, Márton Borbényi, László Lovász +1
We introduce the concept of quotient-convergence for sequences of submodular set functions, providing, among others, a new framework for the study of convergence of matroids throug…
Monotonic Decompositions of Submodular Set Functions
Kristóf Bérczi, Boglárka Gehér, András Imolay +2
Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions ha…
Cycle Matroids of Graphings: From Convergence to Duality
Kristóf Bérczi, Márton Borbényi, László Lovász +1
A recent line of research has concentrated on exploring the links between analytic and combinatorial theories of submodularity, uncovering several key connections between them. In…
The matroid of a graphing
László Lovász
Graphings serve as limit objects for bounded-degree graphs. We define the ``cycle matroid'' of a graphing as a submodular setfunction, with values in [0,1], which generalizes (up t…