Polimatroide

Análogo multiconjunto de matroides

En matemáticas, un polimatroide es un politopo asociado a una función submodular . El concepto fue introducido por Jack Edmonds en 1970. ^[1] También se lo describe como el análogo multiconjunto del matroide .

Definición

Sea un conjunto finito y una función submodular no decreciente , es decir, para cada uno tenemos , y para cada uno tenemos . Definimos el polimatroide asociado a como el siguiente politopo : ${\displaystyle E}$ ${\displaystyle f:2^{E}\rightarrow \mathbb {R} _{+}}$ ${\displaystyle A\subseteq B\subseteq E}$ ${\displaystyle f(A)\leq f(B)}$ ${\displaystyle A,B\subseteq E}$ ${\displaystyle f(A)+f(B)\geq f(A\cup B)+f(A\cap B)}$ ${\displaystyle f}$

${\displaystyle P_{f}={\Big \{}{\textbf {x}}\in \mathbb {R} _{+}^{E}~{\Big |}~\sum _{e\in U}{\textbf {x}}(e)\leq f(U),\forall U\subseteq E{\Big \}}}$.

Cuando permitimos que las entradas de sean negativas, denotamos este politopo por , y lo llamamos polimatroide extendido asociado a . ^[2] ${\displaystyle {\textbf {x}}}$ ${\displaystyle EP_{f}}$ ${\displaystyle f}$

Una definición equivalente

Sea un conjunto finito . Si entonces denotamos por la suma de las entradas de , y escribimos siempre que para cada (nótese que esto da un orden a ). Un polimatroide en el conjunto base es un subconjunto compacto no vacío en , el conjunto de vectores independientes, tal que: ${\displaystyle E}$ ${\displaystyle {\textbf {u}},{\textbf {v}}\in \mathbb {R} ^{E}}$ ${\displaystyle |{\textbf {u}}|}$ ${\displaystyle {\textbf {u}}}$ ${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$ ${\displaystyle {\textbf {v}}(i)-{\textbf {u}}(i)\geq 0}$ ${\displaystyle i\in E}$ ${\displaystyle \mathbb {R} _{+}^{E}}$ ${\displaystyle E}$ ${\displaystyle P}$ ${\displaystyle \mathbb {R} _{+}^{E}}$

1. Tenemos que si , entonces para cada : ${\displaystyle {\textbf {v}}\in P}$ ${\displaystyle {\textbf {u}}\in P}$ ${\displaystyle {\textbf {u}}\leq {\textbf {v}}}$
2. Si con , entonces existe un vector tal que . ${\displaystyle {\textbf {u}},{\textbf {v}}\in P}$ ${\displaystyle |{\textbf {v}}|>|{\textbf {u}}|}$ ${\displaystyle {\textbf {w}}\in P}$ ${\displaystyle {\textbf {u}}<{\textbf {w}}\leq (\max\{{\textbf {u}}(1),{\textbf {v}}(1)\},\dots ,\max\{{\textbf {u}}({|E|}),{\textbf {v}}({|E|})\})}$

Esta definición es equivalente a la descrita anteriormente, ^[3] donde es la función definida por para cada . ${\displaystyle f}$ ${\displaystyle f(A)=\max {\Big \{}\sum _{i\in A}{\textbf {v}}(i)~{\Big |}~{\textbf {v}}\in P{\Big \}}}$ ${\displaystyle A\subset E}$

Relación con los matroides

A cada matroide del conjunto base podemos asociar el conjunto , donde es el conjunto de conjuntos independientes de y denotamos por el vector característico de : para cada ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle V_{M}=\{{\textbf {w}}_{F}~|~F\in {\mathcal {I}}\}}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle M}$ ${\displaystyle {\textbf {w}}_{F}}$ ${\displaystyle F\subset E}$ ${\displaystyle i\in E}$

${\displaystyle {\textbf {w}}_{F}(i)={\begin{cases}1,&i\in F;\\0,&i\not \in F.\end{cases}}}$

Al tomar la envoltura convexa de obtenemos un polimatroide. Está asociado a la función de rango de . Las condiciones de la segunda definición reflejan los axiomas para los conjuntos independientes de un matroide. ${\displaystyle V_{M}}$ ${\displaystyle M}$

Relación con permutaedros generalizados

Como los permutaedros generalizados pueden construirse a partir de funciones submodulares, y cada permutaedro generalizado tiene una función submodular asociada, tenemos que debería haber una correspondencia entre los permutaedros generalizados y los polimatroides. De hecho, cada polimatroides es un permutaedro generalizado que se ha traducido para tener un vértice en el origen. Este resultado sugiere que la información combinatoria de los polimatroides es compartida con los permutaedros generalizados.

Propiedades

${\displaystyle P_{f}}$es no vacío si y solo si y que es no vacío si y solo si . ${\displaystyle f\geq 0}$ ${\displaystyle EP_{f}}$ ${\displaystyle f(\emptyset )\geq 0}$

Dado cualquier polimatroide extendido existe una función submodular única tal que y . ${\displaystyle EP}$ ${\displaystyle f}$ ${\displaystyle f(\emptyset )=0}$ ${\displaystyle EP_{f}=EP}$

Contrapolimatroides

Para una f supermodular se puede definir análogamente el contrapolimatroide

${\displaystyle {\Big \{}w\in \mathbb {R} _{+}^{E}~{\Big |}~\forall S\subseteq E,\sum _{e\in S}w(e)\geq f(S){\Big \}}}$

Esto generaliza de forma análoga el dominante del politopo del conjunto extensor de matroides.

Polimatroides discretos

Cuando nos centramos únicamente en los puntos de la red de nuestros polimatroides obtenemos lo que se denomina polimatroides discretos . Formalmente hablando, la definición de un polimatroid discreto es exactamente la misma que la de los polimatroides, excepto por el lugar en el que vivirán los vectores, en lugar de vivirán en . Este objeto combinatorio es de gran interés debido a su relación con los ideales monomiales . ${\displaystyle \mathbb {R} _{+}^{E}}$ ${\displaystyle \mathbb {Z} _{+}^{E}}$

Referencias

Notas al pie

1. Edmonds, Jack. Funciones submodulares, matroides y ciertos poliedros . 1970. Estructuras combinatorias y sus aplicaciones (Proc. Calgary Internat. Conf., Calgary, Alta., 1969) págs. 69–87 Gordon y Breach, Nueva York. MR 0270945
2. Schrijver, Alexander (2003), Optimización combinatoria , Springer , §44, p. 767, ISBN 3-540-44389-4
3. J. Herzog, T. Hibi. Monomial Ideals . 2011. Textos de posgrado en matemáticas 260, págs. 237–263 Springer-Verlag, Londres.

Lectura adicional

• Lee, Jon (2004), Un primer curso de optimización combinatoria , Cambridge University Press , ISBN 0-521-01012-8
• Fujishige, Satoru (2005), Funciones submodulares y optimización , Elsevier , ISBN 0-444-52086-4
• Narayanan, H. (1997), Funciones submodulares y redes eléctricas , ISBN 0-444-82523-1