The Facets of the Bases Polytope of a Matroid and Two Consequences

Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.

On Functions of K-Balanced Matroids

In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.

Extreme Matroid Graphs

Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.

关于MATROID的一个特征性质

本文给出了 Matroid 的一个特征性质,即给出了以下定理:设 S 是集合, 2,Φ∈, 为子集闭的,则（S,）为 Matroid 当且仅当下列条件满足:对X={x1,x2…xn)∈,Y={y1,y2,…ym)∈,X、Y 在 F中极大,则 n=m,且适当调整 xi的顺序,可使i,{y1…yi-1,xi,yi+1…,ym}∈（i=1,2,…n）

Min-max partitioning problem with matroid constraint

In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.

The Log-Concavity of Kazhdan-Lusztig Polynomials of Uniform Matroids

Elias,et al.(2016)conjectured that the Kazhdan-Lusztig polynomial of any matroid is logconcave.Inspired by a computer proof of Moll’s log-concavity conjecture given by Kauers and Paule,the authors use a computer algebra system to prove the conjecture for arbitrary uniform matroids.

k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints

A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint subsets.The k-submodular maximization problem has a wide range of applications.In this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

A Characterization of Sequentially Cohen-Macaulay Matroidal Ideals

Let R=K[x1,…,xn]be the polynomial ring in n variables over a field K and I be a matroidal ideal of R.We show that I is sequentially Cohen-Macaulay if and only if the Alexander dual Iy has linear quotients.As a consequence,I is sequentially Cohen-Macaulay if and only if I is shellable.

The Connectivity and Minimum Degree of Circuit Graphs of Matroids

Let G be the circuit graph of any connected matroid M with minimum degree 5（G）. It is proved that its connectivity κ（G） ≥2｜E（M） - B（M）｜ - 2. Therefore 5（G） ≥ 2｜E（M） - B（M）｜ - 2 and this bound is the best possible in some sense.

Eulerian and Bipartite Binary Delta-matroids

Delta-matroid theory is often thought of as a generalization of topological graph theory.It is well-known that an orientable embedded graph is bipartite if and only if its Petrie dual is orientable.In this paper,we first introduce the concepts of Eulerian and bipartite delta-matroids and then extend the result from embedded graphs to arbitrary binary delta-matroids.The dual of any bipartite embedded graph is Eulerian.We also extend the result from embedded graphs to the class of delta-matroids that arise as twists of binary matroids.Several related results are also obtained.

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.

NEW APPROACHES TO THE GRAPHICNESS OF A MATROID

This article provides some new characterizations for testing if a matroid isgraphic. One of them can be seen as a consequence deduced from the Wu’s theory on theplanarity of graphs.

PROOF OF A CONJECTURE ON MATROID BASE GRAPHS

Let G be the base graph of a matroid. L et k(G),λ(G) and δ(G)denote the connectivity edge-connectivity and the minimum degree of G, respectively. The conjecture that k(G)= λ(G)=δ(G) is proved true for any matroid.

Vertex Disjoint Cycles in Intersection Graphs of Bases of Matroids

The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.

New Results on Global Rank Axioms of Poset Matroids

An excellent introduction to the topic of poset matroids is due to M.Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rankaxioms for poset matroids. In this paper, we study the special integral function f and obtain a newclass of poset matroids from the old ones, and then we generalize this result according to theproperties of f. Almost all of these results can be regarded as the application of global rankaxioms for poset matroids. The main results in our paper have, indeed, investigated the restrictionof the basis of the poset matroid, and we give them the corresponding geometric interpretation.

Nowhere-zero 3-flows in matroid base graph

The base graph of a simple matroid M = （E, A） is the graph G such that V（G） = A and E（G） = {BB＇： B, B＇ B, [B ／ B＇｜ = 1}, where the same notation is used for the vertices of G and the bases of M. It is proved that the base graph G of connected simple matroid M is Z3-connected if ｜V（G）｜ ≥5. We also proved that if M is not a connected simple matroid, then the base graph G of M does not admit a nowhere-zero 3-flow if and only if IV（G）[ =4. Furthermore, if for every connected component Ei （ i≥ 2） of M, the matroid base graph Gi of Mi=MIEi has IV（Gi）｜≥5, then G is Z3-connected which also implies that G admits nowhere-zero 3-flow immediately.

Matroidal Error Correction Networks and Linear Network Error Correction MDS Codes

In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case when errors occur in multi- ple channels. Importantly, we show the necessary and sufficient conditions on the existence of linear network error correction mul- ticast/broadcast/dispersion maximum distance separable （MDS） code on a matroidal error correction network.

A GUIDED TOUR THROUGH ORIENTED MATROID AXIOMS

Oriented Matroids arise as a natural combinatorial abstraction of linear algebra and geometry.Some of the topics were foreseen by Rockafellar.Later,oriented matroids were independently discovered by Bland,Dress and Las Vergnas.As with matroids oriented matroids can be developed from many different axiom systems.In this survey we shall concentrate on some of the more important ones and show how one system can be

Properties of Hamilton cycles of circuit graphs of matroids

让 G 是连接 matroid 的一张电路图。P. 李和 G. 刘[Comput。数学。Appl， 2008， 55：654659 ] 证明 G 让哈密尔顿包括 e 和如果 G 有至少四个顶点，为 G 的任何边 e 排除 e 的另一个哈密尔顿周期骑车。这份报纸证明 G 有一个哈密尔顿周期包括 e 并且如果 G 有至少五个顶点，为任何二边 e 和 G 的 e 排除 e。这结果是在某感觉可能的最好。一个开的问题这份报纸最后被建议。

APPLICATIONS OF MATROID PARTITION TO TREE DECOMPOSITION

In this paper we present a matroid approach to the tree decomposition problem, give alternative proofs of the main results in [1,2], which give the necessary and sufficient conditions for a graph C=(V,E) of order n to have a tree decomposition (T_1,T_2): (i) Ti is of order n-1 and excludes the specified vertex ui V, i=1,2; (n) TI is a spanning tree, T_2 is of order n-2 and excludes the specified vertices u_l,u_2∈V. As an application, we give a necessary and sufficient condition for a connected graph to have a tree-decomposition of {n-1,n-1}.