Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity

arXiv:2601.00140v1 Announce Type: new
Abstract: Diestel, et al. (see Order 35 (2017), JCT-A 167 (2019), arXiv:1805.01439) introduced the notion of abstract separation systems that satisfy a submodularity property, and they call this structural submodularity. Williamson, Goemans, Mihail, and Vazirani (Combinatorica 15 (1995)) call a family of sets $mathcal{F}$ uncrossable if the following holds: for any pair of sets $A,Binmathcal{F}$, both $Acap{B},Acup{B}$ are in $mathcal{F}$, or both $A-B,B-A$ are in $mathcal{F}$. Bansal, Cheriyan, Grout, and Ibrahimpur (Algorithmica 86 (2024), arXiv:2209.11209) call a family of sets $mathcal{F}$ pliable if the following holds: for any pair of sets $A,Binmathcal{F}$, at least two of the sets $Acap{B},Acup{B},A-B,B-A$ are in $mathcal{F}$. We say that a pliable family of sets $mathcal{F}$ satisfies structural submodularity if the following holds: for any pair of crossing sets $A,Binmathcal{F}$, at least one of the sets $Acap{B},Acup{B}$ is in $mathcal{F}$, and at least one of the sets $A-B,B-A$ is in $mathcal{F}$.
For any positive integer $dgeq2$, we construct a pliable family of sets $mathcal{F}$ that satisfies structural submodularity such that (a) there do not exist a symmetric submodular function $g$ and $lambdain{mathbb Q}$ such that $mathcal{F} = { S ,:, g(S)<lambda }$, and (b) $mathcal{F}$ cannot be partitioned into $d$ (or fewer) uncrossable families.