<p>Consider a ground set $U=\{1,2,...,n\}$ and the set $\mathcal{F}$ of all non-negative submodular functions $f: 2^U \mapsto \mathbb{R}_{\geq 0}$. The set $\mathcal{F}$ is closed under taking linear combinations of elements but with non-negative coefficients, and hence it forms a cone. 
Question: does this cone have $O(2^{poly(n)})$ number of extreme rays?</p>

<p>In other words, does there exist a set $\mathcal{B} \subseteq \mathcal{F}$ of non-negative submodular functions over $U$ such that any non-negative submodular function $f$ over $U$ can be represented as $f = \sum_{b\in \mathcal{B}}  \gamma_b \cdot b$ for $\gamma_b \in \mathbb{R}_{\geq 0}$, and such that the size of $\mathcal{B}$ is exponential in $n$?
I don't need a characterization of set $\mathcal{B}$, just quantify its size.</p>

<p>I came across this paper <a href="https://www.jstor.org/stable/1997813?seq=21#page_scan_tab_contents" rel="nofollow noreferrer">https://www.jstor.org/stable/1997813?seq=21#page_scan_tab_contents</a> which in Section 2.1 states that such a cone has just $O(2^n\cdot n^2)$ facets, because we can define such a cone as an intersection of $O(2^n\cdot n^2)$ halfspaces each defined for a different triple $(X ,x,y) \subseteq 2^U \cdot U \cdot U$ by $f(X+x)+f(X+y)-f(X + x + y) -f(X) \geq 0$. I have a hard time reading the paper, so can someone tell me if this argument is already answering my question?</p>

<p>I will greatly appreciate any help. </p>

<p>EDIT: Would it change a lot, if we would be considering only monotone submodular functions? </p>

CC BY-SA 3.0
2017-03-27T23:09:28.170Z
A centrally symmetric polytope with polynomially many facets (in terms of dimension) must have exponentially many vertices. If you can intersect this cone with a hyperplane to get a polytope with a center of symmetry, then the extremal rays would correspond to vertices, and you will get an exponential in $2^n$ (i.e. doubly exponential) lower bound. But I have no clue if there is such symmetry here.
Sasho Nikolov
CC BY-SA 3.0
2017-03-27T23:38:22.367Z
Thanks Sasho for answering, although I hope your argument doesn't work --- however unpolite it sounds;) I think that if it would work without any additional argumentation, i.e., only with the symmetry, then this could also work for some subclasses of submodular functions like alternating ones http://www.sciencedirect.com/science/article/pii/S0012365X16300267 Theorem 3.3, but for them there exist exponentially many rays. So I guess that doubly exponential lowerbound would require more work. Then again, it's just a loose thought of mine.
Marek Adamczyk
CC BY-SA 3.0
2017-03-28T00:09:03.980Z
It's likely that the symmetry is not there. Note that for this argument you need two things: symmetry, and an exponential number of facets.
Sasho Nikolov
CC BY-SA 3.0
2017-04-02T12:45:21.237Z
Just in case you find it useful: The paper Supermodular Functions on Finite Lattices by Promislow and Young (Order, 2005, 22:389), 10.1007/s11083-005-9026-5, doesn't talk about the size of \cal B but it gives precise characterisations of \cal B in interesting special cases.
Standa Zivny
CC BY-SA 3.0
2017-04-03T16:34:41.257Z
Would it change a lot, if we would be considering only monotone submodular functions?
Marek Adamczyk
<submodularity>
Extreme rays of the cone of submodular functions
Marek Adamczyk
# Extreme rays of the cone of submodular functions

(Asked by: username_0 on 2017-03-27)

Consider a ground set $U=\{1,2,...,n\}$ and the set $\mathcal{F}$ of all non-negative submodular functions $f: 2^U \mapsto \mathbb{R}\_{\geq 0}$. The set $\mathcal{F}$ is closed under taking linear combinations of elements but with non-negative coefficients, and hence it forms a cone.
Question: does this cone have $O(2^{poly(n)})$ number of extreme rays?

In other words, does there exist a set $\mathcal{B} \subseteq \mathcal{F}$ of non-negative submodular functions over $U$ such that any non-negative submodular function $f$ over $U$ can be represented as $f = \sum\_{b\in \mathcal{B}} \gamma\_b \cdot b$ for $\gamma\_b \in \mathbb{R}\_{\geq 0}$, and such that the size of $\mathcal{B}$ is exponential in $n$?
I don't need a characterization of set $\mathcal{B}$, just quantify its size.

I came across this paper <https://www.jstor.org/stable/1997813?seq=21#page_scan_tab_contents> which in Section 2.1 states that such a cone has just $O(2^n\cdot n^2)$ facets, because we can define such a cone as an intersection of $O(2^n\cdot n^2)$ halfspaces each defined for a different triple $(X ,x,y) \subseteq 2^U \cdot U \cdot U$ by $f(X+x)+f(X+y)-f(X + x + y) -f(X) \geq 0$. I have a hard time reading the paper, so can someone tell me if this argument is already answering my question?

I will greatly appreciate any help.

EDIT: Would it change a lot, if we would be considering only monotone submodular functions?

**Tags:** submodularity
> **Comments:**
> **username_1**: A centrally symmetric polytope with polynomially many facets (in terms of dimension) must have exponentially many vertices. If you can intersect this cone with a hyperplane to get a polytope with a center of symmetry, then the extremal rays would correspond to vertices, and you will get an exponential in $2^n$ (i.e. doubly exponential) lower bound. But I have no clue if there is such symmetry here.  
> **username_0**: Thanks Sasho for answering, although I hope your argument doesn't work --- however unpolite it sounds;) I think that if it would work without any additional argumentation, i.e., only with the symmetry, then this could also work for some subclasses of submodular functions like alternating ones http://www.sciencedirect.com/science/article/pii/S0012365X16300267 Theorem 3.3, but for them there exist exponentially many rays. So I guess that doubly exponential lowerbound would require more work. Then again, it's just a loose thought of mine.  
> **username_1**: It's likely that the symmetry is not there. Note that for this argument you need two things: symmetry, and an exponential number of facets.  
> **username_2**: Just in case you find it useful: The paper Supermodular Functions on Finite Lattices by Promislow and Young (Order, 2005, 22:389), 10.1007/s11083-005-9026-5, doesn't talk about the size of \cal B but it gives precise characterisations of \cal B in interesting special cases.  
> **username_0**: Would it change a lot, if we would be considering only monotone submodular functions?  

---

## 0 answers

