Interval Partitions and Activities for the Greedoid Tutte Polynomial
Interval Partitions and Activities for the Greedoid Tutte Polynomial
复制标题
Greedoid Tutte 多项式的区间划分和活动
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Elizabeth W. McMahon
中科院分区：
文献类型：
--
作者：
Gary Gordon;Elizabeth W. McMahon
本文通过外部活动研究了作者在前人工作中引入的二元Gette多项式f(G；t，z)。给出了布尔子集格的两种不同划分，并给出了一个可行的集合展开条件(G)。这三个结果都推广了拟阵的定理。一个区间划分给出了所有拟半群的类中的反拟半群的特征。作为应用，我们证明了当G是与有根有向图D相联系的有向分枝格点群时，除以f(G)的(z+1)的最大幂等于可以从D中去掉的最小边数，从而产生一个无圈有向图，其中D的所有顶点仍然是根可达的。这些结果背后的统一主题是计算树的想法。
The two variable greedoid Tutte polynomialf(G;t,z), which was introduced in previous work of the authors, is studied via external activities. Two different partitions of the Boolean lattice of subsets are derived and a feasible set expansion off(G) is developed. All three of these results generalize theorems for matroids. One interval partition yields a characterization of antimatroids among the class of all greedoids. As an application, we prove that whenGis the directed branching greedoid associated with a rooted digraphD, then the highest power of (z+1) which dividesf(G) equals the minimum number of edges which can be removed fromDto produce an acyclic digraph in which all vertices ofDare still accessible from the root. The unifying theme behind these results is the idea of a computation tree.