Search

In this paper, a configuration with n = ( 2 d ) points in the plane is described. This configuration, as a matroid, is a Desargues configuration if d = 5, and the union of ( 5 d ) such configurations if d > 5. As an oriented matroid, it is a rank 3 truncation of the directed complete graph on d vertices. From this fact, it follows from a version of the Lefschetz-Zariski theorem implied by results of Salvetti that the fundamental group π of the complexification of its line arrangement is Artin's pure (or coloured) braid group on d strands. In this paper we obtain, by using techniques introduced by Salvetti, a new algorithm for finding a presentation of π based on this particular configuration.

This paper surveys recent work in matroid representation theory and discusses a number of open problems.

Let M be a matroid on a finite set E ( M ). Then M is packable by bases if E ( M ) is the disjoint union of bases. A partial packing of M is a collection of disjoint bases whose union is a proper subset of E ( M ). M is a randomly packable by bases if every partial packing can be extended to a packing of M . This paper determines the structure of the matroids that are randomly packable by bases. It also gives a characterization, in terms of forbidden restrictions, of the simple matroids that are randomly packable by 3-circuits.

In this paper, we define for a hypergraph H=(X >,E) a class of partial graphs of its line graph GR (H); these graphs are called intergraphs and verify the following property: for each intergraph G=(E, U) we have: ∀Ei, EjϵE∣Ei⌢Ej≠∅ there exists in G a chain (Ei=E1,E2,…,Eq=Ej such that ∀k, 1≤kq̌,Ei⌢Ej⊆E k⌢Ek+1. We show that all the intergraphs minimal w.r.t. inclusion have the same number of edges. Moreover, we show that they are the bases of a matroid. These properties allow us to define a cyclomatic number for a hypergraph, and we show some connections with a previous work on hypergraph cyclicity [Acharya and Las Vergnas (1982)].In the last section we give an application of these results to constraint networks.

Tomescu, I., Ordered h-hypertrees, Discrete Mathematics 105 (1992) 241-248. In this paper a special class of h-uniform hypergraphs, called p-ordered h-hypertrees relatively to a total order p on the vertex set is introduced. Seven other equivalent definitions of such hypertrees are proposed involving the notions of p-ordered path and p-ordered cycle. It is also proved that for a fixed order p the sets of edges of p-ordered h-hypertrees with the same vertex set is the set of bases of a graphic matroid and every h-hypertree can be recognized in polynomial time.

A property of unimodularity is introduced for antisymmetric integral matrices. It is satisfied by the adjacency matrix of a circle graph provided with a Naji orientation [8]. In a further paper we shall interprete this result in terms of symmetric matroids introduced in [2]. In this communication we give a direct proof by means of techniques used in [1] for an algorithmic solution of the Gauss problem on self-intersecting surves in the plane.

This paper considers representations of ternary matroids over fields other than GF(3). It is shown that a 3-connected ternary matroid representable over a finite field F has at most ¦F¦ - 2 inequivalent representations over F. This resolves a special case of a conjecture of Kahn in the affirmative.

Dirac and Halin have shown for n = 2 and n = 3 respectively that a minimally n-connected graph G has at least ((n–1)|V(G)|–2n)/(2n–1) vertices of degree n. This paper determines the graphs which are extremal with respect to these two results and, in addition, establishes a similar extremal result for minimally connected matroids.

A result of Walton and the author establishes that every 3-connected matroid of rank and corank at least three has one of five 6-element rank-3 self-dual matroids as a minor. One of these matroids is the rank-3 whirl W 3 . Another is the rank-3 matroid P 6 that consists of a single 3-point line together with three points off the line. This paper determines the structure of the class of matroids that is obtained by excluding as minors both W 3 and P 6 . As a consequence of this result, we deduce a characterization of the class of GF(4)-representable matroids with no W 3 -minor.

In 1978, Murty and Simon asked the following question: when can the rank function of a polymatroid be decomposed as the sum of rank functions of matroids? Another natural question to ask is the following: when is this decomposition unique? In this paper, we shall address the second question.

Antimatroids are combinatorial structures abstracting some properties of convexity, and in a sense dual to matroids. Greedoids are common generalizations of matroids and antimatroids. We introduce a general operation to produce a greedoid from a matroid and an antimatroid on the same ground set. Greedoids arising by this operation are called trimmed matroids. Many known classes of greedoids are shown to be trimmed matroids. We derive two submodularity properties of trimmed matroids and a subclass of them called polymatroid greedoids. These are used to verify the properties of a rather elaborate counterexample, which shows that certain local properties do not characterize trimmed matroids and polymatroids greedoids (as was conjectured in an earlier paper).

This paper introduces an operation of H -lifts on restrictions of Dowling group geometries and shows how it can be used to construct a new class of tangential ( k + n )-blocks from some known tangential k -blocks.

A matroid-like structure defined on a convex geometry, called a cg-matroid, is defined by Fujishige et al. [Matroids on convex geometries (cg-matroids), Discrete Math. 307 (2007) 1936–1950]. A cg-matroid whose rank function is naturally defined is called a strict cg-matroid. In this paper, we give characterizations of strict cg-matroids by their rank functions.

For any simple arrangement A of n⩾4 pseudolines in the realprojective plane, it is easy to show that the number P3 of triangles in the 2-dimensional cell complex associated with A satisfies P3⩽ 1 3 n(n−1). In this paper we construct infinite classes of simple arrangements for which P3= 1 3 n(n-1), answering negatively a conjecture of Grunbaum. An interpretation of our results in terms of oriented matroids is also given.

In 1976, R.N. Burns and C.E. Haff gave an algorithm for finding the kth-best spanning tree of an edge-weighted graph as well as the kth-best base of an element-weighted matroid. In this paper, after introducing the concept of a convex weight function defined on the vertex set of a connected graph, the following result is proved: Let H = (S, I) be an independence system, where I is the set of independent subsets of H, such that all the maximal independent subsets of H are of the same cardinality. Then a necessary and sufficient condition for H to be a matroid is that, for any weight function W defined on S, the algorithm of Burns and Haff gives a labelling of the family of maximal sets in I as B"1, B"2, ..., B"n such that W(B"1) =< W(B"2) =< ... =< W(B"n).

An element e in a 2-connected matroid M is contractible if its contraction M/e is 2-connected. The existence of contractible elements provides a very useful induction tool. In this paper, we study the distribution of contractible elements in simple 2-connected matroids.

Let M be a matroid with rank function r, and let e@?E(M). The deletion-contraction polymatroid with rank function f=r"M"@?"e+r"M"/"e will be denoted P"e(M). Notice that P"e(M) is uniquely determined by M and e. Similarly, a deletion-contraction polymatroid determines M, unless e is a loop or co-loop. This paper will characterize all polymatroids of this deletion-contraction form by giving the set of excluded minors. Vertigan conjectured that the class of GF(q)-representable deletion-contraction polymatroids is well-quasi-ordered. From this attractive conjecture, both Rota's Conjecture and the WQO Conjecture for GF(q)-representable matroids would follow.

In this paper I begin to build up a theory of Δ-matroids with coefficients parallel to the theory of matroids with coefficients. While the definition of a matroid with coefficients is based on the well-known Grassmann identity concerning determinants, a quite similar identity concerning Pfaffian forms leads to the theory of Δ-matroids with coefficients. Particular examples are Δ-matroids representable by some skew-symmetric matrix with coefficients in a field, oriented Δ-matroids, and valuated Δ-matroids.

Lemos (Discrete Math. 240 (2001) 271–276) proved a conjecture of Mills (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 n1 circuit-hyperplanes and from the other by relaxing n2 circuit-hyperplanes, where n1 and n2 are non-negative integers such that n1+n2⩽k. In this paper, we prove a similar result, where the hypothesis of the matroids being k-connected is replaced by the weaker hypothesis of being vertically k-connected.

This paper characterizes, for each i and j , the matroids that are minor-minimal among connected matroids M with b ij ( M ) > 0, where t ( M ) = Σb ij ( M ) x i y j is the Tutte polynomial of M . One consequence of this characterization for a connected matroid M is that b 11 ( M ) > 0 if and only if the two-wheel is a minor of M . Similar results are obtained for other small values of i and j . A generalization of these results leads to new combinatorial proofs which strengthen known results on the coefficients. These results imply that if M is simple and representable over GF( q ), then there are coefficients of its Tutte polynomial which count the flats of M of each rank that are projective spaces. Similarly, for a simple graphic matroid M ( G ), there are coefficients that count the number of cliques of each size contained in G .

del Greco, J.G., Characterizing bias matroids, Discrete Mathematics 103 (1992) 153–159. In this paper, a set of necessary and sufficient conditions for a matroid to be the bias matroid of a given biased graph is obtained. These conditions are reminiscent of a 1981 result of Seymour that characterized when a matroid is the polygon matroid of a graph.

The paper stems from an attempt to investigate a somewhat mysterious phenomenon: conditions which suffice for the existence of a “large” set satisfying certain conditions (e.g., a large independent set in a graph) often suffice (or at least are conjectured to suffice) for the existence of a covering of the ground set by few sets satisfying these conditions (in the example of independent sets in a graph this means that the graph has small chromatic number). We consider two conjectures of this type, on coloring by sets which are “two-way independent”, in the sense of belonging to a matroid and at the same time being independent in a graph sharing its ground set with the matroid. We prove these conjectures for matroids of rank 2. We also consider dual conjectures, on packing bases of a matroid, which are independent in a given graph.

Let G be a finite simple graph and let I ( G ) be the set of subsets X of V ( G ) such that the subgraph of G induced by X is threshold. If I ( G ) is the independence system of a matroid, then G is called matrogenic [3]. In this paper, we characterize matroids arising from matrogenic graphs.

In the first part of this paper we give a generalization of a result of Ringel [11] on simple arrangements of pseudolines. In terms of fillings with rhombi of an N-zonogon, we obtain a way of generating every filling from a given one by successively performing the same local transformation.In the second part we interpret, via oriented matroids, fillings of N-zonogons with rhombi as families of vectors in ZN.While for results in Section 1 the finiteness of the filling is essential, the aim of Section 2 is to strengthen the possibility already pointed out by Dress [7] of obtaining de Bruijn's results [4] on Penrose tilings from a purely combinatorial point of view.

Let N be a minor of a 3-connected matroid M and let M′ be a 3-connected minor of M that is minimal having N as a minor. This paper commences the study of the problem of finding a best-possible upper bound on |E(M′)−E(N)| . The main result solves this problem in the case that N and M have the same rank.

A matroid may be characterized by the collection of its bases or by the collection of its circuits. Along with any matroid is a uniquely determined dual matroid. Given the bases of a matroid, it is possible to show that base complements are precisely the bases of the dual. So it is easy to construct bases of the dual given the bases of the original matroid.This paper provides two results. The first enables construction of all circuits of the dual matroid from circuits of the original matroid. The second constructs all bases of a matroid from its circuits.

In this paper we investigate the Ehrhart Theory of the independence matroid polytope of uniform matroids. It is proved that these polytopes have an Ehrhart polynomial with positive coefficients. To do that, we prove that indeed all half-open-hypersimplices are Ehrhart positive, and tile disjointly our polytope using them., Comment: 7 pages