Search results for "Matroid"
showing 4 items of 4 documents
On Banaschewski functions in lattices
1991
hold for all x, y ~ X. We call such a function z a Banaschewski function or a B-function on X. A lattice L is a B-lattice or antitonely complemented, if there is a B-function defined on the whole lattice L. For instance, Boolean lattices as well as orthocomplemented lattices are B-lattices. On the other hand, a B-lattice is not necessarily Boolean or orthocomplemented, although a distributive B-lattice is a Boolean lattice. It is shown later that a matroid (geometric) lattice is also a B-lattice. Naturally, our results include the lemma of Banaschewski [ 1, Lemma 4], by which the lattice of the subspaces of a vector space is a B-lattice. It should be emphasized that a B-function is supposed…
Feynman graph polynomials
2010
The integrand of any multi-loop integral is characterised after Feynman parametrisation by two polynomials. In this review we summarise the properties of these polynomials. Topics covered in this article include among others: Spanning trees and spanning forests, the all-minors matrix-tree theorem, recursion relations due to contraction and deletion of edges, Dodgson's identity and matroids.
Matroid optimization problems with monotone monomials in the objective
2022
Abstract In this paper we investigate non-linear matroid optimization problems with polynomial objective functions where the monomials satisfy certain monotonicity properties. Indeed, we study problems where the set of non-linear monomials consists of all non-linear monomials that can be built from a given subset of the variables. Linearizing all non-linear monomials we study the respective polytope. We present a complete description of this polytope. Apart from linearization constraints one needs appropriately strengthened rank inequalities. The separation problem for these inequalities reduces to a submodular function minimization problem. These polyhedral results give rise to a new hiera…
A Constructive Arboricity Approximation Scheme
2020
The arboricity \(\varGamma \) of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they approximate the arboricity as a value without computing a corresponding forest partition. This is because they operate on pseudoforest partitions or the dual problem of finding dense subgraphs.