Polymatroid

Polymatroid

Codes

Published in Joanna A. Ellis-Monaghan, Iain Moffatt, Handbook of the Tutte Polynomial and Related Topics, 2022

A third way to generalize Greene's theorem and the critical theorem is to replace matroids by more general structures. Helgason and Whittle proved a polymatroid generalization of the critical theorem (see [731, 1160, 1162]); Ardila [32] provided hyperplane arrangement generalizations; Farr [474–476] and Britz and Shiromoto [218] proved purely set-theoretical generalizations of Greene's theorem; and similar earlier work is described in the excellent exposition by Kung [731]. As described in Section 16.5, Cameron [262] found a polynomial that simultaneously generalizes the Tutte polynomial and the cycle index of a certain group; see also [263, 264, 266, 267, 975].

On basic operations related to network induction of discrete convex functions

View Article

Journal Information

Published in Optimization Methods and Software, 2021

Kazuo Murota

Here is a supplement to Theorem 3.7. These statements are reformulations of known facts in matroid/polymatroid/submodular function theory (see, e.g.[4,11,18,47]). Parts (1) and (2) for M-convex and M-convex sets are variants of the statement that an integral polymatroid (defined in terms of independent sets or bases) is transformed to another integral polymatroid through Menger-type linkings in a given directed graph. Part (3) for simultaneous exchange jump systems is a special case of [39, Theorem 4.12]. Part (4) for constant-parity jump systems is a special case of [21, Theorem 14].

Explore chapters and articles related to this topic

Codes

On basic operations related to network induction of discrete convex functions