In mathematics, a polymatroid is a
polytope
In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...
associated with a
submodular function
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
. The notion was introduced by
Jack Edmonds
Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...
in 1970.
It is also described as the
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the multiplicity of that e ...
analogue of the
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
.
Definition
Let
be a finite
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
and
a non-decreasing
submodular function
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an ...
, that is, for each
we have
, and for each
we have
. We define the polymatroid associated to
to be the following
polytope
In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...
:
.
When we allow the entries of
to be negative we denote this polytope by
, and call it the extended polymatroid associated to
.
An equivalent definition
Let
be a finite
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
and
. We call the ''modulus'' of
to be the sum of all of its entries, denoted
, and denote
whenever
for every
(notice that this gives an
order
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
to
). A polymatroid on the ground set
is a nonempty
compact
Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to:
* Interstate compact
* Blood compact, an ancient ritual of the Philippines
* Compact government, a type of colonial rule utilized in British ...
subset
in
, the set of independent vectors, such that:
# We have that if
, then
for every
:
# If
with
, then there is a vector
such that
.
This definition is equivalent to the one described before,
where
is the function defined by
for every
.
Relation to matroids
To every
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
on the ground set
we can associate the set
, where for every
we have that
By taking the convex hull of
we get a polymatroid, in the sense of the second definition, associated to the rank function of
.
Relation to generalized permutahedra
Because
generalized permutahedra can be constructed from submodular functions, and every generalized permutahedron has an associated submodular function, we have that there should be a correspondence between generalized permutahedra and polymatroids. In fact every polymatroid is a generalized permutahedron that has been translated to have a vertex in the origin. This result suggests that the combinatorial information of polymatroids is shared with generalized permutahedra.
Properties
is nonempty if and only if
and that
is nonempty if and only if
.
Given any extended polymatroid
there is a unique submodular function
such that
and
.
Contrapolymatroids
For a
supermodular
In mathematics, a function
:f\colon \mathbb^k \to \mathbb
is supermodular if
:
f(x \uparrow y) + f(x \downarrow y) \geq f(x) + f(y)
for all x, y \isin \mathbb^, where x \uparrow y denotes the componentwise maximum and x \downarrow y the componentw ...
''f'' one analogously may define the contrapolymatroid
:
This analogously generalizes the dominant of the ''
spanning set
In mathematics, the linear span (also called the linear hull or just span) of a set of vectors (from a vector space), denoted , pp. 29-30, ยงยง 2.5, 2.8 is defined as the set of all linear combinations of the vectors in . It can be characterized ...
polytope
In elementary geometry, a polytope is a geometric object with flat sides (''faces''). Polytopes are the generalization of three-dimensional polyhedra to any number of dimensions. Polytopes may exist in any general number of dimensions as an -d ...
'' of matroids.
Discrete polymatroids
When we only focus on the
lattice points
In geometry and group theory, a lattice in the real coordinate space \mathbb^n is an infinite set of points in this space with the properties that coordinate wise addition or subtraction of two points in the lattice produces another lattice poin ...
of our polymatroids we get what is called, discrete polymatroids. Formally speaking, the definition of a
discrete
Discrete may refer to:
*Discrete particle or quantum in physics, for example in quantum theory
* Discrete device, an electronic component with just one circuit element, either passive or active, other than an integrated circuit
*Discrete group, a ...
polymatroid goes exactly as the one for polymatroids except for where the vectors will live in, instead of
they will live in
. This combinatorial object is of great interest because of their relationship to
monomial ideals.
References
;Footnotes
;Additional reading
*
*
*{{Citation, last=Narayanan, first=H., year= 1997 , title=Submodular Functions and Electrical Networks, isbn= 0-444-82523-1
Matroid theory