Search

It is shown that a transversal matroid of rank r on a set of cardinality m is representable over any field of order greater than m + ( inr −1 m ).

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.

Assume that we are given a set of applicants and a set of posts such that each applicant has a preference list over the posts. A matching $M$ between the applicants and the posts is said to be popular if there is no other matching $N$ such that the number of applicants that prefer $N$ to $M$ is larger than the number of applicants that prefer $M$ to $N$. Then, the goal of the popular matching problem is to decide whether there is a popular matching, and find a popular matching if one exists. Abraham, Irving, Kavitha, and Mehlhorn proved that this problem can be solved in polynomial time even if the preference lists contain ties. In this paper, we consider the popular matching problem with matroid constraints. In this problem, for each post, we are given a matroid on the set of applicants. A set of applicants assigned to each post must be an independent set of its matroid. Kamiyama proved that if there is not a tie in the preference lists, then this problem can be solved in polynomial time. In this paper, ...

Consider the following problem: given a set system (U,I) and an edge-weighted graph G = (U, E) on the same universe U, find the set A in I such that the Steiner tree cost with terminals A is as large as possible: "which set in I is the most difficult to connect up?" This is an example of a max-min problem: find the set A in I such that the value of some minimization (covering) problem is as large as possible. In this paper, we show that for certain covering problems which admit good deterministic online algorithms, we can give good algorithms for max-min optimization when the set system I is given by a p-system or q-knapsacks or both. This result is similar to results for constrained maximization of submodular functions. Although many natural covering problems are not even approximately submodular, we show that one can use properties of the online algorithm as a surrogate for submodularity. Moreover, we give stronger connections between max-min optimization and two-stage robust optimization, and hence give improved algorithms for robust versions of various covering problems, for cases where the uncertainty sets are given by p-systems and q-knapsacks., 17 pages. Preliminary version combining this paper and http://arxiv.org/abs/0912.1045 appeared in ICALP 2010

The popular matching problem introduced by Abraham, Irving, Kavitha, and Mehlhorn is a matching problem in which there exist applicants and posts, and applicants have preference lists over posts. A matching M is said to be popular, if there exists no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. The goal of this problem is to decide whether there exists a popular matching, and find a popular matching if one exists. In this paper, we first consider a matroid generalization of the popular matching problem with strict preference lists, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of a matroid generalization of the popular matching problem with strict preference lists by deleting a minimum number of applicants so that it has a popular matching. This problem is a matroid generalization of the popular condensation problem with strict preference lists introduced by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

In the classic $k$-center problem, we are given a metric graph, and the objective is to open $k$ nodes as centers such that the maximum distance from any vertex to its closest center is minimized. In this paper, we consider two important generalizations of $k$-center, the matroid center problem and the knapsack center problem. Both problems are motivated by recent content distribution network applications. Our contributions can be summarized as follows: 1. We consider the matroid center problem in which the centers are required to form an independent set of a given matroid. We show this problem is NP-hard even on a line. We present a 3-approximation algorithm for the problem on general metrics. We also consider the outlier version of the problem where a given number of vertices can be excluded as the outliers from the solution. We present a 7-approximation for the outlier version. 2. We consider the (multi-)knapsack center problem in which the centers are required to satisfy one (or more) knapsack constraint(s). It is known that the knapsack center problem with a single knapsack constraint admits a 3-approximation. However, when there are at least two knapsack constraints, we show this problem is not approximable at all. To complement the hardness result, we present a polynomial time algorithm that gives a 3-approximate solution such that one knapsack constraint is satisfied and the others may be violated by at most a factor of $1+\epsilon$. We also obtain a 3-approximation for the outlier version that may violate the knapsack constraint by $1+\epsilon$., Comment: A preliminary version of this paper is accepted to IPCO 2013

It is known that any 3-connected matroid that is large enough is certain to contain a minor of a given size belonging to one of a few special classes of matroids. This paper proves a similar unavoidable minor result for large 4-connected bicircular matroids. The main result follows from establishing the list of unavoidable minors of large 4-biconnected graphs, which are the graphs representing the 4-connected bicircular matroids. This paper also gives similar results for internally 4-connected and vertically 4-connected bicircular matroids.

In this paper, the structural controllability of the systems over $F$ ( $z$ ) is studied using a new mathematical method-matroids. First, a vector matroid is defined over $F$ ( $z$ ). Second, the full rank conditions of $[sI-A\vert B](s\in \wp )$ are derived in terms of the concept related to matroid theory, such as rank, base, and union. Then, the sufficient condition for the linear system and composite system over F(z) to be structurally controllable is obtained. Finally, this paper gives several examples to demonstrate that the married-theoretic approach is simpler than other existing approaches.

Rough sets were proposed to deal with vagueness and incompleteness of knowledge in information systems. In this field, there are many optimization issues such as attribute reduction. Matroids generalized from matrices have been widely used in many fields, particularly greedy algorithm design, which plays an important role in attribute reduction. Therefore, it is meaningful to combine matroids with rough sets to solve the optimization problems. In this paper, we construct a type of matroid of rough sets based on the concept of nullity and apply it to attribute reduction. First, we propose a nullity operator for rough sets to induce a matroid and then we present a specific type of matroid called a nullity-based matroid. Second, given the relationship between nullities and matrices, we present two types of matrices to characterize this type of matroid and its nullity operator. Third, the dual of this type of matroid is induced by the second type of matrix. Finally, we apply the obtained matroids to attribute reduction issues in information systems. In summary, this paper provides a new approach to studying rough sets.

In this paper a method for establishing the structural equivalence of sets of planar geometric features composed by points and lines is presented. It is based on oriented matroid theory, a setting in which the combinatorial structural properties of these geometric features, such as incidence, order, partitioning, separation, and convexity, can be represented and analyzed in a coordinate-free manner. Projective transformations in computer vision keep in general the convexity property which implies an invariant oriented matroid representation of the planar geometric features under this class of transformations. As long as points and lines are in general position, the oriented matroid representation is also insensitive to small changes in the geometric image features. However the oriented matroid representation depends on the labeling of its elements. Checking the structural equivalence of the above mentioned geometric features represented by means of oriented matroids implies establishing whether two oriented matroid representations are equivalent up to relabeling of their elements. This is the oriented matroid isomorphism problem which is solved in this paper by means of a canonical labeling of the elements.

Let G be a circuit graph of a connected matroid. P. Li and G. Liu [Comput. Math. Appl., 2008, 55: 654–659] proved that G has a Hamilton cycle including e and another Hamilton cycle excluding e for any edge e of G if G has at least four vertices. This paper proves that G has a Hamilton cycle including e and excluding e′ for any two edges e and e′ of G if G has at least five vertices. This result is best possible in some sense. An open problem is proposed in the end of this paper.

Properties of molecules of certain hydrocarbons give rise to difficult questions in graph theory. This paper is primarily devoted to the graph theory, but the physico-chemical motivation, which is somewhat speculative, is also presented. Molecules of unsaturated hydrocarbons exhibit alternating paths with single and double bonds. Such alternating paths have been postulated to be electrically conductive. When used to conduct, however, such a path is toggled: the single and double bonds are interchanged. This can imply that other alternating paths appear or disappear. In this way, switching behavior arises. This suggests a possibility of molecular computing. Molecules are represented by graphs where certain nodes, called ports, are chosen as connectors to the outside world. At these ports other chemical groups can be attached to observe and influence the behavior. A choice of single and double bonds in the molecule is represented by an almost-perfect matching in the graph—almost, in the sense that the ports and only the ports are allowed to have no double bond attached to them. The corresponding graph theory is a qualitative idealization of the molecules. It turns out that the switching behavior is completely determined by sets of ports, called cells. The paper is devoted to the question which cells are Kekule cells, i.e., correspond to almost-perfect matchings in graphs. We prove that every Kekule cell is what is known as a linkable Δ -matroid (it appears that this was known). An anonymous referee showed us the existence of a linkable Δ -matroid with 7 ports that is not a Kekule cell. The argument is presented. We classify the linkable cells with ≤ 5 ports and show that they all are Kekule cells. We also classify the linkable cells with 6 ports. There are 214 classes; 210 classes contain Kekule cells; only 4 classes are undecided.

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.

For a 2-connected matroid M, Cunningham and Edmonds gave a tree decomposition that displays all of its 2-separations. When M is 3-connected, two 3-separations are equivalent if one can be obtained from the other by passing through a sequence of 3-separations each of which is obtained from its predecessor by moving a single element from one side of the 3-separation to the other. Oxley, Semple, and Whittle gave a tree decomposition that displays, up to this equivalence, all non-trivial 3-separations of M. Now let M be 4-connected. In this paper, we define two 4-separations of M to be 2-equivalent if one can be obtained from the other by passing through a sequence of 4-separations each obtained from its predecessor by moving at most two elements from one side of the 4-separation to the other. The main result of the paper proves that M has a tree decomposition that displays, up to 2-equivalence, all non-trivial 4-separations of M.

The domination invariant has played an important part in reliability theory. While most of the work in this field has been restricted to various types of network system models, many of the results can be generalized to much wider families of systems associated with matroids. Previous papers have explored the relation between undirected network systems and matroids. In this paper the main focus is on directed network systems and their relation to oriented matroids. An oriented matroid is a special type of matroid where the circuits are signed sets. Using these signed sets one can e.g., obtain a set theoretic representation of the direction of the edges of a directed network system. Classical results for directed network systems include the fact that the signed domination is either +1 or −1 if the network is acyclic, and zero otherwise. It turns out that these results can be generalized to systems derived from oriented matroids. Several classes of systems for which the generalized results hold will be discussed. These include oriented versions of k-out-of-n systems and a certain class of systems associated with matrices.

A neighbor system, introduced in this paper, is a collection of integral vectors in $\mathbb{R}^{n}$ with some special structure. Such collections (slightly) generalize jump systems, which, in turn, generalize integral bisubmodular polyhedra, integral polymatroids, delta-matroids, matroids, and other structures. We show that neighbor systems provide a systematic and simple way to characterize these structures. One of our main results is a simple greedy algorithm for optimizing over (finite) neighbor systems starting from any feasible vector. The algorithm is (essentially) identical to the usual greedy algorithm on matroids and integral polymatroids when the starting vector is zero. But in all other cases, from matroids through jump systems, it appears to be a new greedy algorithm. We end the paper by introducing another structure, which is more general than neighbor systems, and indicate that essentially the same greedy algorithm also works for this structure.

Hliněný and Whittle have shown that the traditional tree-width notion of a graph can be defined without an explicit reference to vertices, and that it can be naturally extended to all matroids. Unfortunately their original paper [P. Hliněný, G. Whittle, Matroid tree-width, European J. Combin. 27 (2006) 1117–1128], as pointed out by Isolde Adler in 2007, contained some incorrect arguments. It is the purpose of this addendum to correct the affected proofs. (All the theorems and results of the original paper remain valid.)

The authors showed in an earlier paper that there is a tree that displays, up to a natural equivalence, all non-trivial 3-separations of a 3-connected matroid. The purpose of this paper is to show that if certain natural conditions are imposed on the tree, then it has a uniqueness property. In particular, suppose that, from every pair of edges that meet at a degree-2 vertex and have their other ends of degree at least three, one edge is contracted. Then the resulting tree is unique.

A 3-connected matroid M is sequential or has path width 3 if its ground set E(M) has a sequential ordering, that is, an ordering (e"1,e"2,...,e"n) such that ({e"1,e"2,...,e"k},{e"k"+"1,e"k"+"2,...,e"n}) is a 3-separation for all k in {3,4,...,n-3}. In this paper, we consider the possible sequential orderings that such a matroid can have. In particular, we prove that M essentially has two fixed ends, each of which is a maximal segment, a maximal cosegment, or a maximal fan. We also identify the possible structures in M that account for different sequential orderings of E(M). These results rely on an earlier paper of the authors that describes the structure of equivalent non-sequential 3-separations in a 3-connected matroid. Those results are extended here to describe the structure of equivalent sequential 3-separations.

An excellent introduction to the topic of poset matroids is due to M. Barnabei, G. Nicoletti and L. Pezzoli. On the basis of their work, we have obtained the global rank axioms for poset matroids. In this paper, we study the special integral function f and obtain a new class of poset matroids from the old ones, and then we generalize this result according to the properties of f. Almost all of these results can be regarded as the application of global rank axioms for poset matroids. The main results in our paper have, indeed, investigated the restriction of the basis of the poset matroid, and we give them the corresponding geometric interpretation.

In a previous paper, the author extended the Whitney rank generating function (or Tutte polynomial) from binary matroids to arbitrary functions f:2S→R, where the binary matroid special case is obtained by letting f be the indicator function of the row space of a matrix over GF(2). This paper continues that work in two directions. Firstly, a natural generalisation of the partition function of the statistical mechanical Potts model of a graph is shown to be a partial evaluation of this generalised Whitney function. Secondly, a continuum of minor operations for functions on 2S is introduced, in which deletion and contraction are distinct points, and the theory of these operations is developed. A related construction of rank-like functions is given, its properties are investigated, and a corresponding continuum of Whitney-type functions is introduced. These functions are shown to contain weight enumerators of general codes over a subset of their domains. We also discuss what these new operations mean at the level of binary matroids and graphs.

A comparison of two expressions of the Tutte polynomial of an ordered oriented matroid, one as a generating function of basis activities, the other as a generating function of reorientation activities, yields a remarkable numerical relation between the number of bases and reorientations with given activities. The object of the paper is a natural activity preserving correspondence with suitable multiplicities between bases and reorientations, constituting a bijective proof of this relation. The general construction will be published elsewhere. In the present self-contained paper, we consider into details two particular cases of special interest: uniform oriented matroids and acyclic oriented matroids of rank 3. In both cases, the construction is simpler than in the general case, but introduces some of the main ideas. The correspondence is closely related to oriented matroid programming, a combinatorial generalization of linear programming. The link is direct in the uniform case: for unitary activities, the correspondence amounts to applying a program or its opposite to all bounded regions of a simple arrangement of pseudohyperplanes. In the rank-3 case, equivalent to pseudoline arrangements, a second step toward the general construction is made: optimizing two nested faces with respect to two lexicographically ordered programs.

In this paper, we shall consider the following problem: up to duality, is a connected matroid reconstructible from its connectivity function? Cunningham conjectured that this question has an affirmative answer, but Seymour gave a counter-example for it. In the same paper, Seymour proved that a connected binary matroid is always reconstructible from its connectivity function, up to duality, in the class of binary matroids. In this paper, we prove that when M is a connected binary matroid and N another matroid with the same connectivity function as N, then M=N or M=N*.

Special issue PRIMA 2013, A (pseudo-)metric D on a finite set X is said to be a \textquotelefttree metric\textquoteright if there is a finite tree with leaf set X and non-negative edge weights so that, for all x,y ∈X, D(x,y) is the path distance in the tree between x and y. It is well known that not every metric is a tree metric. However, when some such tree exists, one can always find one whose interior edges have strictly positive edge weights and that has no vertices of degree 2, any such tree is – up to canonical isomorphism – uniquely determined by D, and one does not even need all of the distances in order to fully (re-)construct the tree\textquoterights edge weights in this case. Thus, it seems of some interest to investigate which subsets of X, 2 suffice to determine (\textquoteleftlasso\textquoteright) these edge weights. In this paper, we use the results of a previous paper to discuss the structure of a matroid that can be associated with an (unweighted) X-tree T defined by the requirement that its bases are exactly the \textquotelefttight edge-weight lassos\textquoteright for T, i.e, the minimal subsets of X, 2 that lasso the edge weights of T.

In this paper, we first consider a matroid generalization of the popular matching problem (without ties) introduced by Abraham, Irving, Kavitha, and Mehlhorn, and give a polynomial-time algorithm for this problem. In the second half of this paper, we consider the problem of transforming a given instance of the popular matching problem (without ties) by deleting a minimum number of applicants so that it has a popular matching under matroid constraints. This problem is a matroid generalization of the popular condensation problem proposed by Wu, Lin, Wang, and Chao. By using the results in the first half, we give a polynomial-time algorithm for this problem.

An essential element of a 3-connected matroid M is one for which neither the deletion nor the contraction is 3-connected. Tutte's Wheels and Whirls Theorem proves that the only 3-connected matroids in which every element is essential are the wheels and whirls. In an earlier paper, the authors showed that a 3-connected matroid with at least one non-essential element has at least two such elements. This paper completely determines all 3-connected matroids with exactly two non-essential elements. Furthermore, it is proved that every 3-connected matroid M for which no single-element contraction is 3-connected can be constructed from a similar such matroid whose rank equals the rank in M of the set of elements e for which the deletion M\e is 3-connected.

This paper introduces a generalization of the matroid operation of Δ – Y exchange. This new operation, segment–cosegment exchange, replaces a coindependent set of k collinear points in a matroid by an independent set of k points that are collinear in the dual of the resulting matroid. The main theorem of the first half of the paper is that, for every field, or indeed partial field, F , the class of matroids representable over F is closed under segment–cosegment exchanges. It follows that, for all prime powers q , the set of excluded minors for GF ( q )-representability has at least 2 q −4 members. In the second half of the paper, the operation of segment–cosegment exchange is shown to play a fundamental role in an excluded-minor result for k -regular matroids, where such matroids generalize regular matroids and Whittle's near-regular matroids.

Two elements in an oriented matroid are inseparable if they have either the same sign in every signed circuit containing them both or opposite signs in every signed circuit containing them both. Two elements of a matroid are adjacent if there is no M(K4)-minor using them both, and in which they correspond to a matching ofK4 . We prove that two elements e, f of an oriented matroid are inseparable if and only ife , f are inseparable in every M(K4) orU42 -minor containing them. This provides a link between inseparability in oriented matroids (introduced by Bland and Las Vergnas) and adjacency in binary matroids (introduced by Seymour). We define the concepts of base orderable and strongly base orderable subsets of a matroid, generalizing the definitions of base orderable and strongly base orderable matroids. Strongly base orderable subsets can be used to obtain packing and covering results, generalizing results of Davies and McDiarmid, as was shown in a previous paper. In this paper, we prove that any pairwise inseparable subset of an oriented matroid is base orderable. For binary matroids we derive the following characterization: a subset is strongly base orderable if and only if it is pairwise adjacent.

In this paper we study the inverse problem of matroid intersection: Two matroids M 1 = (E, $${\mathcal{I}}$$ 1) and M 2 = (E, $${\mathcal{I}}$$ 2), their intersection B, and a weight function w on E are given. We try to modify weight w, optimally and with bounds, such that B becomes a maximum weight intersection under the modified weight. It is shown in this paper that the problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved by strongly polynomial time algorithms. We also give a necessary and sufficient condition for the feasibility of the problem. Finally we extend the discussion to the version of the problem with Multiple Intersections.

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.

In this paper, we consider the following varian to f the matroid intersection problem. We are given two matroids M1,M2 on the same ground set E and a subset A of E. Our goal is to find a common independent set I of M1,M2 such that |I ∩A| is maximum among all common independent sets of M1,M2 and such that (secondly) |I| is maximum among all common independent sets of M1,M2 satisfying the first condition. This problem is a matroid-generalization of the simplest case of the rank-maximal matching problem introduced by Irving, Kavitha, Mehlhorn, Michail and Paluch (2006). In this paper, we extend the "combinatorial" algorithm of Irving et al. for the rank-maximal matching problem to our problem by using a Dulmage-Mendelsohn type decomposition for the matroid intersection problem.

We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast ( 1 2 ρ + 1 ) -approximation algorithm, where ρ is the Steiner ratio.

Given a matroidM with distinguished elemente, aport oracie with respect toe reports whether or not a given subset contains a circuit that containse. The first main result of this paper is an algorithm for computing ane-based ear decomposition (that is, an ear decomposition every circuit of which contains elemente) of a matroid using only a polynomial number of elementary operations and port oracle calls. In the case thatM is binary, the incidence vectors of the circuits in the ear decomposition form a matrix representation forM. Thus, this algorithm solves a problem in computational learning theory; it learns the class ofbinary matroid port (BMP) functions with membership queries in polynomial time. In this context, the algorithm generalizes results of Angluin, Hellerstein, and Karpinski [1], and Raghavan and Schach [17], who showed that certain subclasses of the BMP functions are learnable in polynomial time using membership queries. The second main result of this paper is an algorithm for testing independence of a given input set of the matroidM. This algorithm, which uses the ear decomposition algorithm as a subroutine, uses only a polynomial number of elementary operations and port oracle calls. The algorithm proves a constructive version of an early theorem of Lehman [13], which states that the port of a connected matroid uniquely determines the matroid.

Let Gn, p denote a random graph on n vertices. It is an interesting problem when small cliques arise and what distributions of the number of small cliques may occur. Matroids are natural generalization of graphs; therefore, we can try to investigate maximal flats of a small rank in random matroids. The most studied and most interesting seem to be “random projective geometries” introduced by Kelly and Oxley. Many of the theorems in our paper are based on the results published in a long paper of Barbour, Janson, Karoski, and Ruciski. However, proofs for projective geometries generally are more complicated. © 1995 Wiley Periodicals, Inc.

Rough sets are efficient for data pre-process in data mining. Lower and upper approximations are two core concepts of rough sets. This paper studies generalized rough sets based on symmetric and transitive relations from the operator-oriented view by matroidal approaches. We firstly construct a matroidal structure of generalized rough sets based on symmetric and transitive relations, and provide an approach to study the matroid induced by a symmetric and transitive relation. Secondly, this paper establishes a close relationship between matroids and generalized rough sets. Approximation quality and roughness of generalized rough sets can be computed by the circuit of matroid theory. At last, a symmetric and transitive relation can be constructed by a matroid with some special properties., 5 pages

Result diversification has many important applications in databases, operations research, information retrieval, and finance. In this paper, we study and extend a particular version of result diversification, known as max-sum diversification. More specifically, we consider the setting where we are given a set of elements in a metric space and a set valuation function f defined on every subset. For any given subset S, the overall objective is a linear combination of f(S) and the sum of the distances induced by S. The goal is to find a subset S satisfying some constraints that maximizes the overall objective.This problem is first studied by Gollapudi and Sharma in [17] for modular set functions and for sets satisfying a cardinality constraint (uniform matroids). In their paper, they give a 2-approximation algorithm by reducing to an earlier result in [20]. The first part of this paper considers an extension of the modular case to the monotone submodular case, for which the algorithm in [17] no longer applies. Interestingly, we are able to maintain the same 2-approximation using a natural, but different greedy algorithm. We then further extend the problem by considering any matroid constraint and show that a natural single swap local search algorithm provides a 2-approximation in this more general setting. This extends the Nemhauser, Wolsey and Fisher approximation result [20] for the problem of submodular function maximization subject to a matroid constraint (without the distance function component).The second part of the paper focuses on dynamic updates for the modular case. Suppose we have a good initial approximate solution and then there is a single weight-perturbation either on the valuation of an element or on the distance between two elements. Given that users expect some stability in the results they see, we ask how easy is it to maintain a good approximation without significantly changing the initial set. We measure this by the number of updates, where each update is a swap of a single element in the current solution with a single element outside the current solution. We show that we can maintain an approximation ratio of 3 by just a single update if the perturbation is not too large.

The independence relation in a matroid implies the potential link between a matroid and network coding. Recently, Sun et al. proposed a algorithm of constructing generic linear network codes(GLNC) via representation of the network matroid. However, the construction algorithm was not explicitly given. Moreover, the discussion was merely on the case of GLNC. In this paper we can come to a connection between linear network coding(LNC). The main contributions of this paper are (1) to illustrate the representation algorithm of network matroid explicitly; (2) to apply the representation of three induced matroid to the construction of network code for its linear multicast (LM), linear broadcast (LB) and linear dispersion (LD) properties. Finally the complexity of the polynomial construction algorithm is analysed. Keywords: linear network code, network matroid, induced matroid, representation.

Zonotopal algebra is the study of a family of pairs of dual vector spaces of multivariate polynomials that can be associated with a list of vectors X. It connects objects from combinatorics, geometry, and approximation theory. The origin of zonotopal algebra is the pair (D(X),P(X)), where D(X) denotes the Dahmen-Micchelli space that is spanned by the local pieces of the box spline and P(X) is a space spanned by products of linear forms. The first main result of this paper is the construction of a canonical basis for D(X). We show that it is dual to the canonical basis for P(X) that is already known. The second main result of this paper is the construction of a new family of zonotopal spaces that is far more general than the ones that were recently studied by Ardila-Postnikov, Holtz-Ron, Holtz-Ron-Xu, Li-Ron, and others. We call the underlying combinatorial structure of those spaces forward exchange matroid. A forward exchange matroid is an ordered matroid together with a subset of its set of bases that satisfies a weak version of the basis exchange axiom., Comment: 34 pages, 4 figures, minor corrections, same as journal version (up to layout)

We give an excluded-minor characterization for the class of matroids M in which M\e or M/e is binary for all e in E(M). This class is closely related to the class of matroids in which every member is binary or can be obtained from a binary matroid by relaxing a circuit-hyperplane. We also provide an excluded-minor characterization for the second class., Comment: 14 pages, 4 figures. This paper has been accepted for publication in the European Journal of Combinatorics. This is the final version of the paper

Problems involving representability are among the most frequently studied of all the problems in matroid theory. This paper considers the corresponding class of problems for polymatroids. A polymatroidh on the setS is representable over a free matroid or is Boolean if there is a map ϕ fromS into the set of subsets of a setV which preserves rank, that is for all subsetsA ofS, $$h(A) = \left| {\bigcup\limits_{a \in A} {\phi (a)} } \right|$$ . The class of Boolean polymatroids is minor-closed and in this paper we investigate the excluded minors of this class. In particular, we determine all such Boolean excluded minors that are 2-polymatroids.

We study the theory of matroid Steiner families, which were introduced in a recent paper of Colbourri and Pulleyblank as abstractions of Steiner trees on graphs. Our primary result is that these families are equivalent to matroid ports.Using this equivalence, we relate these Steiner families to two fundamental matroid-theoretic constructions namely, single-element extensions and elementary quotients. We also discuss a new and very general class of Steiner families, which arise as minimal supports of affine systems. The latter half of the paper deals with the structure of Steiner complexes, which are independence systems associated with these Steiner families. We develop the notion of an S-partition of a simplicial complex which extends the notion of a shelling of a pure simplicial complex. We develop an S-partitioning theory for Steiner complexes generalizing the well-known shellability theory for the collection of independent sets of a matroid.

This paper presents a polynomial-time algorithm for solving a restricted version of the recognition problem for bicircular matroids. Given a matroid M, the problem is to determine whether M is bicircular. Chandru, Coullard and Wagner showed that this problem is NP-hard in general. The main tool in the development of the algorithm as well as the main theoretical contribution of the paper is a set of necessary and sufficient conditions for a given matroid to be the bicircular matroid of a given graph. As a final result, the complexity result of Chandru is strenghtened.

We consider the problem of randomly rounding a fractional solution $x$ in an integer polytope $P \subseteq [0,1]^n$ to a vertex $X$ of $P$, so that $\E[X] = x$. Our goal is to achieve {\em concentration properties} for linear and sub modular functions of the rounded solution. Such dependent rounding techniques, with concentration bounds for linear functions, have been developed in the past for two polytopes: the assignment polytope (that is, bipartite matchings and $b$-matchings)~\cite{S01, GKPS06, KMPS09}, and more recently for the spanning tree polytope~\cite{AGMGS10}. These schemes have led to a number of new algorithmic results. In this paper we describe a new {\em swap rounding} technique which can be applied in a variety of settings including {\em matroids} and {\em matroid intersection}, while providing Chernoff-type concentration bounds for linear and sub modular functions of the rounded solution. In addition to existing techniques based on negative correlation, we use a martingale argument to obtain an exponential tail estimate for monotone sub modular functions. The rounding scheme explicitly exploits {\em exchange properties} of the underlying combinatorial structures, and highlights these properties as the basis for concentration bounds. Matroids and matroid intersection provide a unifying framework for several known applications~\cite{GKPS06, KMPS09, CCPV09, KST09, AGMGS10} as well as new ones, and their generality allows a richer set of constraints to be incorporated easily. We give some illustrative examples, with a more comprehensive discussion deferred to a later version of the paper.

In a 1983 paper, D. Gusfield introduced a function which is called (following W.H. Cunningham, 1985) the strength of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link, this is the function η(G) = minF⊆E(G) ∣F∣/(ω(G − F) − ω(G)), where the minimum is taken over all subsets F of E(G) such that ω(G − F), the number of components of G − F, is at least ω(G) + 1. In a 1986 paper, C. Payan introduced the fractional arboricity of a graph or matroid. In terms of a graph G with edge set E(G) and at least one link this function is γ(G) = maxH⊆G ∣E(H)∣/(∣V(H)∣ − ω(H)), where H runs over all subgraphs of G having at least one link. Connected graphs G for which γ(G) = η(G) were used by A. Rucinski and A. Vince in 1986 while studying random graphs. We characterize the graphs and matroids G for which γ(G) = η(G). The values of γ and η are computed for certain graphs, and a recent result of Erdos (that if each edge of G lies in a C3, then ∣E(G)∣≥ 3 2 (∣V(G)∣ − 1)) is generalized in terms of η. The principal partition of a graph was introduced in 1967 by G. Kishi and Y. Kajitani, by T. Ohtsuki, Y. Ishizaki, and H. Watanabe, and by M. Iri (all of these were published in 1968). It has been used since then for the analysis of electrical networks in which the two Kirchhoff laws and Ohm's law hold, because it often allows the currents and voltage drops in the network to be completely computed with fewer measurements than are required for either of the Kirchhoff laws used alone. J. Bruno and L. Weinberg generalized the principal partition to matroids in 1971, and their generalization was refined independently by N. Tomizawa (1976) and by H. Narayanan and M.N. Vartak (1974, 1981). Here we demonstrate that γ and η are closely related to the principal partition and can be used to give a simple definition of both the principal partition and the more recent refinements of it.

This paper introduces a linear relaxation of the matroid matching problem, called the fractional matroid matching problem. When the matroid matching problem is in fact a matroid intersection problem, the fractional matroid matching polytope and the matroid matching polytope coincide. When the matroid matching problem is in fact a matching problem in a graph, the fractional matroid matching polytope and the classic fractional matching polytope of the graph coincide. Thus, the fractional matroid matching polytope may properly contain the matroid matching polytope. The fractional matroid matching polytope is a lattice polyhedron and, although its extreme points are not all integral, they are half-integral. This paper establishes strong relationships between extreme points of the fractional matroid matching polytope and those of graphic fractional matching polyhedra. Despite these strong relationships, adding the rank 1 inequalities does not define the matroid matching polytope. In fact, even the matching polytope of a graphic matroid is not generally described by adding these inequalities.

In this paper we describe a parallel algorithm for generating all non-isomorphic rank $3$ simple matroids with a given multiplicity vector. We apply our implementation in the HPC version of GAP to generate all rank $3$ simple matroids with at most $14$ atoms and a splitting characteristic polynomial. We have stored the resulting matroids alongside with various useful invariants in a publicly available, ArangoDB-powered database. As a byproduct we show that the smallest divisionally free rank $3$ arrangement which is not inductively free has $14$ hyperplanes and exists in all characteristics distinct from $2$ and $5$. Another database query proves that Terao's freeness conjecture is true for rank $3$ arrangements with $14$ hyperplanes in any characteristic., Improved exposition

A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box returning f(S) for a given S. We present a general approach to deriving inapproximability results in the value oracle model, based on the notion of symmetry gap. Our main result is that for any fixed instance that exhibits a certain symmetry gap in its multilinear relaxation, there is a naturally related class of instances for which a better approximation factor than the symmetry gap would require exponentially many oracle queries. This unifies several known hardness results for submodular maximization, and implies several new ones. In particular, we prove that there is no constant-factor approximation for the problem of maximizing a non-negative submodular function over the bases of a matroid. We also provide a closely matching approximation algorithm for this problem., Comment: The conference version of this paper appeared in IEEE FOCS 2009. Unfortunately there was an error in the main theorem of the FOCS 2009 paper. This long version corrects the error (see Theorem 3) and explains why the error does not affect the applications

The present paper is the first in a series of four dealing with a mapping, introduced by the present authors, from orientations to spanning trees in graphs, from regions to simplices in real hyperplane arrangements, from reorientations to bases in oriented matroids (in order of increasing generality). This mapping is actually defined for ordered oriented matroids. We call it the active orientation-to-basis mapping, in reference to an extensive use of activities, a notion depending on a linear ordering, first introduced by W.T. Tutte for spanning trees in graphs. The active mapping, which preserves activities, can be considered as a bijective generalization of a polynomial identity relating two expressions–one in terms of activities of reorientations, and the other in terms of activities of bases–of the Tutte polynomial of a graph, a hyperplane arrangement or an oriented matroid. Specializations include bijective versions of well-known enumerative results related to the counting of acyclic orientations in graphs or of regions in hyperplane arrangements. Other interesting features of the active mapping are links established between linear programming and the Tutte polynomial.We consider here the bounded case of the active mapping, where bounded corresponds to bipolar orientations in the case of graphs, and refers to bounded regions in the case of real hyperplane arrangements, or of oriented matroids. In terms of activities, this is the uniactive internal case. We introduce fully optimal bases, simply defined in terms of signs, strengthening optimal bases of linear programming. An optimal basis is associated with one flat with a maximality property, whereas a fully optimal basis is equivalent to a complete flag of flats, each with a maximality property. The main results of the paper are that a bounded region has a unique fully optimal basis, and that, up to negating all signs, fully optimal bases provide a bijection between bounded regions and uniactive internal bases. In the bounded case, up to negating all signs, the active mapping is a bijection.