Some excluded-minor theorems for a class of polymatroids
type: Item
instance of: scholarly article
title: Some excluded-minor theorems for a class of polymatroids
zbMATH Open document ID: 0793.05041
DOI: 10.1007/BF01303518
published in: Combinatorica
publication date: 1994-08-10T00:00:00Z
review text: A polymatroid function \(h: 2^ S\rightarrow{\mathbf Z}\) is Boolean if it can be represented in the form \(h(A)=|\bigcup_{a\in A}\phi(A)|\) for a set function \(\phi: S\rightarrow 2^ V\). In this paper the authors develop criteria that help to identify excluded minors for classes of Boolean polymatroids. In particular, they show that there are infinitely many excluded minors (non-Boolean polymatroids such that every proper minor is Boolean), while for Boolean \(k\)-polymatroids (i.e., \(|\phi(A)|\leq k\) for all \(a\in S\)) all excluded minors have size at most \(k+2\), and thus their set of excluded minors is finite. The complete list of eight excluded minors is determined for the class of Boolean 2-polymatroids, which correspond to graphs.
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 522717
zbMATH Keywords: set systems
zbMATH Keywords: representation of polymatroids
zbMATH Keywords: graph classes
zbMATH Keywords: polymatroid
zbMATH Keywords: set function
zbMATH Keywords: excluded minors
author: James Oxley
author: Geoff Whittle
reviewed by: Günter M. Ziegler
MaRDI profile type: Publication
cites work: Decomposition of submodular functions
cites work: Q4053708
cites work: The Redei function of a relation
cites work: THE CRITICAL PROBLEM FOR POLYMATROIDS
cites work: A geometric theory of hypergraph colouring
full work available at URL: https://doi.org/10.1007/bf01303518
OpenAlex ID: W2004779176
Recommended article: On an excluded-minor class of matroids
Recommended article: On excluded minors for classes of graphical matroids
Recommended article: Excluded minors for Boolean polymatroids
Recommended article: A characterization of certain excluded-minor classes of matroids
Recommended article: An excluded-minor problem in matroids
Recommended article: Excluded minors for matroids satisfying Kinser's inequalities
Recommended article: The excluded minors for near-regular matroids
Recommended article: The excluded minors for lattice path polymatroids
Recommended article: The Excluded Minors for Three Classes of 2-Polymatroids Having Special Types of Natural Matroids
Recommended article: Excluded minors for the class of split matroids
description: scientific article; zbMATH DE number 522717