Matroids are a common generalization of linearly independent sets and independent sets in graphs. Among other applications, they are exactly the simplical complexes in which the greedy algorithm outputs the optimal solution. Matroids are also studied for their own sake.

learn more… | top users | synonyms

0
votes
0answers
14 views

Number of Different Bases in a Matroid

I am trying to figure out a lower bound on the number of different bases a matroid can have. The matroid has rank n and its ground set is the disjoint union of two bases. I think that it's $2^n$ ...
0
votes
1answer
16 views

the rank of a matroid $\mid X \mid + r(E\backslash X)-r(E) \geq 0 $

If I have the matroid $M=(E,I)$ and $\mid X \mid + r(E\backslash X)-r(E) \geq 0 $ . Can someone give me any idea about how I can prove it ?I was thinking to: I know that $\mid X \mid \geq r(X)$ then I ...
0
votes
0answers
12 views

Lattice of Flats of Graphic Matroid and Intersection Lattice of Graphic Arrangement

Let $G$ be a simple graph. We will be looking at hyperplane arrangements in $\mathbb{R}^d$. Suppose $\mathcal{H}$ is the graphic hyperplane arrangement arising from $G$. Let $L(\mathcal{H})$ be the ...
1
vote
0answers
10 views

Definition of circuits in matroid theory

I am reading about matroids and I am kind of confused in the following definition. A nonempty subset $C$ of $\{0,1,...,n\}$ is a circuit of $I$ if $C= supp(l)$ for some nonzero linear form $l$ in ...
0
votes
0answers
10 views

What are some interesting applications of the Bixby-Coullard inequality?

Recall that the connectivity function $\lambda_{M} = \lambda$ of a matroid $M$ may be defined as follows, letting $X$ be an arbitrary subset of the ground set of $M$ (and letting $r_{M} = r$ denote ...
1
vote
1answer
23 views

How to find a maximum matching which considering the weight of vertex

First, if G=(V,E), and C is the collection of all vertices set which can be covered by a matching in G. I have proved that such (V,C) is a matroid. And each vertex $v_i$ has a weight $w(v_i)$, how ...
1
vote
0answers
21 views

Definition of Quasi-Concave Set Function for an Accessible Set System

Is $F(C(X\cup Y))\ge \min(F(X),F(Y))\ \forall X,Y$ where $(E,\mathbb{F})$ is a set system with $X,Y\in E$ the definition of a quasi-concave set function? $E$ is a set of all possible subsets of ...
3
votes
0answers
62 views

Is there a connection between the “independent sets” in matroids and “independent sets” in graph theory?

I've been reading up on matroids recently, which are used in the theory of greedy algorithms. A matroid is a pair $(X, I)$ where $X$ is a set and $I \subseteq \wp(X)$ is a family of sets over $X$ ...
0
votes
0answers
6 views

Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
1
vote
0answers
15 views

Matroids on set systems

Let $\mathcal{F}$ be a collection of subsets of a finite set $X$, partially ordered by inclusion, and let $\mathcal{I}$ consist of the antichains of $\mathcal{F}$, taken as independent sets. Under ...
0
votes
1answer
22 views

basic understanding of hereditary property in matroid

I'm trying to prove something is a matroid and to do that I must understand what a matroid is. I don't get the hereditary property. A matroid is an ordered pair $(S, I)$. I is a non-empty family ...
1
vote
1answer
52 views

Prove that a real matrix is a matroid

Problem $A$ real matrix, size $m\times n$ $M$ some structure, possible matroid $E(M)$ set of all columns of $A$ (we're considering them vectors) $I(M)$ set of all linearly independent columns of $A$ ...
0
votes
0answers
7 views

Transforming a vector configuration to an affine point configuration

I am reading the first chapter of Oriented Matroids by Bjorner et. al, in which they consider the set of vectors $\mathbf{v}_1,\mathbf{v}_2,\dots,\mathbf{v}_6$ given as the columns of the following ...
0
votes
0answers
35 views

How to prove that rank(closure(A))=rank(A)

I'm doing a project on matroid theory and one of the properties I have to prove for closure operations is that closure(closure(S))=closure(S) but to do this I need to use a lemma that ...
1
vote
0answers
33 views

On the base axioms of a matroid

The base axioms of a matroid state that A collection $B\subseteq 2^E$ is a set of bases of a matroid M(E,I) if and only if the following hold B1: $B\neq \emptyset$ B2: If $B_1,B_2\in B$ and $x\in ...
0
votes
1answer
31 views

Does maximising modular functions carry the same properties as maximising submodular functions?

A function $f:2^V\to \mathbb{R}$ is submodular if for the sets $A$ and $B$ with $A \subset B$ we have that $$f(A) + f(B) \geq f(A\cup B) + f(A\cap B)$$ or equivalently that $$f(A\cup \{v\}) - f(A) ...
1
vote
0answers
20 views

intersection and union of two independent sets is independent in matroid

As we know that, a matroid $M$ is a pair $(U,\mathcal{I})$ where $U$ is a finite set and $\mathcal{I}\subseteq \mathcal{P}(U)$ satisfying $\varnothing \in \mathcal{I}$, if $Y \in \mathcal{I}$ and ...
1
vote
0answers
23 views

Determine existence of matroid with some barrier given

Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...
0
votes
1answer
50 views

Matroids and minimal dependence

Let $M = (E, S)$ be a matroid and $D$ be the set of all minimal dependent sets of $M$. Prove that if $A_1, A_2 \in D$ such that $A_1 \neq A_2$, and if $x \in A_1 \cup A_2$, then there exists $B \in ...
2
votes
1answer
75 views

Matroids and forests

Let $G = (V, E)$ be an undirected graph. For all $k \in \mathbb{N}$ set $M_k(G) = (E, S)$ where $S = \{ A \subseteq E | \exists M, F \subseteq E$ such that $ |M| \leq k, F$ is a forest and $ A = F ...
2
votes
2answers
96 views

List of all matroids

List all matroids $(E, S)$ with $E = \{1\}, E = \{1, 2\}, E = \{1, 2, 3\}$. I know that $(E, S)$ is called an independence system, and that according to the definition $S \subseteq 2^E$ and $S$ ...
0
votes
0answers
23 views

Maximize number of bins and minimize cost of elements chosen from a set

I am considering the following problem: there is a set of elements $S$ where each element is assigned to a bin $B$. The bins are disjoint and their union is $S$. There is also a cost function ...
1
vote
1answer
75 views

Sign patterns in kernel and rowspace of a matrix

I'm looking for the reference of the following fact from oriented matroid theory. This must be known; in fact, I think it is in the book "Oriented Matroids" by Björner et al., but I can't locate it. ...
4
votes
1answer
56 views

Proving that the intersection of two closed sets is closed in a matroid

I am stuck on a little homework problem I have. Here, $M$ is a matroid with rank function $R$. I am given this definition: In a matroid $M$, a set $A$ is closed if $R(A \cup e) > R(A)$ for all $e ...
2
votes
0answers
42 views

What does it mean to be equicardinal?

I'm reading up on matroids and have run into a lemma (and proof for said lemma) stating that the bases of a matroid are equicardinal. I assume that it means the bases have the same cardinality, but ...
0
votes
2answers
55 views

Signing of a binary matrix to a totally unimodular matrix

I have the following binary matrix: \begin{pmatrix} 1& 1& 1& 0 \\ 0& 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ \end{pmatrix} Definition: Signing a matrix ...
1
vote
1answer
125 views

Matching between $n$ men and $m$ women

There is a group of $n$ men and $m$ women, and there is a symmetric dating between them (between the men and the women). How can we find a match between the men and the women (depending to the ...
3
votes
0answers
29 views

Clarification on an argument in a Matroid paper

I am currently reading this paper on matroids. http://arxiv.org/pdf/1411.2277.pdf I am reading the proof to proposition 3.17 which involves transversal matroids. "In particular, any coloop is ...
2
votes
3answers
99 views

What is the proof that the rank of a matroid is sub-modular?

Recall the definition of the rank of a matroid $(V, \mathcal{I})$: $$ r(A) = \operatorname{rank}(A) = \max_{I \in \mathcal{I}}\{ | A \cap I | \} = \max\{ |I| : I \subseteq A, I \in \mathcal{I} \}$$ ...
3
votes
0answers
44 views

Intuition for oriented matroids

Can someone provide some intuition on oriented matroids? Also how do you get the chirotope of a oriented matroid from the signed circuits? (other than just work backwards) Also is there any nice ...
0
votes
1answer
57 views

Matrices M such that for a fixed A there exists B such that M = AMB

I'm interested in characterizing the $m×n$ matrices $M$ such that for a fixed $m×m$ matrix $A$, there exists an $n×n$ matrix $B$ such that $M=AMB$. I'm not sure if it makes the question easier or ...
0
votes
1answer
50 views

Closure function of a matroid

I need some help to understand: If $M$ is matroid and e is an element in that matroid, what is the closure function of $M\setminus e$? And what is the closure function of $ M/e$? Any help would be ...
0
votes
1answer
51 views

What is the justification for calling a hereditary system an independent system?

I was learning about set systems and hereditary systems and I noticed that they also call a hereditary system a independence system and that didn't quite make sense to me intuitively. First recall ...
2
votes
2answers
54 views

How to show that a matroid doesn't have any circuits if and only if the entire set is the only base?

The question is pretty self explanatory. I'm working with the definitions: Matroid (Bases) $(E,\mathcal{B})$ 1) No base is a subset of another base 2) $B_1,B_2 \in \mathcal{B}$ and $e \in B_1$ ...
1
vote
2answers
41 views

Let $M$ be a matroid with circuit $C$, and $x,y \in C$. Prove that there is a cocircuit $D$ so that $x,y \in D$. Contradiction?

Let $M$ be a matroid with circuit $C$, and $x,y \in C$. Prove that there is a cocircuit $D$ so that $x,y \in D$. My problem: We learned in class that $Y$ is dependent in $M^*$ iff for every basis $B ...
2
votes
1answer
59 views

Matroids: Prove that for circuit $C$ and its cocircuit $C^*$: $|C \cap C^*| \neq 1$

Prove that for circuit $C$ and its cocircuit $C^*$: $|C \cap C^*| \neq 1$ Any hints and assistance would be very nice! Thank you.
0
votes
1answer
27 views

If $M$ is a matroid, and $e \in M$, than what is the closure function of $M/e$, and what is the closure function of $M\setminus e$?

If $M$ is a matroid, and $e \in M$, than what is the closure function of $M/e$, and what is the closure function of $M\setminus e$? What I find confusing to start with, is what elements does the ...
3
votes
1answer
39 views

Not understanding the uniqueness of uniform matroid

According to Oxley's Matroid Theory, page 19 (second edition), a uniform matroid is a matroid with $n$ elements in set $E$, so that for some integer $m$ the set $I$ is defined: $I(U_{m,n})=\{X ...
2
votes
1answer
47 views

Why does the feasible set being a matroid ensure a polynomial time algorithm?

Reading up on matroid theory in the context of graph optimization and in particular minimum spanning trees. It turns out that finding a set of acyclic arcs is equivalent to finding an independent ...
1
vote
0answers
13 views

Does a Matroid's graph not having 3-separation mean its dual doesn't have 3-separation?

Let there be a graph $G$, with a matroid $M(G)$. If there is no 3-separation in $M$, does it imply there isn't one in $M^*$? Any hints would be much appriciated!
3
votes
1answer
62 views

Theory of matroids and euclidean representation

I am looking for the definition of the "euclidian representation" of a matroid. I guess it is used for graphic matroids but impossible to find the construction for this representation. Thank you for ...
0
votes
1answer
14 views

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets?

If $M=(E,S)$ and $N=(E,F)$ are 2 partition matroids, and $I=S \cap F $ . Is there a matroid with $I$ being its set of independent sets? My intuition says it's correct because $M,N$ are ...
1
vote
0answers
42 views

Good and thorough online and/or free Matroid Theory references?

I'm studying a course on Matroid theory. Sadly, I can't really afford buying the textbook, so I only use the lecture notes, which aren't enough for me. Are there any good and thorough online and ...
3
votes
1answer
59 views

How many matroids with 1 element exist?

So we got the following question in the lecture: How many matroids with a single element exist? Couldn't really think of an answer. Any assistance would be of help!
1
vote
1answer
133 views

Matroid Isomorphism Definition

I'm working though Welsh's Matroid Theory work, and he very casually mentions matroid isomorphisms in the first chapter but I don't think I like his statement. He says that two matroids ...
0
votes
1answer
51 views

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$

Finding representation matrix of $M$*$(K_5)$ above $\mathbb F_2$. $M$*$(K_5)$ is the dual matroid representing the graph $K_5$, that is, a complete graph with 5 vertices. How do I solve this? ...
1
vote
0answers
56 views

Example of a k-matroid

Let the set $K_i = (S, I_i)$ be a matroid for each $i \in \{1 \ldots k\}$. We define $K = (S, I) $ where $I = \{ X \subset S $ | $ X \in \bigcap_{i=1}^k I_i\}$ The claim now is that $K$ is a ...
3
votes
1answer
605 views

How are inclusion-wise maximal and minimal sets defined?

I have tried to find them over the internet, but am lacking a resource that rigorously defines these two terms.
1
vote
1answer
25 views

Natural properties of graph cycles that do not hold for circuits in a matroid?

In a graphic matroid $M(G)$, circuits correspond directly to cycles in the original graph $G$. This means that any property that can be defined for both a circuit in $M(G)$ and for a cycle in $G$ ...
0
votes
0answers
94 views

Are matroids really a generalization of independence in vector spaces?

The axioms of matroids are (Wikipedia): A finite matroid $M$ is a pair $(E,\mathcal{I})$, where $E$ is a finite set (called the ground set) and $\mathcal{I}$ is a family of subsets of $E$ (called ...