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

Homotopy Sphere Representations for Matroids

For any rank r oriented matroid M, a construction is given of a ??topological representation?? of M by an arrangement of homotopy spheres in a simplicial complex which is homotopy equivalent to S ^r?C1 . The construction is completely explicit and depends only on a choice of maximal flag in M. If M is orientable, then all Folkman-Lawrence representations of all orientations of M embed in this representation in a homotopically nice way.     

Stieltjes- and Geronimus-type polynomials

This work is an extension to the formal case of a previous work by Monegato [5].A Stieltjes-type polynomial is a polynomial of degree (n + 1), E_n+1, orthogonal with respect to the functional \s{;c̃_i = c(P_n(x)xⁱ), i = 0, 1, 2,…\s}, where c is a functional defined by the series f(t) = ∑^∞_i=0c_itⁱ. E_n+1 is of important use in the estimation of the error in Padé approximation. An iteration of the construction of E_n+1 is attempted. (Sections 1, 2, 3, 4).In the last section, we study the properties of the polynomial S_n associated with E_n+1 with respect to another functional c̄. S_n is called a Geronimus-type polynomial. It is shown that S_n verifies the system c(P_nS_nG_k) = 0 for k = 1,…,n, where the G_k's are orthogonal with respect to c̄.     

On matroids of the greatestW-connectivity

The Whitney connectivity (W-connectivity) of a matroidM is defined by T. Inukai and L. Weinberg as the least integerk for which there exists a subsetS of the ground setE ofM such that ?(S) ≥ k, ?(E ? S) ≥ k, andp(S)+p(E-S)-pM+1=k where ? is the rank function ofM.Mis called a Whitney matroid if there exists no such integer. In this case, theW-connectivity ofM to be the rank ofM is defined. In this paper, several properties of Whitney matroids are demonstrated. In addition, the Whitney matroids whose duals are also Whitney matroids are characterized, and an interpretation of binaryW-matroids is given.     

Extremal critically connected matroids

A connected matroid M is called a critically connected matroid if the deletion of any one element from M results in a disconnected matroid. We show that a critically connected matroid of rank n, n≥3, can have at most 2n?2 elements. We also show that a critically connected matroid of rank n on 2n?2 elements is isomorphic to the forest matroid of K₂, n?2.     

A Splitter Theorem Relative to a Fixed Basis

A standard matrix representation of a matroid M represents M relative to a fixed basis B, where contracting elements of B and deleting elements of E(M)–B correspond to removing rows and columns of the matrix, while retaining standard form. If M is 3-connected and N is a 3-connected minor of M, it is often desirable to perform such a removal while maintaining both 3-connectivity and the presence of an N-minor. We prove that, subject to a mild essential restriction, when M has no 4-element fans with a specific labelling relative to B, there are at least two distinct elements, s ₁ and s ₂, such that for each i ∈ {1, 2}, si(M/s _i ) is 3-connected and has an N-minor when s _i ∈ B, and co(M\s _i ) is 3-connected and has an N-minor when s _i ∈ E(M)–B. We also show that if M has precisely two such elements and P is the set of elements that, when removed in the appropriate way, retain the N-minor, then (P, E(M)–P) is a sequential 3-separation.     

Matroid optimization with the interleaving of two ordered sets

We study the structure of the minimum weight base of a matroid M = (E, I) the order of whose element set E is determined by the interleaving of two ordered subsets of E, R and W. The results imply an interesting application in economics, and are useful for the rapid recomputation of the minimum weight base when the order of E is successively modified by changing the interleaving of R and W. As a special case of the main result, the following parametric problem is efficiently solved: For M = (E, I) a matroid with weighted element set E, and R a subset of E, find for all feasible values of q, the minimum weight base of M containing exactly q elements of R. This parametric problem is a weighted matroid intersection problem and hence can be solved by known matroid intersection algorithms. The approach in this paper is different, and vastly improves the efficiency of the solution, as well as determining structural information about the bases.     

Local diameters of compact planar sets

Given a compact setS?E² andP ₁ εS, we consider sequencesP _i , 1<i<∞, such that $$h_i : = \left\| {P_i - P_{i + 1} } \right\| = \mathop {\max }\limits_{R \in S} \left\| {P_i - R} \right\|$$ . Callh=limh _i a local diameter ofS. It is realized by a line segmentPQS. In relation toD(S), the ordinary diameter ofS, we determine (with and without certain angular constraints) how smallh can be. For example, ifA, B ε S and the line segmentAB is a diameter ofS, we determine best possible lower bounds for ∥P?Q∥/∥A?B∥ in terms of the smallest angle formed by the lines extendingPQ andAB. Local diameters arise from the problem of computing generalized transfinite diameters. Moreover, information about local diameters provides both upper and lower bounds on the isoperimetric quotient ofS.     

Classification of polynomial translation hypersurfaces of finite type

In this paper we prove that any hypersurface in Eⁿ⁺¹ of the form where P ₁ is a polynomial of degree ≥2 and P ₂, ... , P _n are functions such that P _i ^′ P _i ^″ = 0 somewhere for all i = 2, ... , n, is of infinite type. As a consequence, we deduce that a polynomial translation hypersurface in Eⁿ⁺¹, i. e. a hypersurface of the above form where P ₁, ... , P _n are polynomials, is of finite type if and only if it is a hyperplane. This provides some partial solutions to a problem of B. Y. Chen [C3].     

Une relation de séparation entre cocircuits d'un matroide

Let S₁′S₂′S₃′ be 3 distinct cocircuits of a matroid M on a set E. We say that S₁′ does not separate S₂′ and S₃′ when S₂′\S₁′ and S₃′\S₁′ are included in one single and the same component of the submatroid M × (E\S₁′). Our main result is: A matroid is graphic if and only if from any 3 cocircuits having a non-empty intersection there is at least one which separates the two others.     

The structure of 0-bisimple strongly E *-unitary inverse monoids

We introduce a class of strongly E ^*-unitary inverse semigroups S _i (G, P) (i = 1,2) determined by a group G and a submonoid P of G and give an embedding theorem for S _i (G, P). Moreover we characterize 0-bisimple strongly E ^*-unitary inverse monoids and 0-bisimple strongly F ^*-inverse monoids by using S _i (G, P).     

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

Connected matroids with a small circumference

Lemos and Oxley proved that if M is a connected matroid with |E(M)|⩾3r(M), then M has a circuit C such that M⧹C is connected. In this paper, we shall improve this result proving that for a simple and connected matroid M, if r(M)⩾7 and |E(M)|⩾3r(M)−3, then M has a circuit C such that M⧹C is connected. To prove this result, we shall construct all the connected matroids having circumference at most five, with the exception of those which are 3-connected and have rank five.     

The Critical Case of the Cramer-Lundberg Theorem on the Asymptotic Tail Behavior of the Maximum of a Negative Drift Random Walk

We study the asymptotic tail behavior of the maximum M = max{0,S _n ,n ≥ = 1} of partial sums S _n = ξ₁ + ? + ξ _n of independent identically distributed random variables ξ₁,ξ₂,... with negative mean. We consider the so-called Cramer case when there exists a β > 0 such that E e ^βξ1 = 1. The celebrated Cramer-Lundberg approximation states the exponential decay of the large deviation probabilities of M provided that Eξ₁ e ^βξ1 is finite. In the present article we basically study the critical case Eξ₁ e ^βξ1 = ∞.     

Translating IΔ0 + exp Proofs into Weaker Systems

The purpose of this paper is to explore the relationship between IΔ₀ + exp and its weaker subtheories. We give a method of translating certain classes of IΔ₀ + exp proofs into weaker systems of arithmetic such as Buss' systems S₂. We show if IE_i (exp) ⊢ A with a proof P of expind‐rank(P) ≤ n + 1where all (∀ ≤: right) or (∃ ≤: left) have bounding terms not containing function symbols, then Sⁱ ₂ ⊇ IE_i,2 ⊢ Aⁿ. Here A is not necessarily a bounded formula. For IOpen(exp) we prove a similar result. Using our translations we show IOpen(exp) ⊊ IΔ₀(exp). Here IΔ₀(exp) is a conservative extension of IΔ₀ + exp obtained by adding to IΔ₀ a symbol for 2 ^x to the language as well as defining axioms for it.     

Strong Splitter Theorem

The Splitter Theorem states that, if N is a 3-connected proper minor of a 3-connected matroid M such that, if N is a wheel or whirl then M has no larger wheel or whirl, respectively, then there is a sequence M ₀, . . . , M _n of 3-connected matroids with ${M_0 \cong N}$ , M _n = M and for ${i \in \{1, \ldots , n}\}$ , M _i is a single-element extension or coextension of M _i?1. Observe that there is no condition on how many extensions may occur before a coextension must occur. We give a strengthening of the Splitter Theorem, as a result of which we can obtain, up to isomorphism, M starting with N and at each step doing a 3-connected single-element extension or coextension, such that at most two consecutive single-element extensions occur in the sequence (unless the rank of thematroids involved is r(M)). Moreover, if two consecutive single-element extensions by elements {e, f} are followed by a coextension by element g, then {e, f , g} form a triad in the resulting matroid.     

On the adjunction process over a surface in char.p

Let K_s be the canonical bundle on a non singular projective surface S (over an algebraically closed field F, char F=p) and L be a very ample line bundle on S. Suppose (S,L) is not one of the following pairs: (P²,O(e)), e=1,2, a quadric, a scroll, a Del Pezzo surface, a conic bundle. Then

1. (K_s?L)² is spanned at each point by global sections. Let \(\phi :S \to P^N _F \) be the map given by the sections Γ(K_s?L)², and let φ=s o r its Stein factorization.
2. r:S→S′=r(S) is the contraction of a finite number of lines, E_i for i=1,...r, such that E_i·E_i=K_S·E_i=?L·E_i=?1.
3. If h°(L)≥6 and L·L≥9, then s is an embedding.

     

Asymptotic joint distribution of the largest roots of several multivariate F matrices I. Quasi-independent case

An asymptotic expansion of the joint distribution of k largest characteristic roots C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is given, where S'_is and S₀ are independent Wishart matrices with common covariance matrix Σ. The modified second-approximation procedure to the upper percentage points of the maximum of C_M⁽ⁱ⁾(S_iS₀^?1), i = 1,…, k, is also considered. The evaluation of the expansion is based on the idea for studentization due to Welch and James with the use of differential operators and of the perturbation procedure.     

Testing membership in matroid polyhedra

Given a matroid M on E and a nonnegative real vector x=(x_j:j∈E), a fundamental problem is to determine whether x is in the convex hull P of (incidence vectors of) independent sets of M. An algorithm is described for solving this problem for which the amount of computation is bounded by a polynomial in |E|, independently of x, allowing as steps tests of independence in M and additions, subtractions, and comparisons of numbers. In case x ∈ P, the algorithm finds an explicit representation for x which has additional nice properties; in case x ? P it finds a most-violated inequality of the system defining P. The same technique is applied to the problem of finding a maximum component-sum vector in the intersection of two matroid polyhedra and a box.