Search

Suppose B 1 and B 2 are two bases in a matroid M. For subsets X ⊆ B 1 and Y ⊆ B 2 , we say that X is serially exchangeable with Y if there exist orderings x 1 ≺ x 2 ≺ ⋯ ≺ x k and y 1 ≺ y 2 ≺ ⋯ ≺ y k of X and Y, respectively, such that for i = 1 , … , k , B 1 − x 1 − ⋯ − x i + y 1 + ⋯ + y i and B 2 − y 1 − ⋯ − y i + x 1 + ⋯ + x i are bases. Kotlar and Ziv [9] conjectured that for any X ⊆ B 1 , there exists Y ⊆ B 2 for which X is serially exchangeable with Y. Let M q be the set of matroids representable over G F ( q ) . In this paper, we show that to prove the above conjecture for matroids in M q , it suffices to prove it for such matroids of rank at most ( k + 2 ) q 2 k . In second part of the paper, we show that if M is binary, and | X | ≤ 3 , then there exists Y ⊆ B 2 for which X is serially exchangeable with Y.

Graph minors play an important role in graph theory. The focus of this paper is on immersion minors and their relationship to planarity. In general, planar graphs can have non-planar immersion minors. This paper shows that by placing a simple restriction on the immersion-minor operations, all immersion minors of a planar graph are planar. This then allows one to easily obtain a characterization of planar graphs using immersion minors. A dual form of this characterization, as well as an extension to binary matroids, are also considered.

The edge covering number of a hypergraph A is s ( A ) = min { | B | : B ? A , ? B = ? A } . The paper studies a conjecture on the edge covering number of the intersection of two matroids. For two natural numbers k , ? , let f ( k , ? ) be the maximal value of s ( M ? N ) over all pairs of matroids M , N such that s ( M ) = k and s ( N ) = ? . In (Aharoni and Berger, 2006) 1] the first two authors proved that f ( k , ? ) ? 2 max ( k , ? ) and conjectured that f ( k , k ) = k + 1 and f ( k , ? ) = ? when ? k . In this paper we prove that f ( k , k ) ? k + 1 , f ( 2 , 2 ) = 3 and f ( 2 , 3 ) ? 4 . We also form a conjecture on the edge covering number of 2-polymatroids that is a common extension of the above conjecture and the Goldberg-Seymour conjecture, and prove its first non-trivial case.

An edge e in a 3-connected graph G is contractible if the contraction G / e is still 3-connected. The problem of bounding the number of contractible edges in a 3-connected graph has been studied by numerous authors. In this paper, the corresponding problem for matroids is considered and new graph results are obtained. An element e in a 3-connected matroid M is contractible or vertically contractible if its contraction M / e is, respectively, 3-connected or vertically 3-connected. Cunningham and Seymour independently proved that every 3-connected matroid has a vertically contractible element. In this paper, we study the contractible and vertically contractible elements in 3-connected matroids and get best-possible lower bounds for the number of vertically contractible elements in 3-connected and minimally 3-connected matroids. We also prove generalizations of Tutte's Wheels and Whirls Theorem for matroids and Tutte's Wheels Theorem for graphs.

Assume that the vertices of a graph G are always operational, but the edges of G fail independently with probability q ∈ [ 0 , 1 ] . The all-terminal reliability of G is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in q , and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We show that such is the case for matroids of rank 3 and paving matroids of rank 4. We also prove that the reliability roots of shellable complexes are dense in the complex plane, and that the real reliability roots of any matroid lie in [ − 1 , 0 ) ∪ { 1 } . Finally, we also show that the reliability roots of thickenings of the Fano matroid can lie outside the unit disk.

In this paper, we investigate the classes of matroid intersection admitting a solution for the problem of partitioning the ground set E into k common independent sets, where E can be partitioned into k independent sets in each of the two matroids. For this problem, we present a new approach building upon the generalized-polymatroid intersection theorem. We exhibit that this approach offers alternative proofs and unified understanding of previous results showing that the problem has a solution for the intersection of two laminar matroids and that of two matroids without ( k + 1 ) -spanned elements. Moreover, we newly show that the intersection of a laminar matroid and a matroid without ( k + 1 ) -spanned elements admits a solution. We also construct an example of a transversal matroid which is incompatible with the generalized-polymatroid approach.

The beta invariant is related to the Chromatic and Tutte Polynomials and has been studied by Crapo [4] , Brylawski [2] , Oxley [7] and others. Crapo [4] showed that a matroid with at least two elements is connected if and only if its beta invariant is greater than zero. Brylawski [2] showed that a connected matroid has beta invariant one if and only if M is isomorphic to a serial-parallel network. Oxley [7] characterized all matroids with beta invariant two, three and four. In this paper, we first give a best possible lower bound on the beta invariant of 3-connected matroids, then we characterize all 3-connected matroids attaining the lower bound. We also characterize all binary matroids with beta invariant 5, 6, and 7.

Let M be a matroid and e ∈ E ( M ) . The e -exchange basis graph of M has vertices labeled by bases of M , and two vertices are adjacent when the bases labeling them have symmetric difference { e , x } for some x ∈ E ( M ) . In this paper we show that a connected matroid is exactly a matroid with the property that for every element e ∈ E ( M ) , the e -exchange basis graph is connected.

A matroid M has all-graphic cocircuits if M ∖ Y is a graphic matroid for every cocircuit Y ∈ C ∗ ( M ) . In Papalamprou and Pitsoulis (2013) it has been shown that signed-graphic matroids that are representable in G F ( 2 ) can be decomposed into graphic matroids and matroids with all-graphic cocircuits. In this paper we study this class of signed-graphic matroids with all-graphic cocircuits and provide the set of regular excluded minors as well as a complete characterization when the matroid is cographic, which in turn results in a simple recognition algorithm.

In this paper, we obtain a sharp lower bound for the number of elements covered by triads in a minimally 3-connected binary matroid.

The problem of decomposing an independence system into the set-theoretic union of matroids is considered in the first part of this paper and a Boolean procedure is proposed for finding the prime matroidal components of such a decomposition. The second part of the paper deals with the special case of the independence system of all stable sets of a graph, characterizes the graphs whose family of stable sets is the set-theoretic union of two matroids, produces a class of perfect graphs of matroidal number k and gives for graphs an accelerated version of the general decomposition technique.

A maximum stable set in a graph G is a stable set of maximum cardinality. S is a local maximum stable set of G, and we write [email protected][email protected](G), if S is a maximum stable set of the subgraph induced by [email protected]?N(S), where N(S) is the neighborhood of S. A greedoid (V,F) is called a local maximum stable set greedoid if there exists a graph G=(V,E) such that [email protected](G). Nemhauser and Trotter Jr. (1975) [29], proved that any [email protected][email protected](G) is a subset of a maximum stable set of G. In Levit and Mandrescu (2002) [19] we have shown that the family @J(T) of a forest T forms a greedoid on its vertex set. The cases where G is bipartite, triangle-free, well-covered, unicycle, while @J(G) is a greedoid, were analyzed in Levit and Mandrescu (2004, 2007, 2008, 2001, 2009) [20-22,18,25], respectively. In this paper, we demonstrate that if the family @J(G) satisfies the accessibility property, then, first, @J(G) is a greedoid, and, second, this greedoid, which we called the local maximum stable set greedoid defined by G, is an interval greedoid. We also characterize those graphs whose families of local maximum stable sets are either antimatroids or matroids. For these cases, some polynomial recognition algorithms are suggested.

This paper is the first of three parts of a comprehensive survey of a newly emerging field: a topological approach to the study of locally finite graphs that crucially incorporates their ends. Topological arcs and circles, which may pass through ends, assume the role played in finite graphs by paths and cycles. The first two parts of the survey together provide a suitable entry point to this field for new readers; they are available in combined form from the ArXiv [18]. They are complemented by a third part [28], which looks at the theory from an algebraic-topological point of view.The topological approach indicated above has made it possible to extend to locally finite graphs many classical theorems of finite graph theory that do not extend verbatim. While the second part of this survey [19] will concentrate on those applications, this first part explores the new theory as such: it introduces the basic concepts and facts, describes some of the proof techniques that have emerged over the past 10 years (as well as some of the pitfalls these proofs have in stall for the naive explorer), and establishes connections to neighbouring fields such as algebraic topology and infinite matroids. Numerous open problems are suggested.

Whittle [12] conjectured that if M is a 3-connected quaternary matroid with a clonal pair {e,f}, then M@?e,f and M/e,f are both binary. In this paper we show that for q@?{4,5,7,8,9} if M is a 3-connected GF(q)-representable matroid with a clonal set X of size q-2, then M@?X and M/X are binary.

A matroid M is called minor-minimally 3-connected if M is 3-connected and, for each [email protected]?E(M), either [email protected]?e or M/e is not 3-connected. In this paper, we prove a chain theorem for the class of minor-minimally 3-connected binary matroids. As a consequence, we obtain a chain theorem for the class of minor-minimally 3-connected graphs.

For a k-connected graph or matroid M, where k is a fixed positive integer, we say that a subset X of E(M) is k-removable provided M∖X is k-connected. In this paper, we obtain a sharp condition on the size of a 3-connected binary matroid to have a 3-removable circuit.

Rayleigh monotonicity in Physics has a combinatorial interpretation. In this paper we give a combinatorial proof of the Rayleigh formula using the Jacobi Identity and the all-minors matrix tree Theorem. Motivated by the fact that the edge set of each spanning tree of G is a basis of the graphic matroid induced by G, we define the Rayleigh monotonicity of the generating polynomial for the set of bases of a matroid and suggest a few related problems.

All orientations of binary and ternary matroids are representable [R.G. Bland, M. Las Vergnas, Orientability of matroids, J. Combinatorial Theory Ser. B 24 (1) (1978) 94–123; J. Lee, M. Scobee, A characterization of the orientations of ternary matroids, J. Combin. Theory Ser. B 77 (2) (1999) 263–291]. In this paper we show that this is not the case for matroids that are representable over GF(pk) where k⩾2. Specifically, we show that there are orientations of the rank-k free spike that are not representable for all k⩾4. The proof uses threshold functions to obtain an upper bound on the number of representable orientations of the free spikes.

In this paper, we consider the coboundary polynomial for a matroid as a generalization of the weight enumerator of a linear code. By describing properties of this polynomial and of a more general polynomial, we investigate the matroid analogue of the MacWilliams identity. From coding-theoretical approaches, upper bounds are given on the size of circuits and cocircuits of a matroid, which generalizes bounds on minimum Hamming weights of linear codes due to I. Duursma.

The purpose of this paper is to provide links between matroid theory and the theory of subcode weights and supports in linear codes. We describe such weights and supports in terms of certain matroids arising from the vector matroids associated to the linear codes. Our results generalize classical results by Whitney, Tutte, Crapo and Rota, Greene, and other authors. As an application of our results, we obtain a new and elegant dual correspondence between the bond union and cycle union cardinalities of a graph.

Let T be a family of graphs. A T-packing of a graph G is a subgraph of G, components of which are isomorphic to members of T. We are concerned with families T, such that in every graph G, the subsets of vertices that can be saturated by some T-packing form a collection of independent sets of a matroid. The main purpose of this paper is to introduce a new class of families with this property.

An element e of a 3-connected matroid M is said to be superfluous provided M/e is 3-connected. In this paper, we show that a 3-connected matroid M with exactly k superfluous elements has at leastmax5|E(M)|+30-15k9,5r^*(M)+30-10k7elements covered by triangles. For each k, an infinite family of matroids that attain this bound is constructed.

The present publication is mainly a survey paper on the author's contributions on the relations between graph theory and linear algebra. A system of axioms introduced by Ghouila-Houri allows one to generalize to an arbitrary Abelian group the notion of interval in a linearly ordered group and to state a theorem that generalizes two due to A.J. Hoffman. The first is on the feasibility of a system of inequalities and the other is Hoffman's circulation theorem reported in the first Berge's book on graph theory. Our point of view permitted us to prove classical results of linear programming in the more general setting of linearly ordered groups and rings. It also shed a new light on convex programming.

For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $k\in\{1, 2, ..., n - 1\}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very special and important in matroid theory. In 2003 Wu found the exact numbers of $n$-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number $p$, a $GF(p$) representable $n$-spike $M$ is only representable on fields with characteristic $p$ provided that $n \ge 2p-1$. Moreover, $M$ is uniquely representable over $GF(p)$., 8 pages

In [On Mills's conjecture on matroids with many common bases, Discrete Math. 240 (2001) 271-276], Lemos proved a conjecture of Mills [On matroids with many common bases, Discrete Math. 203 (1999) 195-205]: for two (k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n"1 circuit-hyperplanes and from the other by relaxing n"2 circuit-hyperplanes, where n"1 and n"2 are non-negative integers such that n"1+n"[email protected]?k. In [Matroids with many common bases, Discrete Math. 270 (2003) 193-205], Lemos proved a similar result, where the hypothesis of the matroids being k-connected is replaced by the weaker hypothesis of being vertically k-connected. In this paper, we extend these results.

One of the most interesting results about finite matroids of finite rank and generalized projective spaces is the result of Basterfield, Kelly and Green (1968/1970) (J.G. Basterfield, L.M. Kelly, A characterization of sets of n points which determine n hyperplanes, in: Proceedings of the Cambridge Philosophical Society, vol. 64, 1968, pp. 585–588; C. Greene, A rank inequality for finite geometric lattices, J. Combin Theory 9 (1970) 357–364) affirming that any matroid contains at least as many hyperplanes as points, with equality in the case of generalized projective spaces. Consequently, the goal is to characterize and classify all matroids containing more hyperplanes than points. In 1996, I obtained the classification of all finite matroids containing one more hyperplane than points. In this paper a complete classification of finite matroids with two more hyperplanes than points is obtained. Moreover, a partial contribution to the classification of those matroids containing a certain number of hyperplanes more than points is presented.

Bondy proved that an n-vertex simple Hamiltonian graph with at least n^2/4 edges has cycles of every length unless it is isomorphic to K"n"/"2","n"/"2. This paper considers finding circuits of every size in GF(q)-representable matroids with large numbers of elements. A consequence of the main result is that a rank-r simple binary matroid with at least 2^r^-^1 elements either has circuits of all sizes or is isomorphic to AG(r-1,2).

The Critical Theorem, due to Henry Crapo and Gian-Carlo Rota, has previously been extended or generalised in a number of different ways. The main result of the present paper is a general form of the Critical Theorem that encompasses many of these results. Applications include generalisations of a theorem by Curtis Greene that describes how the weight enumerator of a linear code is determined by the Tutte polynomial of the associated vector matroid, as well as generalisations of the MacWilliams identity for linear codes.

Transition polynomials for 4-regular graphs were defined by Jaeger [On transition polynomials of 4-regular graphs, in: Hahn et al. (Eds.), Cycles and Rays, Kluwer Academic Publishers, Dordrecht, 1990, pp. 123-150.]. Many polynomials with a wide range of applications in mathematics and physics are transition polynomials. Such is the case for Penrose, Martin and Kauffman bracket polynomials. The Tutte polynomial of a plane graph is also a transition polynomial (in the case x=y). The authors in [J.A. Ellis-Monaghan, I. Sarmiento, Medical graphs and the Penrose polynomial, Congr. Numer. 150 (2001) 211-222.] generalized Jaeger's transition polynomials to a class of graphs including planar drawings of non-planar graphs. A further generalization was obtained in [J.A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 150 (2003) 211-222.] where the authors defined transition polynomials for all Eulerian graphs. In [J.A. Ellis-Monaghan, I. Sarmiento, Medical graphs and the Penrose polynomial, Congr. Numer. 150 (2001) 211-222.] and [J.A. Ellis-Monaghan, I. Sarmiento, Generalized transition polynomials, Congr. Numer. 150 (2003) 211-222.] transition polynomials were seen as homomorphisms of Hopf algebras. Following a different approach, Aigner and Mielke [The Penrose polynomial of binary matroids, Monatsh. Math. 131 (2000) 1-13.] defined a transition polynomial for isotropic systems associated to binary matroids. In this paper we will present an overview of the very rich world of transition polynomials.

In this paper, we prove a conjecture proposed by Leo: a large minimally 3-connected matroid M has at least (5|E(M)|+30)/9 of its elements belonging to some triad. A bound on the number of elements belonging to triads of a 3-connected matroid which is close to be minimally 3-connected is also given. Both of these bounds are sharp and infinite families of matroids attaining them are constructed. A new proof of results of Lemos and Leo about triads meeting circuits with at most one removable element in 3-connected matroids is given.

For an integer n>=3, a rank-n matroid is called an n-spike if it consists of n three-point lines through a common point such that, for all k in {1,2,...,n-1}, the union of every set of k of these lines has rank k+1. It is well known that there is a unique binary n-spike for each integer n>=3. In this paper, we first prove that, for each integer n>=3, there are exactly two distinct ternary n-spikes, and there are exactly @?(n^2+6n+24)/[email protected]? quaternary n-spikes. Then we prove that, for each integer n>=4, there are exactly [email protected]?n/[email protected]? quinternary n-spikes and, for each integer n>=18, the number of n-spikes representable over GF(7) is @?(2n^2+6n+6)/[email protected]?. Finally, for each q>7, we find the asymptotic value of the number of distinct rank-n spikes that are representable over GF(q).

An element e of a 3-connected matroid M is essential if neither the deletion nor the contraction of e from M is 3-connected. Tutte's 1966 Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. It was proved by Oxley and Wu that if a 3-connected matroid M has a non-essential element, then it has at least two such elements. Moreover, the set of essential elements of M can be partitioned into classes where two elements are in the same class if M has a fan, a maximal partial wheel, containing both. In addition, if M has a fan with 2k or 2k+1 elements for some k⩾2, then M can be obtained by sticking together a (k+1)-spoked wheel and a certain 3-connected minor of M. In this paper, it is shown how a slight modification of these ideas can be used to describe the structure of a 3-connected matroid M having a 3-separation (A,B) such that every element of A is essential. The motivation for this study derives from a desire to determine when one can remove an element from M so as to both maintain 3-connectedness and preserve one side of the 3-separation.

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.

This paper is devoted to a simple alternative proof for a theorem of Frank and Tardos (Math. Programming 42 (1988) 489) on adjacency of extreme points in the common base polytope of a pair of matroids. The new proof relies merely on the simultaneous base exchange axiom, independent of the linear inequality description of the polytope due to Edmonds (Guy et al. (Eds.), Combinatorial Structures and Their Applications, Gordon and Breach, London, 1970, p. 69).

In this paper, we shall prove a conjecture of Mills: for two ( k +1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n 1 circuit-hyperplanes and from the other by relaxing n 2 circuit-hyperplanes, where n 1 and n 2 are non-negative integers such that n 1 + n 2 ⩽ k

Matching 2-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, etc. In this paper we develop a polynomial-time extreme point algorithm for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

In this paper, we shall present an algorithm to decide when a connected matroid M is reconstructible from its connectivity function. When M is not reconstructible, this algorithm gives all the matroids with the same connectivity function as M .

This paper proves several extremal results for 3 -connected matroids. In particular, it is shown that, for such a matroid M , (i) if the rank r(M) of M is at least six, then the circumference c(M) of M is at least six and, provided |E(M)|⩾4r(M)−5 , there is a circuit whose deletion from M leaves a 3-connected matroid; (ii) if r(M)⩾4 and M has a basis B such that M⧹e is not 3-connected for all e in E(M)−B , then |E(M)|⩽3r(M)−4 ; and (iii) if M is minimally 3 -connected but not hamiltonian, then |E(M)|⩽3r(M)−c(M) .

This paper relates the recent theory of discrete Morse functions due to Forman (Adv. in Math. 134 (1998) 90–145) and combinatorial decompositions such as shellability, which are known to have many useful applications within combinatorics. First, we present the basic aspects of discrete Morse theory for regular cell complexes in terms of the combinatorial structure of their face posets. We introduce the notion of a generalized shelling of a regular cell complex and describe how to construct a discrete Morse function associated with such a decomposition. An application of Forman's theory gives us generalizations of known results about the homotopy properties of shellable complexes. We also discuss an application to a set of complexes related to matroids.

Let B (M) denote the collection of bases of a matroid M. Truemper showed that if M1 and M2 are connected matroids having the same ground set and the symmetric difference B (M 1 ) Δ B (M 2 ) has cardinality one, then one of M1 and M2 is obtained from the other by relaxing a circuit-hyperplane. This paper shows that, apart from a trivial exception, a pair of connected matroids M1 and M2 having the same ground set and the property that | B (M 1 ) Δ B (M 2 )|=2 must also be related via the relaxation operation.

This paper generalizes a result of Mader for graphs by proving that if f is an element of a circuit C of a 3-connected matroid M and M ⧹ e is not 3-connected for each e ϵ C − { f }, then C meets a triad of M . Several consequences of this result are proved. One of these generalizes a graph result of Wu. The others provide 3-connected analogues of 2-connected matroid results of Oxley.

A matroid ℳ of rank r ⩾ k is k -paving if all of its circuits have cardinality exceeding r − k . In this paper, we develop some basic results concerning k -paving matroids and their connections with codes. Also, we determine all binary 2-paving matroids.

In this paper we are interested in the following question: what is the smallest number of circuits, s(n,r) , that is sufficient to determine every uniform oriented matroid of rank r on n elements? We shall give different upper bounds for s(n,r) by using special coverings called connected coverings .

D.W. Hall proved that every simple 3-connected graph with a K 5 -minor must have a K 3.3 -minor, the only exception being K 5 itself. In this paper, we prove that every 3-connected binary matroid with an M ( K 5 )-minor must have an M ( K 3.3 )- or M *( K 3.3 )-minor, the only exceptions being M ( K 5 ), a highly symmetric 12-element matroid which we call T 12 , and any single-element contraction of T 12 .

Brylawski first raised the questions of whether a matroid can be reconstructed from its multisets of hyperplanes, single-element deletions, or minors. This paper explores the relationships between these questions, and resolves them for certain classes of matroids. In particular, finite Dowling lattices are shown to be reconstructible both by deletions and by contractions.

In this paper we determine completely the class of binary matroids with no minors isomorphic to the cycle matroid of the prism graph M * ( K 5 e ), its dual M ( K 5 e ), and the binary affine cube AG (3,2).

A set of axioms of defining a matroid in terms of its bases is given by the Steinitz exchange lemma. In this paper, we show these axioms are not independent, and find a subcollection defining the same structure.A special motivation is given by the Graβmann variety and by oriented matroids, where we present improved versions of known results.

The main result of this paper can be quickly described as follows. Let G be a bipartite graph and assume that for any vertex v of G a strongly base orderable matroid is given on the set of edges adjacent with v . Call a subgraph of G a system of representatives of G if the edge neighborhood of each vertex of this subgraph is independent in the corresponding matroid. Two systems of representatives we call compatible if they have no common edge. We give a necessary and sufficient condition for G to have k pairwise compatible systems of representatives with at least d edges. Unfortunately, this condition is not sufficient if we deal with arbitrary matroids. Furthermore, we establish a listing variant of the Edmonds' covering theorem for strongly base orderable matroids.

We prove that matroid complexes of rank 3 are extendably shellable. Let (,“) be the family of k-element subsets of a finite set E. There is a conjecture of Simon [lo] that (f) is extendably shellable for every k. In this paper we will prove that matroid complexes of rank 3 are extendably shellable. Simon’s conjecture for k = 3 then follows as a special case, since (t) is the uniform matroid of rank 3. For BE(~) we will write B for the simplicial complex generated by B (i.e. such that B is the set of maximal faces of B). Our convention is that 0 E B. We will write B, /*B, if B1 GB, s(f) and B, shells to B,, i.e. a sequence of shelling steps extends B1 to BZ. By a shelling step is meant adding to BG(~) a set A@)--B such that A--B= {C: DGCGA} f or some D G A. A family B z(f) (or the simplicial complex B) is called shellable if 0 /* B, and extendably shellable if also 0 P C implies C /* B for all C E B. By a matroid complex we mean the family of all independent sets of a matroid. See [3] for more about combinatorial topology (e.g. shellability and r-connectivity) and [ 1 l] for matroid theory. We will show that connectivity (i.e. that edge-paths connect every pair of vertices) is a sufficient condition for a 2-dimensional complex to be extendable by shelling steps to an enveloping matroid complex. In fact (see Corollary 4), this condition is also necessary. Proposition 1. Let B, E B, s(t). Suppose that B, is connected and B, is a matroid. Then Bl/* &. *Corresponding author. 0012-365X/94/$07.00