Bias matroids with unique graphical representations

Given a 3-connected biased graph Ω with three node-disjoint unbalanced circles, at most one of which is a loop, we describe how the bias matroid of Ω is uniquely represented by Ω.     

A characterization of some graph classes using excluded minors

In this article we present a structural characterization of graphs without K ₅ and the octahedron as a minor. We introduce semiplanar graphs as arbitrary sums of planar graphs, and give their characterization in terms of excluded minors. Some other excluded minor theorems for 3-connected minors are shown. Communicated by Attila Pethő     

Random graphs containing few disjoint excluded minors

The Erd?s‐Pósa theorem (1965) states that in each graph G which contains at most k disjoint cycles, there is a ‘blocking’ set B of at most f(k) vertices such that the graph G – B is acyclic. Robertson and Seymour (1986) give an extension concerning any minor‐closed class of graphs, as long as does not contain all planar graphs: in each graph G which contains at most k disjoint excluded minors for , there is a set B of at most g(k) vertices such that G – B is in . In an earlier paper (Kurauskas and McDiarmid, Combin, Probab Comput 20 (2011) 763–775), we showed that, amongst all graphs on vertex set which contain at most k disjoint cycles, all but an exponentially small proportion contain a blocking set of just k vertices. In the present paper we build on the previous work, and give an extension concerning any minor‐closed graph class with 2‐connected excluded minors, as long as does not contain all fans (here a ‘fan’ is a graph consisting of a path together with a vertex joined to each vertex on the path). We show that amongst all graphs G on which contain at most k disjoint excluded minors for , all but an exponentially small proportion contain a set B of k vertices such that G – B is in . (This is not the case when contains all fans.) For a random graph R_n sampled uniformly from the graphs on with at most k disjoint excluded minors for , we consider also vertex degrees and the uniqueness of small blockers, the clique number and chromatic number, and the probability of being connected. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 240‐268, 2014     

Nowhere zero 4‐flow in regular matroids

Jensen and Toft 8 conjectured that every 2‐edge‐connected graph without a K₅‐minor has a nowhere zero 4‐flow. Walton and Welsh 19 proved that if a coloopless regular matroid M does not have a minor in {M(K_3,3), M*(K₅)}, then M admits a nowhere zero 4‐flow. In this note, we prove that if a coloopless regular matroid M does not have a minor in {M(K₅), M*(K₅)}, then M admits a nowhere zero 4‐flow. Our result implies the Jensen and Toft conjecture. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On minors of non-binary matroids

No binary matroid has a minor isomorphic toU ₄ ² , the “four-point line”, and Tutte showed that, conversely, every non-binary matroid has aU ₄ ² minor. However, more can be said about the element sets ofU ₄ ² minors and their distribution. Bixby characterized those elements which are inU ₄ ² minors; a matroidM has aU ₄ ² minor using elementx if and only if the connected component ofM containingx is non-binary. We give a similar (but more complicated) characterization for pairs of elements. In particular, we prove that for every two elements of a 3-connected non-binary matroid, there is aU ₄ ² minor using them both.     

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.     

On some algorithmic aspects of hypergraphic matroids

Hypergraphic matroids were studied first by Lorea [23] and later by Frank et al. [11]. They can be seen as generalizations of graphic matroids. Here we show that several algorithms developed for the graphic case can be extended to hypergraphic matroids. We treat the following: the separation problem for the associated polytope, testing independence, separation of partition inequalities, computing the rank of a set, computing the strength, computing the arboricity and network reinforcement.     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

On minor-minimally 3-connected binary matroids

A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each e∈E(M), either M?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.     

闭模糊拟阵模糊圈的算法研究

用闭模糊拟阵的基本序列来研究和描述它的模糊圈,找到了从闭模糊拟阵的模糊相关集或模糊独立集计算模糊圈的方法,并给出了相应的算法.     

Orientable arithmetic matroids

The theory of matroids has been generalized to oriented matroids and, recently, to arithmetic matroids. We want to give a definition of “oriented arithmetic matroid” and prove some properties like the “uniqueness of orientation”.     

Properties of matroids characterizable in terms of excluded matroids

Some properties π of matroids are characterizable in terms of a set S(π) of exluded matroids, that is, a matroid M satisfies property π if and only if M has no minor (series-minor, parallel-minor) isomorphic to a matroid in S(π). This note presents a necessary and sufficient condition for a property to be characterizable in terms of excluded 3-connected matroids.     

On 3-connected minors of 3-connected matroids and graphs

Whittle proved, for k=1,2, that if N is a 3-connected minor of a 3-connected matroid M, satisfying r(M)−r(N)≥k, then there is a k-independent set I of M such that, for every x∈I, si(M/x) is a 3-connected matroid with an N-minor. In this paper, we establish this result for k=3. It is already known that it cannot be extended to greater values of k. But, here we also show that, in the graphic case, with the extra assumption that r(M)−r(N)≥6, we can guarantee the existence of a 4-independent set of M with such a property. Moreover, in the binary case, we show that if r(M)−r(N)≥5, then M has such a 4-independent set or M has a triangle T meeting 3 triads and such that M/T is a 3-connected matroid with an N-minor.     

Characterizing graphic matroids by a system of linear equations

Given a rank-r   binary matroid we construct a system of O(r³)$O(r^3)$ linear equations in O(r²)$O(r^2)$ variables that has a solution over GF(2)$\mathrm{GF}(2)$ if and only if the matroid is graphic.