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
1answer
25 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
5 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
31 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 ...
0
votes
0answers
26 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
29 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) ...
0
votes
0answers
15 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
18 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
49 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
71 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 ...
1
vote
2answers
90 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
21 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
72 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
0answers
39 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
37 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
50 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
120 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
27 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
82 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} \}$$ ...
0
votes
0answers
38 views

Why is the component sum of a polymatroid analogous to size of a set and what is its relation to independence of a matroid?

I was learning about sub modularity and matroids in the following microsoft tutorial and they introduce the concept of polymatroid in parallel to matroids. In that talk they also introduce the concept ...
3
votes
0answers
41 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
45 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
47 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
0answers
8 views

Does a totally normalized version of a sub modular function form the same polymatroid?

Consider any sub modular function $f$: $$f(A) + f(B) \geq f(A \cup B) + f(A \cap B)$$ and a totally normalized version of f $\bar{f}(A) = f(A) - m(A)$ where $m(A)$ is a modular. Consider the ...
0
votes
0answers
10 views

Does the totally normalized version a sub modular f satisfy $\bar{f}(a|A) =f(a|A) - (a|V \setminus {a})$?

To provide context, I was reading the following slides and was confused about slide 55 on the presentation. Specifically what confused me is that, if we have $\bar{f}$ (i.e. a totally normalized ...
0
votes
1answer
43 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
49 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
34 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
51 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
26 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
32 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
45 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
12 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
61 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
13 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
41 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
58 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
93 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
52 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 ...
2
votes
1answer
491 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
24 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
87 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 ...
0
votes
0answers
52 views

Alternative definition of a matroid?

$\mathcal M\,$ is a nonempty subset of the set of all subsets of the finite set $X$, such that: $(1)\quad\; \neg\exists U,V\in\mathcal M:U\subset V\quad$ $(2)\quad\; A\subseteq B\in\mathcal M\wedge ...
0
votes
0answers
63 views

Topological matroids?

Are topological matroids something that has been studied? I would like to construct and study mathematical models of an abstract world consisting of a finite number of particles in a finite number ...
1
vote
1answer
84 views

Example Intersection Matroid is not a matroid.

Consider any two matroids $M_1=(E,\mathcal{I})$ and $M_2=(E,\mathcal{K})$ and let $\mathcal{Z}=\mathcal{I}\cap\mathcal{K}$. Can someone give an example where $(E,\mathcal{Z})=M_1 \cap M_2$ is not a ...
1
vote
0answers
120 views

Efficient algorithm to find a minimum spanning set for a given vector.

A few days ago a colleague proposed the following problem. Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
2
votes
1answer
103 views

Proving something is a matroid

I am taking a matroid theory class, and I am having trouble understanding an example we did in class: Let $F$ be a field, $E$ a ground set, and $V$ a vector space over $F$. Let $\phi : E ...
-1
votes
1answer
85 views

Is this function submodular?

Let $f:2^V\to \mathbb{R}$ be a symmetric submodular function. Let $T\subset V$, consider the function $f_T:2^T\to \mathbb{R}$ defined as follows: $$f_T(X) = \min \{f(Y) | X\subset Y,T\backslash ...
1
vote
1answer
51 views

Small remarkable matroids

I'm working on a problem involving matroids $M=(E,\mathfrak{C})$ (here $E$ is the ground set, $\mathfrak{C}$ the set of circuits) with a "small" ground set $E,$ in the sense that $\sharp(E)\leq7$ I ...
1
vote
1answer
85 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)