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.     

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.     

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 Ω.     

Systems of Polynomials for Detecting Orientable Matroids

We study systems of polynomial equations that correspond to a matroid M. Each of these systems has a zero solution if and only if M is orientable. Since determining if a matroid is orientable is NP-complete with respect to the size of the input data, determining if these systems have solutions is also NP-complete. However, we show that one of the associated polynomial systems corresponding to M is linear if M is a binary matroid and thus it may be determined if binary matroids are orientable in polynomial time given the circuits and cocircuits of said matroid as the input. In the case when M is not binary, we consider the associated system of non-linear polynomials. In this case Hilbertʼs Nullstellensatz gives us that M is non-orientable if and only if a certain certificate to the given polynomials system exists. We wish to place bounds on the degree of these certificates in future research.     

Linked tree-decompositions of represented infinite matroids

We prove that a represented infinite matroid having finite tree-width w has a linked tree-decomposition of width at most 2w. This result should be a key lemma in showing that any class of infinite matroids representable over a fixed finite field and having bounded tree-width is well-quasi-ordered under taking minors. We also show that for every finite w, a represented infinite matroid has tree-width at most w if and only if all its finite submatroids have tree-width at most w. Both proofs rely on the use of a notion of chordality for represented matroids.     

The structure of 4-flowers of vertically 4-connected matroids

Aikin and Oxley (2012) [2] studied the structure of 4-flowers in 4-connected matroids. In the paper we consider 4-flowers in vertically 4-connected matroids. There is a natural relation of equivalence on such 4-flowers. We characterize the structure that arises when 4-flowers are equivalent under the relation.     

On the regularity of orientable matroids

We present two characterizations of regular matroids among orientable matroids and use them to give a measure of “how far” an orientable matroid is from being regular.     

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

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

Graphic matroids and the multicommodity transportation problem

A necessary and sufficient condition for unimodularity in the multicommodity transportation problem is established, and the constructive proof yields an equivalent, single commodity network flow problem for the class of problems satisfying the condition. The concept of a graphic matroid is used to establish the transformation.     

可定向闭曲面上保定向的周期映射

讨论可定向闭曲面上保定向周期映射的共轭类分类问题.Kulkarni(1997)指出:亏格g大于3时,曲面上任意周期大于或等于4g的周期映射共轭于两类周期映射中某个映射的幂.之后Hirose(2010)得到:亏格g大于12时,曲面上任意周期大于或等于3g的周期映射共轭于4类周期映射中某个映射的幂.本文在此基础上研究了周期大于或等于3(g-1)的情形:当亏格g大于21时,得到了和Hirose相似的结论,且找出了更多不能被包含在前面所讲的4类周期映射中的情形.     

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.     

Bounding the beta invariant of 3-connected matroids

The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4], Brylawski [2], Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7.     

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.     

On finite matroids with two more hyperplanes than points

One of the most interesting results about finite matroids of finite rank and generalized projective spaces is the result of Basterfield, Kelly and Green (1968/1970) (J.G. Basterfield, L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, in: Proceedings of the Cambridge Philosophical Society, vol. 64, 1968, pp. 585-588; C. Greene, A rank inequality for finite geometric lattices, J. Combin Theory 9 (1970) 357-364) affirming that any matroid contains at least as many hyperplanes as points, with equality in the case of generalized projective spaces. Consequently, the goal is to characterize and classify all matroids containing more hyperplanes than points. In 1996, I obtained the classification of all finite matroids containing one more hyperplane than points. In this paper a complete classification of finite matroids with two more hyperplanes than points is obtained. Moreover, a partial contribution to the classification of those matroids containing a certain number of hyperplanes more than points is presented.     

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.     

Characterizing 3‐connected planar graphs and graphic matroids

A well‐known result of Tutte states that a 3‐connected graph G is planar if and only if every edge of G is contained in exactly two induced non‐separating circuits. Bixby and Cunningham generalized Tutte's result to binary matroids. We generalize both of these results and give new characterizations of both 3‐connected planar graphs and 3‐connected graphic matroids. Our main result determines when a natural necessary condition for a binary matroid to be graphic is also sufficient. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 165–174, 2010     

Minimal non-orientable matroids in a projective plane

We construct a new family of minimal non-orientable matroids of rank three. Some of these matroids embed in Desarguesian projective planes. This answers a question of Ziegler: for every prime power q, find a minimal non-orientable submatroid of the projective plane over the q-element field.