Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization

Bisubmodular functions are a natural “directed”, or “signed”, extension of submodular functions with several applications. Recently Fujishige and Iwata showed how to extend the Iwata, Fleischer, and Fujishige (IFF) algorithm for submodular function minimization (SFM) to bisubmodular function minimization (BSFM). However, they were able to extend only the weakly polynomial version of IFF to BSFM. Here we investigate the difficulty that prevented them from also extending the strongly polynomial version of IFF to BSFM, and we show a way around the difficulty. This new method gives a somewhat simpler strongly polynomial SFM algorithm, as well as the first combinatorial strongly polynomial algorithm for BSFM. This further leads to extending Iwata’s fully combinatorial version of IFF to BSFM. The research of S. T. McCormick was supported by an NSERC Operating Grant. The research of S. Fujishige was supported by a Grant-in-Aid of the Ministry of Education, Culture, Science and Technology of Japan.     

Global Rank Axioms for Poset Matroids

An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained.     

Two Remarks Concerning Balanced Matroids

The property of balance (in the sense of Feder and Mihail) is investigated in the context of paving matroids. The following examples are exhibited: (a) a class of “sparse” paving matroids that are balanced, but at the same time rich enough combinatorially to permit the encoding of hard counting problems; and (b) a paving matroid that is not balanced. The computational significance of (a) is the following. As a consequence of balance, there is an efficient algorithm for approximating the number of bases of a sparse paving matroid within specified relative error. On the other hand, determining the number of bases exactly is likely to be computationally intractable. * The work described here was supported by the grant “Sharper analysis of randomised algorithms” from the UK Engineering and Physical Sciences Research Council.     

Directed submodularity,ditroids and directed submodular flows

Set relations and operations such as inclusion, union and intersection are generalized to directed subsets whose elements are distinguished between forward and backward elements. The concepts of submodular functions, matroids and polymatroidal network flows are extended to the concepts of directed submodular functions, ditroids and directed submodular flows on directed subsets. Two unrelated matroids (submodular functions) can be embedded in one ditroid (directed submodular function). Total dual integrality is preserved in these generalizations and proved for very general set-function class-directed odd submodular functions.This work was partially supported by Chinese National Natural Science Fund.     

Recognizing graphic matroids

There is no polynomially bounded algorithm to test if a matroid (presented by an “independence oracle”) is binary. However, there is one to test graphicness. Finding this extends work of previous authors, who have given algorithms to test binary matroids for graphicness. Our main tool is a new result that ifM′ is the polygon matroid of a graphG, andM is a different matroid onE(G) with the same rank, then there is a vertex ofG whose star is not a cocircuit ofM.     

Equivalence classes of functions between finite groups

Two types of equivalence relation are used to classify functions between finite groups into classes which preserve combinatorial and algebraic properties important for a wide range of applications. However, it is very difficult to tell when functions equivalent under the coarser (“graph”) equivalence are inequivalent under the finer (“bundle”) equivalence. Here we relate graphs to transversals and splitting relative difference sets (RDSs) and introduce an intermediate relation, canonical equivalence, to aid in distinguishing the classes. We identify very precisely the conditions under which a graph equivalence determines a bundle equivalence, using transversals and extensions. We derive a new and easily computed algebraic measure of nonlinearity for a function f, calculated from the image of its coboundary ∂f. This measure is preserved by bundle equivalence but not by the coarser equivalences. It takes its minimum value if f is a homomorphism, and takes its maximum value if the graph of f contains a splitting RDS.     

Minimizing submodular functions over families of sets

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting cases, there exist two elementsa andb of the groundset such that the problem is equivalent to the problem of minimizing the submodular function over the sets containinga but notb. This leads to a polynomial-time algorithm for minimizing a submodular function over these families of sets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets separating two given vertices, or to the complement of a lattice family of subsets. We also derive that the second smallest value of a submodular function over a lattice family can be computed in polynomial-time. These results generalize and unify several known results.Research partially supported by NSF contract 9302476-CCR, Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.     

Decomposition of submodular functions

A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed.     

Extremal Problems For Transversals In Graphs With Bounded Degree

We introduce and discuss generalizations of the problem of independent transversals. Given a graph property , we investigate whether any graph of maximum degree at most d with a vertex partition into classes of size at least p admits a transversal having property . In this paper we study this problem for the following properties : “acyclic”, “H-free”, and “having connected components of order at most r”. We strengthen a result of [13]. We prove that if the vertex set of a d-regular graph is partitioned into classes of size d+⌞d/r⌟, then it is possible to select a transversal inducing vertex disjoint trees on at most r vertices. Our approach applies appropriate triangulations of the simplex and Sperner’s Lemma. We also establish some limitations on the power of this topological method. We give constructions of vertex-partitioned graphs admitting no independent transversals that partially settles an old question of Bollobás, Erdős and Szemerédi. An extension of this construction provides vertex-partitioned graphs with small degree such that every transversal contains a fixed graph H as a subgraph. Finally, we pose several open questions. * Research supported by the joint Berlin/Zurichgrad uate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich. † Research partially supported by Hungarian National Research Fund grants T-037846, T-046234 and AT-048826.     

The Geometry of Standard Deontic Logic

Whereas geometrical oppositions (logical squares and hexagons) have been so far investigated in many fields of modal logic (both abstract and applied), the oppositional geometrical side of “deontic logic” (the logic of “obligatory”, “forbidden”, “permitted”, . . .) has rather been neglected. Besides the classical “deontic square” (the deontic counterpart of Aristotle’s “logical square”), some interesting attempts have nevertheless been made to deepen the geometrical investigation of the deontic oppositions: Kalinowski (La logique des normes, PUF, Paris, 1972) has proposed a “deontic hexagon” as being the geometrical representation of standard deontic logic, whereas Joerden (jointly with Hruschka, in Archiv für Rechtsund Sozialphilosophie 73:1, 1987), McNamara (Mind 105:419, 1996) and Wessels (Die gute Samariterin. Zur Struktur der Supererogation, Walter de Gruyter, Berlin, 2002) have proposed some new “deontic polygons” for dealing with conservative extensions of standard deontic logic internalising the concept of “supererogation”. Since 2004 a new formal science of the geometrical oppositions inside logic has appeared, that is “n-opposition theory”, or “NOT”, which relies on the notion of “logical bi-simplex of dimension m” (m = n − 1). This theory has received a complete mathematical foundation in 2008, and since then several extensions. In this paper, by using it, we show that in standard deontic logic there are in fact many more oppositional deontic figures than Kalinowski’s unique “hexagon of norms” (more ones, and more complex ones, geometrically speaking: “deontic squares”, “deontic hexagons”, “deontic cubes”, . . ., “deontic tetraicosahedra”, . . .): the real geometry of the oppositions between deontic modalities is composed by the aforementioned structures (squares, hexagons, cubes, . . ., tetraicosahedra and hyper-tetraicosahedra), whose complete mathematical closure happens in fact to be a “deontic 5-dimensional hyper-tetraicosahedron” (an oppositional very regular solid).      

A Characterization of Mixed Branching Greedoids

Branching greedoids have been defined and characterized for both directed and undirected rooted graphs. Such greedoids can be extended to rooted mixed graphs – graphs with both directed and undirected edges. These greedoids are characterized by a list of forbidden minors. If Ω is a rooted mixed graph, its mixed branching greedoid has the edges of Ω as its ground set and the collection of arborescences as its feasible sets. The set of mixed branching greedoids is exactly the set of local forest greedoids without

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

Quasi-randomness and the distribution of copies of a fixed graph

We show that if a graph G has the property that all subsets of vertices of size n/4 contain the “correct” number of triangles one would expect to find in a random graph G(n, 1/2), then G behaves like a random graph, that is, it is quasi-random in the sense of Chung, Graham, and Wilson [6]. This answers positively an open problem of Simonovits and Sós [10], who showed that in order to deduce that G is quasi-random one needs to assume that all sets of vertices have the correct number of triangles. A similar improvement of [10] is also obtained for any fixed graph other than the triangle, and for any edge density other than 1/2. The proof relies on a theorem of Gottlieb [7] in algebraic combinatorics, concerning the rank of set inclusion matrices.     

On Brylawski’s Generalized Duality

We introduce a notion of duality??due to Brylawski??that generalizes matroid duality to arbitrary rank functions. This allows us to define a generalization of the matroid Tutte polynomial. This polynomial satisfies a deletion-contraction recursion, where deletion and contraction are defined in this more general setting. We explore this notion of duality for greedoids, antimatroids and demi-matroids, proving that matroids correspond precisely to objects that are simultaneously greedoids and ??dual?? greedoids.     

The universal partition theorem for oriented matroids

We consider realization spaces of a family of oriented matroids of rank three as point configurations in the affine plane. The fundamental problem arises as to which way these realization spaces partition their embedding space. The Universal Partition Theorem roughly states that such a partition can be as complicated as any partition of ℝ ⁿ into elementary semialgebraic sets induced by an arbitrary finite set of polynomials in ℤ[X]. We present the first proof of the Universal Partition Theorem. In particular, it includes the first complete proof of the so-called Universality Theorem. This work was supported by the Deutsche Forschungsgemeinschaft, Graduiertenkolleg “Analyse und Konstruktion in der Mathematik”.     

How canonical is the canonical model? A comment on Aumann's interactive epistemology

Aumann (1989) argued that the natural partitions on the space of all maximally consistent sets of formulas in multi-player S5 logic are necessarily “commonly known” by the players. We show, however, that there are many other sets of partitions on this space that conform with the formulas that build the states – as many as there are subsets of the continuum! Thus, assuming a set of partitions on this space is “common knowledge” is an informal but meaningful meta-assumption.     

Matroid Enumeration for Incidence Geometry

Matroids are combinatorial abstractions for point configurations and hyperplane arrangements, which are fundamental objects in discrete geometry. Matroids merely encode incidence information of geometric configurations such as collinearity or coplanarity, but they are still enough to describe many problems in discrete geometry, which are called incidence problems. We investigate two kinds of incidence problem, the points–lines–planes conjecture and the so-called Sylvester–Gallai type problems derived from the Sylvester–Gallai theorem, by developing a new algorithm for the enumeration of non-isomorphic matroids. We confirm the conjectures of Welsh–Seymour on ≤11 points in ℝ³ and that of Motzkin on ≤12 lines in ℝ², extending previous results. With respect to matroids, this algorithm succeeds to enumerate a complete list of the isomorph-free rank 4 matroids on 10 elements. When geometric configurations corresponding to specific matroids are of interest in some incidence problems, they should be analyzed on oriented matroids. Using an encoding of oriented matroid axioms as a boolean satisfiability (SAT) problem, we also enumerate oriented matroids from the matroids of rank 3 on n≤12 elements and rank 4 on n≤9 elements. We further list several new minimal non-orientable matroids.     

基于覆盖上近似算子的拟阵结构及其关系

Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.     

A KAM phenomenon for singular holomorphic vector fields

Let X be a germ of holomorphic vector field at the origin of Cⁿ and vanishing there. We assume that X is a good perturbation of a “nondegenerate” singular completely integrable system. The latter is associated to a family of linear diagonal vector fields which is assumed to have nontrivial polynomial first integrals (they are generated by the so called “resonant monomials”). We show that X admits many invariant analytic subsets in a neighborhood of the origin. These are biholomorphic to the intersection of a polydisc with an analytic set of the form “resonant monomials = constants”. Such a biholomorphism conjugates the restriction of X to one of its invariant varieties to the restriction of a linear diagonal vector field to a toric variety. Moreover, we show that the set of “frequencies” defining the invariant sets is of positive measure.