Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908743812251648 |
|---|---|
| author | Simmons, Miles Bansal, Ishan Cheriyan, Joe |
| author_facet | Simmons, Miles Bansal, Ishan Cheriyan, Joe |
| contents | 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,B\in\mathcal{F}$, both $A\cap{B},A\cup{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,B\in\mathcal{F}$, at least two of the sets $A\cap{B},A\cup{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,B\in\mathcal{F}$, at least one of the sets $A\cap{B},A\cup{B}$ is in $\mathcal{F}$, and at least one of the sets $A-B,B-A$ is in $\mathcal{F}$.
For any positive integer $d\geq2$, 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 $λ\in{\mathbb Q}$ such that $\mathcal{F} = \{ S \,:\, g(S)<λ\}$, and (b) $\mathcal{F}$ cannot be partitioned into $d$ (or fewer) uncrossable families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_00140 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity Simmons, Miles Bansal, Ishan Cheriyan, Joe Discrete Mathematics 68W25, 90C27, 05C40 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,B\in\mathcal{F}$, both $A\cap{B},A\cup{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,B\in\mathcal{F}$, at least two of the sets $A\cap{B},A\cup{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,B\in\mathcal{F}$, at least one of the sets $A\cap{B},A\cup{B}$ is in $\mathcal{F}$, and at least one of the sets $A-B,B-A$ is in $\mathcal{F}$. For any positive integer $d\geq2$, 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 $λ\in{\mathbb Q}$ such that $\mathcal{F} = \{ S \,:\, g(S)<λ\}$, and (b) $\mathcal{F}$ cannot be partitioned into $d$ (or fewer) uncrossable families. |
| title | Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity |
| topic | Discrete Mathematics 68W25, 90C27, 05C40 |
| url | https://arxiv.org/abs/2601.00140 |