Matroids with given restrictions and contractions

If M is a matroid on a set S and if X is a subset of S, then there are two matroids on X induced by M: namely, the restriction and the contraction of M onto X. Necessary and sufficient conditions are obtained for two matroids on the same set to be of this form and an analogous result is obtained when (X₁,…, X_t) is a partition of S. The corresponding results when all the matroids are binary are also obtained.     

Semi-crossed products of C1-algebras

Given a C¹-algebra $\text{U}$ and endomorphim α, there is an associated nonselfadjoint operator algebra $\text{Z}$⁺ X_α$\text{U}$, called the semi-crossed product of $\text{U}$ with α. If α is an automorphim, $\text{Z}$⁺ X_α$\text{U}$ can be identified with a subalgebra of the C¹-crossed product $\text{Z}$⁺ X_α$\text{U}$. If $\text{U}$ is commutative and α is an automorphim satisfying certain conditions, $\text{Z}$⁺ X_α$\text{U}$ is an operator algebra of the type studied by Arveson and Josephson. Suppose S is a locally compact Hausdorff space, φ: S → S is a continuous and proper map, and α is the endomorphim of U=C₀(S) given by α(?) = ? ō φ. Necessary and sufficient conditions on the map φ are given to insure that the semi-crossed product Z⁺X_αC₀(S) is (i) semiprime; (ii) semisimple; (ii) strongly semisimple.     

The Greedy Algorithm and Coxeter Matroids

The notion of matroid has been generalized to Coxeter matroid by Gelfand and Serganova. To each pair (W, P) consisting of a finite irreducible Coxeter group W and parabolic subgroup P is associated a collection of objects called Coxeter matroids. The (ordinary) matroids are a special case, the case W = A (isomorphic to the symmetric group Sym_{_n+1}) and P a maximal parabolic subgroup. The main result of this paper is that for Coxeter matroids, just as for ordinary matroids, the greedy algorithm provides a solution to a naturally associated combinatorial optimization problem. Indeed, in many important cases, Coxeter matroids are characterized by this property. This result generalizes the classical Rado-Edmonds and Gale theorems.A corollary of our theorem is that, for Coxeter matroids L, the greedy algorithm solves the L-assignment problem. Let W be a finite group acting as linear transformations on a Euclidean space , and let

Progressive scattered data filtering

Given a finite point set $\text{Z⊂}\text{R}{}^{\mathrm{d}}$, the covering radius of a nonempty subset X⊂Z is the minimum distance r_X,Z such that every point in Z is at a distance of at most r_X,Z from some point in X. This paper concerns the construction of a sequence of subsets of decreasing sizes, such that their covering radii are small. To this end, a method for progressive data reduction, referred to as scattered data filtering, is proposed. The resulting scheme is a composition of greedy thinning, a recursive point removal strategy, and exchange, a postprocessing local optimization procedure. The paper proves adaptive a priori lower bounds on the minimal covering radii, which allows us to control for any current subset the deviation of its covering radius from the optimal value at run time. Important computational aspects of greedy thinning and exchange are discussed. The good performance of the proposed filtering scheme is finally shown by numerical examples.     

Greedy algorithm and symmetric matroids

Symmetric matroids are set systems which are obtained, in some sense, by a weakening of the structure of a matroid. These set systems are characterized by a greedy algorithm and they are suitable for dealing with autodual properties of matroids. Applications are given to the eulerian tours of 4-regular graphs and the theory ofg-matroids.     

Sur la compatibilité des extensions ponctuelles d'un matroïde

A natural sufficient condition for a finite family of single element extensions of a matroid to be compatible is given. Characterizations of all the finite extensions N of a matroid M(E) are given for which the rank function satisfies

$\text{ρ}{}_{\mathrm{N}}\text{(X)=}\text{Min}\text{Z?E}\text{{ρ}{}_{\mathrm{M}}\text{(Z)+|X?}\text{Z}{}^{\mathrm{N}}\text{|}}$

or equivalently the closure operator satisfies $\text{X}{}^{\mathrm{N}}\text{=}\text{X}{}^{\mathrm{N}}\text{? E}{}^{\mathrm{N}}\text{? X}$. The single element extensions and the principal extensions are examples of such matroids. The notion of a sheaf of flats of M. Las Vergnas is used in the proof of a new necessary and sufficient condition for two single element extensions of a matroid to be compatible. An initial announcement of part of these results appeared in R. Cordovil (C. R. Acad. Sci. Paris. A284 (1977), 1249–1252).     

On projections and limit mappings of inverse systems of compact spaces

A compactificaton αX of a completely regular space X is “determined” by a subset F of C¹(X) if αX is the smallest compactificaton of X to which each element of F extends, and is “generated” by F if the evaluation map $\text{e}{}_{\mathrm{F}}\text{:X →}\text{R}{}^{\mathrm{n}}\text{,n = |F|}$, is an embedding and $\text{αX =}\text{e}{}_{\mathrm{F}}\text{(X)}$. Evidently, if F either determines or generates αX, then every elements of F has an extension to αX; whenever F satisfies this latter condition, the set of all such extensions is denoted F^α.A major results of our previous paper is that F determines αX if and only if F^α separates points of αX ? X. A major result of the present paper is that F generates αX if and only if F^α separates points of αX.     

A matroid-friendly basis for the quasisymmetric functions

A new Z-basis for the space of quasisymmetric functions (QSym, for short) is presented. It is shown to have nonnegative structure constants, and several interesting properties relative to the quasisymmetric functions associated to matroids by the Hopf algebra morphism F of Billera, Jia, and Reiner [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646]. In particular, for loopless matroids, this basis reflects the grading by matroid rank, as well as by the size of the ground set. It is shown that the morphism F distinguishes isomorphism classes of rank two matroids, and that decomposability of the quasisymmetric function of a rank two matroid mirrors the decomposability of its base polytope. An affirmative answer to the Hilbert basis question raised in [L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, arXiv:math.CO/0606646] is given.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Infinite subgraphs as matroid circuits

A matroidal family $\text{C}$ is defined to be a collection of graphs such that, for any given graph G, the subgraphs of G isomorphic to a graph in $\text{C}$ satisfy the matroid circuit-axioms. Here matroidal families closed under homeomorphism are considered. A theorem of Simöes-Pereira shows that when only finite connected graphs are allowed as members of $\text{C}$, two matroids arise: the cycle matroid and bicircular matroid. Here this theorem is generalized in two directions: the graphs are allowed to be infinite, and they are allowed to be disconnected. In the first case four structures result and in the second case two infinite families of matroids are obtained. The main theorem concerns the structures resulting when both restrictions are relaxed simultaneously.     

A characterization of orthogonal duality in matroid theory

An operation on matroids is a function defined from the collection of all matroids on finite sets to itself which preserves isomorphism of matroids and sends a matroid on a set S to a matroid on the same set S. We show that orthogonal duality is the only non-trivial operation on matroids which interchanges contraction and deletion.     

Greedy Families for Linear Objective Functions

The following structures are characterized: for which families of feasible subsets of a finite set does the greedy algorithm return the optimum subset independent of the weighting of a linear objective function on the set? Characteristically, the family must then have as bases the bases of a matroid (even when the feasible family is not a system of independent sets), and for every accessible feasible set X, the subset of elements by which X can be augmented is the complement of a proper closed set of the matroid. Another characterization is given for a family in which the greedy algorithm gives the optimum subset at every stage: the family is that of the bases of a sequence of matroid strong maps resulting in a natural duality theory. Theoretical underpinnings are given for several classical instances such as the algorithms of Kruskal, Prim, and Dijkstra.     

Optimal cocircuits in regular matroids and applications

Let M = (E, C) be a regular matroid with circuit set H and cocircuit set H and let $\text{(}\text{H}\text{, +, ?)}$ be an ordered group. To given partitions D = D⁺ ∈ D^? for all D ?H and weighting functions ?,k: E → H optimale ê-cocircuits are defined by having a minimal value $\text{K}\text{(}\text{D}{}^{\mathrm{+}}\text{) ? ol(}\text{D}{}^{\mathrm{?}}\text{ø 1^e1}$.It is shown that P as well as NP problems can be formulated by means of optimal cocircuits. We discuss a class of optimal cocircuit problems which can be solved using flow theory in regular matroids. Applications of the derived theory and algorithms to graphic and cographic matroids and to special ordered groups yield polynomial algorithms for some new minimal cut and shortest path problems which are useful in combinatorial and integer optimization problems.     

Efficient algorithms for a family of matroid intersection problems

Consider a matroid where each element has a real-valued cost and a color, red or green; a base is sought that contains q red elements and has smallest possible cost. An algorithm for the problem on general matroids is presented, along with a number of variations. Its efficiency is demonstrated by implementations on specific matroids. In all cases but one, the running time matches the best-known algorithm for the problem without the red element constraint: On graphic matroids, a smallest spanning tree with q red edges can be found in time O(n log n) more than what is needed to find a minimum spanning tree. A special case is finding a smallest spanning tree with a degree constraint; here the time is only O(m + n) more than that needed to find one minimum spanning tree. On transversal and matching matroids, the time is the same as the best-known algorithms for a minimum cost base. This also holds for transversal matroids for convex graphs, which model a scheduling problem on unit-length jobs with release times and deadlines. On partition matroids, a linear-time algorithm is presented. Finally an algorithm related to our general approach finds a smallest spanning tree on a directed graph, where the given root has a degree constraint. Again the time matches the best-known algorithm for the problem without the red element (i.e., degree) constraint.     

The max-flow min-cut property of two-dimensional affine convex geometries

In a matroid, (X,e) is a rooted circuit if X is a set not containing element e and X∪{e} is a circuit. We call X a broken circuit of e. A broken circuit clutter is the collection of broken circuits of a fixed element. Seymour [The matroids with the max-flow min-cut property, J. Combinatorial Theory B 23 (1977) 189-222] proved that a broken circuit clutter of a binary matroid has the max-flow min-cut property if and only if it does not contain a minor isomorphic to Q₆. We shall present an analogue of this result in affine convex geometries. Precisely, we shall show that a broken circuit clutter of an element e in a convex geometry arising from two-dimensional point configuration has the max-flow min-cut property if and only if the configuration has no subset forming a ‘Pentagon’ configuration with center e.Firstly we introduce the notion of closed set systems. This leads to a common generalization of rooted circuits both of matroids and convex geometries (antimatroids). We further study some properties of affine convex geometries and their broken circuit clutters.     

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved by Aharoni and Berger in 2009.We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids.In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.     

On a generalization of linear independence in finite-dimensional vector spaces

A set X in a vector space V is said to be k-independent (where k is a positive integer) if, for each x?X,X{x} admits a partition into k subsets {χ_gq}_θ=1,…,k such that x ? span χ_θ, θ = 1,…,k. It is proved that if dim V = n and X ? V is k-independent, then X cannot contain more than $\text{(}\text{n+k?1}\text{k}\text{)}$ elements; this bound is sharp for vector spaces over sufficiently large fields. A broader notion (k-independence in degrees) is considered, and similar results are obtained. Several unresolved problems are stated, some involving matroid generalizations of questions answered as yet only within vector space context.     

Distribution results for the occupation measures of continuous Gaussian fields

For a d-dimensional random field X(t) define the occupation measure corresponding to the level α by the Lebesgue measure of that portion of the unit cube over which X(t)?α. Denoting this by M[X, α], it is shown that for sample continuous Gaussian fields

$\text{P}\text{{M[X,α]>β}=}\text{exp}\text{{?}\text{1}\text{2}\text{α}{}^2\text{k}{}_{\mathrm{\beta }}\text{(1+0(1))}}$

as α→∞, for a particular functional kβ. This result is applied to a variety of fields related to the planar Brownian motion, and for each such field we obtain bounds for kβ.     

Über asymmetrische diophantische approximationen

For irrational numbers θ define α(θ) = lim sup{1/(q(p ? qθ))|p ∈ $\text{Z}$, q ∈ $\text{N}$, p ? qθ > 0} and α(θ) = 0 for rationals. Put $\text{α}\text{(θ) = max{α(θ), α(?0)}}$. Then $\text{U}$ = α($\text{R}$β$\text{Q}$) is an asymmetric analogue to the Lagrange spectrum $\text{U}\text{=}\text{α}\text{(RβQ)}$. Our results concerning $\text{U}$ partly contrast the known properties of $\text{U}$. In fact, $\text{U}$ is a perfect set, each element of which is a condensation point of the spectrum and has continuously many preimages. $\text{U}$ is the closure of its rational elements and of its elements of the form p√m (p ∈ $\text{Q}$), as well. The arbitrarily well approximable numbers form a G_δ-set of 2. category. One has, roughly speaking, $\text{α}\text{→ ∞}$ for α → 1. Finally, the well-known Markov sequence which constitutes the lower Lagrange and Markov spectrum is proved to be a (small) subset of $\text{U}$?[√5,3).