Topological representations of matroids

There is a one-to-one correspondence between geometric lattices and the intersection lattices of arrangements of homotopy spheres. When the arrangements are essential and fully partitioned, Zaslavsky's enumeration of the cells of the arrangement still holds. Bounded subcomplexes of an arrangement of homotopy spheres correspond to minimal cellular resolutions of the dual matroid Steiner ideal. As a result, the Betti numbers of the ideal are computed and seen to be equivalent to Stanley's formula in the special case of face ideals of independence complexes of matroids.

     

Axioms for infinite matroids

We give axiomatic foundations for infinite matroids with duality, in terms of independent sets, bases, circuits, closure and rank. Continuing work of Higgs and Oxley, this completes the solution to a problem of Rado of 1966.     

Rank functions of strict cg-matroids

A matroid-like structure defined on a convex geometry, called a cg-matroid, is defined by Fujishige et al. [Matroids on convex geometries (cg-matroids), Discrete Math. 307 (2007) 1936-1950]. A cg-matroid whose rank function is naturally defined is called a strict cg-matroid. In this paper, we give characterizations of strict cg-matroids by their rank functions.     

Matroid matching with Dilworth truncation

Let H=(V,E) be a hypergraph and let k?1 and l?0 be fixed integers. Let M be the matroid with ground-set E s.t. a set F⊆E is independent if and only if each X⊆V with k|X|-l?0 spans at most k|X|-l hyperedges of F. We prove that if H is dense enough, then M satisfies the double circuit property, thus Lovász’ min-max formula on the maximum matroid matching holds for M. Our result implies the Berge-Tutte formula on the maximum matching of graphs (k=1, l=0), generalizes Lovász’ graphic matroid (cycle matroid) matching formula to hypergraphs (k=l=1) and gives a min-max formula for the maximum matroid matching in the two-dimensional rigidity matroid (k=2, l=3).     

On the (co)girth of a connected matroid

This article studies the girth and cogirth problems for a connected matroid. The problem of finding the cogirth of a graphic matroid has been intensively studied, but studies on the equivalent problem for a vector matroid or a general matroid have been rarely reported. Based on the duality and connectivity of a matroid, we prove properties associated with the girth and cogirth of a matroid whose contraction or restriction is disconnected. Then, we devise algorithms that find the cogirth of a matroid M from the matroids associated with the direct sum components of the restriction of M. As a result, the problem of finding the (co)girth of a matroid can be decomposed into a set of smaller sub-problems, which helps alleviate the computation. Finally, we implement and demonstrate the application of our algorithms to vector matroids.     

On the facets of the secondary polytope

The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope.The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.     

初等模糊拟阵与基本截片模糊拟阵的若干性质

对两种初等模糊拟阵和基本截片模糊拟阵的定义进行了比较,研究了它们之间的关系.研究了初等模糊拟阵的若干性质,得到了初等模糊拟阵和基本截片模糊拟阵为闭正则模糊拟阵等结论,给出了初等模糊拟阵的等价刻画以及初等模糊拟阵与其截拟阵之间的关系.     

On Automatic Rees Matrix Semigroups

We consider a Rees matrix semigroup S = M[U; I, J; P] over a semigroup U, with I and J finite index sets, and relate the automaticity of S with the automaticity of U. We prove that if U is an automatic semigroup and S is finitely generated then S is an automatic semigroup. If S is an automatic semigroup and there is an entry p in the matrix P such that pU ¹ = U then U is automatic. We also prove that if S is a prefix-automatic semigroup, then U is a prefix-automatic semigroup.     

A generalization of Kneser's Addition Theorem

Let A=(A₁,…,Am) be a sequence of finite subsets from an additive abelian group G. Let Σ?(A) denote the set of all group elements representable as a sum of ? elements from distinct terms of A, and set . Our main theorem is the following lower bound: