Metraipolis › archive › dc_3b75ea6685cd

Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula — arXiv:2610.40032

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.40032
License (as archived)
CC0-1.0
Archived
2026-11-01T02:38:02.986Z
SHA-256 of the archived text
26e2cab3411235da246c50d63819c0b27bd2778b1555b5f0d4618b564b6ca9a6
Stable URL of this page
https://metraipolis.com/documento/dc_3b75ea6685cd

How to cite

Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula — arXiv:2610.40032 — arXiv (en), https://arxiv.org/abs/2610.40032 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3b75ea6685cd (Metraipolis archive dc_3b75ea6685cd, sha256 26e2cab3411235da246c50d63819c0b27bd2778b1555b5f0d4618b564b6ca9a6)
BibTeX
@misc{dc3b75ea6685cd,
  title = {Submodular decompositions: a bounded-variation counterexample and an exact planar cut formula — arXiv:2610.40032},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.40032},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3b75ea6685cd; sha256 26e2cab3411235da246c50d63819c0b27bd2778b1555b5f0d4618b564b6ca9a6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.40032. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Bérczi, Gehér, Imolay, Lovász, and Schwarcz (SIAM J. Discrete Math. 40(2026), 308--335) asked whether every set function of bounded variation is a difference of two bounded submodular functions, and how to determine the optimum in a monotonic sum-decomposition of a planar graph cut function. In this paper, we answer both questions and obtain quantitative extensions. For the first question, we characterize the continuous profiles $f:[0,1]\to\R$ for which $A\mapsto f(m(A))$ is a bounded submodular difference on an atomless probability space. More precisely, we express the minimum oscillation of the subtracted component through the positive part of the distributional second derivative. We also characterize admissible discontinuous profiles and give an exact summability criterion for countable block functions. In particular, the first question has a negative answer even for increasing functions of variation one whose scalar profiles have log-Lipschitz derivatives and belong to every $C^{1,\alpha}$, $0<\alpha<1$. Turning to graph cuts, we prove that the optimum equals the total edge weight minus the maximum fractional triangle-packing weight for every nonnegative weighting if and only if the graph is $K_5$-free. Moreover, maximum packings parametrize the symmetrized optimal components, while on $K_4$-free graphs we describe all optimal components and characterize uniqueness. Consequently, the formula applies to weighted planar graphs and implies edge-weight monotonicity on $K_5$-free graphs. For rational weights, it also yields polynomial-time constructions.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.40032 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:28.287Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).