A unique exchange property for bases

We define the concept of unique exchange on a sequence (X₁,…, X_m) of bases of a matroid M as an exchange of x ? X_i for y ? X_j such that y is the unique element of X_j which may be exchanged for x so that (X_i ? {x}) ∪ {y} and (X_j ? {y}) ∪ {x} are both bases. Two sequences X and Y are compatible if they are on the same multiset. Let UE(1) [UE(2)] denote the class of matroids such that every pair of compatible basis sequences X and Y are related by a sequence of unique exchanges [unique exchanges and permutations in the order of the bases]. We similarly define UE(3) by allowing unique subset exchanges. Then UE(1),UE(2), and UE(3) are hereditary classes (closed under minors) and are self-dual (closed under orthogonality). UE(1) equals the class of series-parallel networks, and UE(2) and UE(3) are contained in the class of binary matroids. We conjecture that UE(2) contains the class of unimodular matroids, and prove a related partial result for graphic matroids. We also study related classes of matroids satisfying transitive exchange, in order to gain information about excluded minors of UE(2) and UE(3). A number of unsolved problems are mentioned.     

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.     

Submodular set functions,matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem

For the problem maxlcub;Z(S): S is an independent set in the matroid Xrcub;, it is well-known that the greedy algorithm finds an optimal solution when Z is an additive set function (Rado-Edmonds theorem). Fisher, Nemhauser and Wolsey have shown that, when Z is a nondecreasing submodular set function satisfying Z(?)=0, the greedy algorithm finds a solution with value at least half the optimum value. In this paper we show that it finds a solution with value at least 1/(1 + α) times the optimum value, where α is a parameter which represents the ‘total curvature’ of Z. This parameter satisfies 0≤α≤1 and α=0 if and only if the set function Z is additive. Thus the theorems of Rado-Edmonds and Fisher-Nemhauser-Wolsey are both contained in the bound 1/(1 + α). We show that this bound is best possible in terms of α. Another bound which generalizes the Rado-Edmonds theorem is given in terms of a ‘greedy curvature’ of the set function. Unlike the first bound, this bound can prove the optimality of the greedy algorithm even in instances where Z is not additive. A third bound, in terms of the rank and the girth of X, unifies and generalizes the bounds (e?1)/e known for uniform matroids and $\text{1}\text{2}$ for general matroids. We also analyze the performance of the greedy algorithm when X is an independence system instead of a matroid. Then we derive two bounds, both tight: The first one is [1?(1?α/K)^k]/α where K and k are the sizes of the largest and smallest maximal independent sets in X respectively; the second one is 1/(p+α) where p is the minimum number of matroids that must be intersected to obtain X.     

Complexity of Finding Irreducible Components of a Semialgebraic Set

Let W ⊂ Rⁿ be a semialgebraic set defined by a quantifier-free formula with k atomic polynomials of the kind f ∈ Z[X₁, . . . , X_n] such that deg_{X1, . . . , Xn}(f) < d and the absolute values of coefficients of f are less than 2^M for some positive integers d, M. An algorithm is proposed for producing the complexification, Zariski closure, and also for finding all irreducible components of W. The running time of the algorithm is bounded from above by M^O(1)(kd)^nO(1). The procedure is applied to computing a Whitney system for a semialgebraic set and the real radical of a polynomial ideal.     

Two, more readily computable equivariant Nielsen numbers I. Nielsen theory for M-ads

In this, the first of two papers outlining a Nielsen theory for “two, more readily computable equivariant numbers”, we define and study two Nielsen type numbers N(f,k;X−{Xν}_ν∈M) and N(f,k;X,{Xν}_ν∈M), where f and k are M-ad maps. While a Nielsen theory of M-ads is of interest in its own right, our main motivation lies in the fact that maps of M-ads accurately mirror one of two fundamental structures of equivariant maps. Being simpler however, M-ad Nielsen numbers are easier to study and to compute than equivariant Nielsen numbers. In the sequel, we show our M-ad numbers can be used to form both upper and lower bounds on their equivariant counterparts.The numbers N(f,k;X−{Xν}_ν∈M) and N(f,k;X,{Xν}_ν∈M), generalize the generalizations to coincidences, of Zhao's Nielsen number on the complement N(f;X−A), respectively Schirmer's relative Nielsen number N(f;X,A). Our generalizations are from the category of pairs, to the category of M-ads. The new numbers are lower bounds for the number of coincidence points of all maps f^′ and k^′ which are homotopic as maps ofM-ads to f, respectively k firstly on the complement of the union of the subspaces Xν in the domain M-ad X, and secondly on all of X. The second number is shown to be greater than or equal to a sum of the first of our numbers. Conditions are given which allow for both equality, and Möbius inversion. Finally we show that the fixed point case of our second number generalizes Schirmer's triad Nielsen number N(f;X₁∪X₂).Our work is very different from what at first sight appears to be similar partial results due to P. Wong. The differences, while in some sense subtle in terms of definition, are profound in terms of commutability. In order to work in a variety of both fixed point and coincidence points contexts, we introduce in this first paper and extend in the second, the concept of an essentiality on a topological category. This allows us to give computational theorems within this diversity. Finally we include an introduction to both papers here.     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

Connected hyperplanes in binary matroids

For a 3-connected binary matroid M, let dim_A(M) be the dimension of the subspace of the cocycle space spanned by the non-separating cocircuits of M avoiding A, where A⊆E(M). When A=∅, Bixby and Cunningham, in 1979, showed that dim_A(M)=r(M). In 2004, when |A|=1, Lemos proved that dim_A(M)=r(M)-1. In this paper, we characterize the 3-connected binary matroids having a pair of elements that meets every non-separating cocircuit. Using this result, we show that 2dim_A(M)?r(M)-3, when M is regular and |A|=2. For |A|=3, we exhibit a family of cographic matroids with a 3-element set intersecting every non-separating cocircuit. We also construct the matroids that attains McNulty and Wu’s bound for the number of non-separating cocircuits of a simple and cosimple connected binary matroid.     

Productivity of Zariski-compactness for constructs of affine spaces

We study compactness for hereditary coreflective subconstructs X of SSET, the construct of affine spaces over the two point set S and with affine maps as morphisms, endowed with the Zariski closure operator z. We formulate necessary conditions for productivity of z-compactness. Moreover, if in X arbitrary products of quotients are quotients, then our conditions are also sufficient. We apply the results to some well-known subconstructs of SSET, in particular we investigate situations in which another sufficient condition for productivity of compactness, known as finite structure property for products (FSPP), is not fulfilled by the Zariski closure.     

Non-regular simplicial matroids

Let (ks) denote the set of all k-element-subsets of a finite set S. A k-simplical matroid on a subset E of (ks) is a binary matroid the circuit of which are simplicial complexes {X1,…Xm} ? E with boundary 0 (mod 2). The k-simplical matroid on (ks) is called the full simplicial matroid Gk(S). The polygon matroid on the edges of a finite graph is 2-simplicial. Polygon-matroids and their duals are regular. The dual of Gk(S) is Gn?k(S) if the cardinnlity of S is n. More details on simplicial matroids can be found in [3, Chapter 6] and also in [4, pp. 180–181].Welsh asked if every simplicial matroid is regular. We prove that this is not the case, for all full k-simplicial matroids Gk(S) with 3?k?n?3 are non-regular (n is the cardinality of S). This result has also been proved σy R. Cordovil and M. Las Vergnas recently. Their proof is different from our proof, which is somewhat shorter.     

Vector representable matroids of given rank with given automorphism group

A simple way of associating a matroid of prescribed rank with a graph is shown. The matroids so constructed are representable over any sufficiency large field. Their use is demonstrated by the following result: Given an integer k?3 and a function G associating a group with each subset of a set S, there is a matroid M(E), representable over any sufficiently large field, such that E ? S, and for any T ?/ S, the rank of M/Tis k, and the automorphine group of MT is isomorphic to G(T).     

The mixing advantage for bounded random variables

Corresponding to n independent non-negative random variables X₁,…,X_n concentrated on a bounded interval set are values M₁,…,M_n, where each M_i is the expected value of the maximum of n independent copies of X_i. We obtain a sharp upper bound for the expected value of the maximum of X₁,…,X_n in terms of M₁,…,M_n. This inequality is sharp. A similar result is demonstrated for minima.     

Multivariate model with a Kronecker product covariance structure: S. N. Roy method of estimation

In this paper we consider a (p × q)-matrix X = (X ₁, ..., X _q ), where a pq-vector vec (X) = (X ₁ ^T , ...,X _q ^T ) ^T is assumed to be distributed normally with mean vector vec (M) = (M ₁ ^T , ...,M _q ^T ) ^T and a positive definite covariance matrix Λ. Suppose that Λ follows a Kronecker product covariance structure, that is Λ = Φ?Σ, where Φ = (? _ij ) is a (q × q)-matrix and Σ = (σ _ij ) is a (p × p)-matrix and the matrices Φ, Σ are positive definite. Such a model is considered in [4], where the maximum likelihood estimates of the parameters M, Φ, Σ are obtained. Using S. N. Roy’s technique (see, e.g., [3]) of the multivariate statistical analysis, we obtain consistent and unbiased estimates of M, Φ, Σ as in [4], but with less calculations.     

Patroids

A matroid M over a set E of elements is semiseparated by a partition {S¹, S²} of E iff rank E = rank S¹ + rank S² + 1. Such a semiseparation defines in each Sⁱ a pair of matroids or patroid Pⁱ = (Mⁱ, mⁱ); the two patroids P¹, P² weld to form M. The operations of removing and contracting a non-degenerate element of a matroid produce a patroid. The properties of patroids, their bases, and circuits are discussed.     

Additive operators preserving rank-additivity on symmetry matrix spaces

We characterize the additive operators preserving rank-additivity on symmetry matrix spaces. LetS _n(F) be the space of alln×n symmetry matrices over a fieldF with 2,3 ∈F ^*, thenT is an additive injective operator preserving rank-additivity onS _n(F) if and only if there exists an invertible matrixU∈M _n(F) and an injective field homomorphism ? ofF to itself such thatT(X)=cUX ^?U^T, ?X=(x_ij)∈S_n(F) wherec∈F ^*,X ^?=(?(x _ij)). As applications, we determine the additive operators preserving minus-order onS _n(F) over the fieldF.     

Best Interpolatory Approximation in Normed Linear Spaces

A theory of best approximation with interpolatory contraints from a finite-dimensional subspaceMof a normed linear spaceXis developed. In particular, to eachxX, best approximations are sought from a subsetM(x) ofMwhichdependson the elementxbeing approximated. It is shown that this “parametric approximation” problem can be essentially reduced to the “usual” one involving a certainfixedsubspaceM₀ofM. More detailed results can be obtained when (1) Xis a Hilbert space, or (2) Mis an “interpolating subspace” ofX(in the sense of [1]).     

A unified approach to theories of shadowing

This paper introduces the notion of a general approximation property, which encompasses many existing types of shadowing. It is proven that there exists a metric space X such that the sets of maps with many types of general approximation properties (including the classic shadowing, the L _p -shadowing, limit shadowing, and the s-limit shadowing) are not dense in C(X), S(X), and H(X) (the space of continuous self-maps of X, continuous surjections of X onto itself, and self-homeomorphisms of X) and that there exists a manifold M such that the sets of maps with general approximation properties of nonlocal type (including the average shadowing property and the asymptotic average shadowing property) are not dense in C(M), S(M), and H(M). Furthermore, it is proven that the sets of maps with a wide range of general approximation properties (including the classic shadowing, the L _p -shadowing, and the s-limit shadowing) are dense in the space of continuous self-maps of the Cantor set. A condition is given that guarantees transfer of general approximation property from a map on X to the map induced by it on the hyperspace of X. It is also proven that the transfer in the opposite direction always takes place.     

Packing and covering with matroid circuits

We prove a conjecture of Welsh, that for every matroid M without coloops, ν(M) + θ(M) ≤ ?(M) + κ(M) where ν(M) is the maximum number of pairwise disjoint circuits, θ(M) is the minimum number of circuits whose union is E(M), ?(M) is the corank of M, and κ(M) is the number of connected components of M. For binary matroids the result was previously proved by Oxley.     

On certain non-Kahlerian strongly pseudoconvex manifolds

It has been conjectured that strongly pseudoconvex manifoldsX such that its exceptional setS is an irreducible curve can be embedded biholomorphically into some ? ^N ×P _m . In this paper we show that this is true, with one exception, namely when dim_? X = 3 and its first Chern classc ₁ (K _X ¦S) = 0 whereS ?P ₁ andK _X is the canonical bundle ofX. On the other hand, we explicitly exhibit such a 3-foldX that is not Kahlerian; also we construct non-Kahlerian strongly pseudoconvex 3-foldX whose exceptional setS is a ruled surface; those concrete examples naturally raise the possibility of classifying non-Kahlerian strongly pseudoconvex 3-folds.     

Holomorphic vector bundles on open subsets of Stein manifolds

LetM be a connected two-dimensional Stein manifold withH ²(M,Z)=0 andS∈M a discrete subset withS≠ Ø. SetX:=M/S. Fix an integerr≥2. Then there exists a rankr vector bundleE onX such that there is no line bundleL onX with a non-zero mapL →E.