THE CRITICAL PROBLEM FOR POLYMATROIDS
THE CRITICAL PROBLEM FOR POLYMATROIDS
复制标题
多形体的关键问题
DOI：
10.1093/qmath/45.1.117
复制
发表时间：
1994
影响因子：
0.7
通讯作者：
G. Whittle
中科院分区：
文献类型：
--
作者：
G. Whittle
设5是GF (q)上的秩r向量空间V （r, q）的子空间的集合。在V （r, q）中不包含5中的元素的子空间中，设U为秩最大的子空间。在U中所有子空间的秩都小于等于1的特殊情况下，上述问题得到了很好的研究。从本质上讲，这是Crapo和Rota b[2]开发的拟阵的关键问题。证明了U的秩只与矩阵5的矩阵结构有关，并且由矩阵5的特征多项式的求值决定。在本文中，我们证明了在更一般的情况下也有类似的结果。在这种情况下，U的秩仅取决于U的多矩阵结构，并由该多矩阵的特征多项式的求值决定。在第3节中提出的主要结果是对标准拟阵理论的直接多拟阵理论推广。有了第2节中建立的一些多拟阵理论的初步证明，证明就很简单了。鉴于此，本文中的材料可能需要一些理由，本介绍的其余部分将致力于此。
LET 5 be a collection of subspaces of V (r, q), the rank-r vector space over GF (q). Of the subspaces of V (r, q) which contain no member of 5, let U be one with maximum rank. What is the rank of Ul In the special case that the subspaces in U all have rank less than or equal to 1, the above problem is well-studied. It is, in essence, the critical problem for matroids developed by Crapo and Rota [2]. There it is shown that the rank of U depends only on the matroid structure of 5 and that it is determined by an evaluation of the characteristic polynomial of this matroid. In this paper we show that a similar result holds in the more general case. In this case, the rank of U depends only on the poly matroid structure of U and is determined by an evaluation of the characteristic polynomial of this polymatroid.The main results, presented in Section 3, are direct polymatroidtheoretic generalisations of the standard matroid-theoretic ones. With some polymatroid-theoretic preliminaries, established in Section 2, the proofs are very simple. Given this, the material in this paper perhaps needs some justification and the remainder of this introduction is devoted to this.