<p>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 through their rank functions. Extending the limit theory of bounded degree graphs, which analyzes graph sequences via neighborhood sampling, we address the challenge posed by the absence of a neighborhood concept in matroids. We show that any bounded set function can be approximated by a sequence of finite set functions that quotient-converges to it. In addition, we explicitly construct such sequences for increasing, submodular, and upper continuous set functions, and prove the completeness of the space under quotient-convergence.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quotient-Convergence of Submodular Setfunctions

  • Kristóf Bérczi,
  • Márton Borbényi,
  • László Lovász,
  • László Márton Tóth

摘要

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 through their rank functions. Extending the limit theory of bounded degree graphs, which analyzes graph sequences via neighborhood sampling, we address the challenge posed by the absence of a neighborhood concept in matroids. We show that any bounded set function can be approximated by a sequence of finite set functions that quotient-converges to it. In addition, we explicitly construct such sequences for increasing, submodular, and upper continuous set functions, and prove the completeness of the space under quotient-convergence.