# Base polyhedron

Let *V* be a finite ground set, and let [math]b:2^V \to {\mathbb R} \cup \{\infty\}[/math] be a submodular function for which *b(V)* is finite and [math]b(\emptyset) = 0[/math]. The **base polyhedron** of *b* is

[math]B(b)=\{x \in {\mathbb R}^V: x(Z) \leq b(Z)\ \forall Z\subseteq V,\ x(V)=b(V)\}.[/math]

A base polyhedron defined this way is always nonempty. Moreover, if the finite values of *b* are integer, then *B(b)* is an integer polyhedron. If *b* is finite, then the polyhedron is bounded, and it is called a **base polytope**.

The same definition can be used for a crossing submodular function *b*. In this case, the polyhedron may be empty, and non-emptiness is characterized by Fujishige's base polyhedron theorem. However if it is non-empty, then there is a submodular function *b' * for which [math]B(b)=B(b')[/math].