Compression of M#-convex functions --- Flag matroids and valuated permutohedra
Compression of M#-convex functions --- Flag matroids and valuated permutohedra
复制标题
M 的压缩
DOI：
10.1016/j.jcta.2021.105525
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Hirai Hiroshi
中科院分区：
文献类型：
--
作者：
Fujishige Satoru;Hirai Hiroshi
Murota（1998）和Murota and Shioura（1999）引入了M-凸函数和M-凸函数作为离散凸函数的概念，它们是Dress和Wenzel（1992）赋值拟阵的推广。本文考虑一种由M-凸函数的截面卷积定义的新运算，它将给定的M-凸函数变换为M-凸函数，我们称之为M-凸函数的压缩.对于赋值广义拟阵这类特殊的M ∞-凸函数，压缩诱导赋值置换面，并将赋值广义拟阵分解为旗拟阵条，每个旗拟阵条对应于诱导赋值置换面的一个极大线性域.我们研究的旗拟阵条的结构和诱导赋值permutohedron的Murota的离散凸分析。
Murota (1998) and Murota and Shioura (1999) introduced concepts of M-convex function and M♮-convex function as discrete convex functions, which are generalizations of valuated matroids due to Dress and Wenzel (1992). In the present paper we consider a new operation defined by a convolution of sections of an M♮-convex function that transforms the given M♮-convex function to an M-convex function, which we call acompressionof an M♮-convex function. For the class of valuated generalized matroids, which are special M♮-convex functions, the compression induces avaluated permutohedrontogether with a decomposition of the valuated generalized matroid intoflag-matroid strips, each corresponding to a maximal linearity domain of the induced valuated permutohedron. We examine the details of the structure of flag-matroid strips and the induced valuated permutohedron by means of discrete convex analysis of Murota.