Id: arxiv/2603.10710 Url: https://arxiv.org/abs/2603.10710 Tags: math.CO, cs.DS Score: 0 Title: Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions Domain: math.CO Source: arxiv Authors: Sang-il Oum, Marek Sokołowski Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-03-11 Page: https://delphi.science/r/arxiv/2603.10710 We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining $0$ on the empty set. For a connectivity function $f$ on an $n$-element set $V$ and an integer $k\ge 0$, we show that the family of all sets $X\subseteq V$ with $f(X)=k$ admits a polynomial-size representation: it can be described by a list of at most $O(n^{4k})$ items, each consisting of a set to be included, another set to be excluded, and a partition of remaining elements, such that the union of some members of the partition and the set to be included are precisely all…