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.     

The lattice of flats and its underlying flag matroid polytope

LetM be a matroid andF the collection of all linear orderings of bases ofM, orflags ofM. We define the flag matroid polytope Δ(F). We determine when two vertices of Δ(F) are adjacent, and provide a bijection between maximal chains in the lattice of flats ofM and certain maximal faces of Δ(F). Supported in part by NSA grant MDA904-95-1-1056.     

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.     

The Euler circuit theorem for binary matroids

It is proved that, if M is a binary matroid, then every cocircuit of M has even cardinality if and only if M can be obtained by contracting some other binary matroid M⁺ onto a single circuit. This is the natural analog of the Euler circuit theorem for graphs. It is also proved that every coloop-free matroid can be obtained by contracting some other matroid (not in general binary) onto a single circuit.     

Vaught’s conjecture for some meager groups

AssumeG is a superstable group ofM-rank 1 and the division ring of pseudo-endomorphisms ofG is a prime field. We prove a relative Vaught’s conjecture for Th(G). When additionallyU(G) =ω, this yields Vaught’s conjecture for Th(G). Research supported by KBN grant 2 P03A 006 09.     

An Erd?s-Gallai Theorem for Matroids

Erdős and Gallai showed that for any simple graph with n vertices and circumference c it holds that | E(G) | ￡ \frac12(n - 1)c{{{\mid}{E(G)}{\mid} \leq {\frac{1}{2}}(n - 1)c}}. We extend this theorem to simple binary matroids having no F ₇-minor by showing that for such a matroid M with circumference c(M) ≥  3 it holds that | E(M) | ￡ \frac12r(M)c(M){{{\mid}{E(M)}{\mid} \leq {\frac{1}{2}}r(M)c(M)}}.     

Primitive permutation groups of simple diagonal type

LetG be a finite primitive group such that there is only one minimal normal subgroupM inG, thisM is nonabelian and nonsimple, and a maximal normal subgroup ofM is regular. Further, letH be a point stabilizer inG. ThenH∩M is a (nonabelian simple) common complement inM to all the maximal normal subgroups ofM, and there is a natural identification ofM with a direct powerT ^m of a nonabelian simple groupT in whichH∩M becomes the “diagonal” subgroup ofT ^m: this is the origin of the title. It is proved here that two abstractly isomorphic primitive groups of this type are permutationally isomorphic if (and obviously only if) their point stabilizers are abstractly isomorphic. GivenT ^m, consider first the set of all permutational isomorphism classes of those primitive groups of this type whose minimal normal subgroups are abstractly isomorphic toT ^m. Secondly, form the direct productS _m×OutT of the symmetric group of degreem and the outer automorphism group ofT (so OutT=AutT/InnT), and consider the set of the conjugacy classes of those subgroups inS _m×OutT whose projections inS _m are primitive. The second result of the paper is that there is a bijection between these two sets. The third issue discussed concerns the number of distinct permutational isomorphism classes of groups of this type, which can fall into a single abstract isomorphism class.     

Minors of a random binary matroid

Let A be an n × m matrix over GF ₂ where each column consists of k ones, and let M be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant C_M such that m ≥ C_Mn² implies that the binary matroid induced by A contains M as a minor. We prove that if the columns of A = A _n,m,k are chosen randomly, then there are constants k_M,L_M such that k ≥ k_M and m ≥ L_Mn implies that A contains M as a minor with high probability .     

Homogeneous Riemannian manifolds of positive Ricci curvature

We prove that a homogeneous effective spaceM=G/H, whereG is a connected Lie group andH⊂G is a compact subgroup, admits aG-invariant Riemannian metric of positive Ricci curvature if and only if the spaceM is compact and its fundamental group π₁(M) is finite (in this case any normal metric onG/H is suitable). This is equivalent to the following conditions: the groupG is compact and the largest semisimple subgroupLG⊂G is transitive onG/H. Furthermore, ifG is nonsemisimple, then there exists aG-invariant fibration ofM over an effective homogeneous space of a compact semisimple Lie group with the torus as the fiber. Translated fromMatematicheskie Zametki, Vol. 58, No. 3, pp. 334–340, September, 1995.     

Separating cocircuits in binary matroids

A cocircuit of a matroid is separating if deleting it leaves a separable matroid. We give an effecient algorithm which finds a separating cocircuit or a Fano minor in a binary matroid, thus proving constructively a theorem of Tutte. Using this algorithm and a new recursive characterization of bond matroids, we give a new method for testing binary matroids for graphicness. We also give an efficient algorithm for finding a special kind of separating cocircuit: one whose deletion leaves a matroid having a coloop.     

On the Cocircuit Graph of an Oriented Matroid

In this paper we consider the cocircuit graph G _M of an oriented matroid M , the 1 -skeleton of the cell complex W formed by the span of the cocircuits of M . In general, W is not determined by G _M . However, we show that if the vertex set (resp. edge set) of G _M is properly labeled by the hyperplanes (resp. colines) of M , G _M determines W . Also we prove that, when M is uniform, the cocircuit graph together with all antipodal pairs of vertices being marked determines W . These results can be considered as variations of Blind—Mani's theorem that says the 1-skeleton of a simple convex polytope determines its face lattice. Received August 14, 1998, and in revised form March 2, 1999.     

Symmetric products of surfaces and the cycle index

We study some of the combinatorial structures related to the signature ofG-symmetric products of (open) surfacesSP _G ^m (M)=M ^m/G whereG ⊂S _m.The attention is focused on the question, what information about a surfaceM can be recovered from a symmetric productSP ⁿ(M). The problem is motivated in part by the study of locally Euclidean topological commutative (m+k,m)-groups, [16]. Emphasizing a combinatorial point of view we express the signature Sign(SP _G ^m (M))in terms of the cycle index ofG, a polynomial which originally appeared in Pólya enumeration theory of graphs, trees, chemical structures etc. The computations are used to show that there exist punctured Riemann surfacesM _g,k,M _g′,k′such that the manifoldsSP ^m(M _g,k)andSP ^m(M)_g′,k′)are often not homeomorphic, although they always have the same homotopy type provided 2 _g +k=2 _g′ +k′ andk,k′≥1. Supported by the Serbian Ministry for Science and Technology, Grant No. 1643.     

On Maximum-sized k-Regular Matroids

 Let k be an integer exceeding one. The class of k-regular matroids is a generalization of the classes of regular and near-regular matroids. A simple rank-r regular matroid has the maximum number of points if and only if it is isomorphic to M(K _r+1), the cycle matroid of the complete graph on r+1 vertices. A simple rank-r near-regular matroid has the maximum number of points if and only if it is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding a point to a 3-point line of M(K _r+2) and then contracting this point. This paper determines the maximum number of points that a simple rank-r k-regular matroid can have and determines all such matroids having this number. With one exception, there is exactly one such matroid. This matroid is isomorphic to the simplification of , that is, the simplification of the matroid obtained, geometrically, by freely adding k independent points to a flat of M(K _r+k+1) isomorphic to M(K _k+2) and then contracting each of these points. Revised: July 27, 1998     

A matroid generalization of a result of Dirac

This paper generalizes a theorem of Dirac for graphs by proving that ifM is a 3-connected matroid, then, for all pairs {a,b} of distinct elements ofM and all cocircuitsC ^* ofM, there is a circuit that contains {a,b} and meetsC ^*. It is also shown that, although the converse of this result fails, the specified condition can be used to characterize 3-connected matroids.The author's research was partially supported by a grant from the National Security Agency.     

Independence and port oracles for matroids,with an application to computational learning theory

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.Research partially funded by NSF PYI Grant No. DDM-91-96083.Research partially funded by NSF Grant No CCR-92-10957.     

Equivalent factor matroids of graphs

The factor matroid of a graphG is the matric matroid of the vertex-edge incidence matrix ofG interpreted over the real numbers. This paper presents a constructive characterization of the graphs hat have the same factor matroid as a given 4-connected bipartite graph.Research partially supported by NSF Grant ESS-8307796 and Office of Naval Research Grant N00014-86-K-0689.     

Compactifying coverings of 3-manifolds

If a finitely presented groupG is negatively curved, automatic or asynchronously automatic thenG has an asynchronously bounded “almost prefix closed” combing. Results in [Br₁] and [E] imply that the fundamental group of any closed 3-manifold satisfying Thurston's geometrization conjecture has an asynchronously bounded, almost prefix closed combing. MAIN THEOREM. IfM is a compactP ²-irreducible 3-manifold,π ₁ (M) has an asynchronously bounded, almost prefix closed combing, andH, a subgroup ofπ ₁ (M), is quasiconvex with respect to this combing, then the cover ofM corresponding toH is a missing boundary manifold.     

Prime modules of a gamma ring

We define a prime ΓM-module for a Γ-ringM. It is shown that a subsetP ofM is a prime ideal ofM if and only ifP is the annihilator of some prime ΓM-moduleG. s-prime ideals ofM were defined by the first author. We defines-modules ofM, analogous to a concept defined by De Wet for rings. It is shown that a subsetQ ofM is ans-prime ideal ofM if and only ifQ is the annihilator of somes-moduleG ofM. Relationships between prime ΓM-modules and primeR-modules are established, whereR is the right operator ring ofM. Similar results are obtained fors-modules.     

The quotient field as a torsion-free covering module

R will denote a commutative integral domain with quotient fieldQ. A torsion-free cover of a moduleM is a torsion-free moduleF and anR-epimorphism σ:F→M such that given any torsion-free moduleG and λ∈Hom _R (G, M) there exists μ∈Hom _R (G,F) such that σμ=λ. It is known that ifM is a maximal ideal ofR, R→R/M is a torsion-free cover if and only ifR is a maximal valuation ring. LetE denote the injective hull ofR/M thenR→R/M extends to a homomorphismQ→E. We give necessary and sufficient conditions forQ→E to be a torsion-free cover.     

Nielsen’s theorem for model aspherical manifolds

The main issue of this paper is the discussion of Nielsen’s realisation-problem for aspherical manifolds arising from (generalised) Seifert fiber space constructions. We present sufficient conditions on such “model” aspherical manifoldsM to have that a finite abstract kernel ψ:G → Out (π₁ (M)) can be (effectively) geometrically realised by a group of fiber preserving homeomorphisms ofM if and only if ψ can be realised by an (admissible) group extension 1 → (π₁ (M)) →E’ →G → 1. Then an algebraic approach to a (partial) study of the symmetry ofM is possible. Our result covers all situations already described in literature and we show with an example that we also deal with other types of Seifert fiber space constructions which were not yet treated before. Research Assistant of the Belgian National Fund for Scientific Research (N.F.W.O.)