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
35 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
31 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
20 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
39 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
83 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
26 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
49 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
35 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 ...
2
votes
0answers
29 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
33 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
39 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
7 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
34 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 ...
1
vote
2answers
40 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
26 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
43 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
19 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 ...
2
votes
1answer
21 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 ...
1
vote
1answer
35 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!
2
votes
1answer
48 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
12 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 ...
2
votes
0answers
35 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 ...
0
votes
0answers
29 views

Intersection of a matroid's circuit with a circuit in its dual matroid

Let $M$ be a matroid, with circuit $C$. Let $x,y$ be different elements within $C$. Show that there is a circuit $D$ in the dual of $M$, so that $C \cap D=\{x,y\}$. We've given a hint to try and ...
3
votes
1answer
54 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!
0
votes
1answer
50 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
47 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
41 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 ...
1
vote
1answer
251 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
23 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
69 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
49 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
35 views

Hyperplane arrangements and matroids

I'm studying some topics related to hyperplane arrangements and matroids. I've some problem in finding some practical example. Here's my question: Let $\mathbb{K}$ be a field (suppose of ...
0
votes
0answers
53 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 ...
0
votes
1answer
61 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
80 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
84 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
77 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 ...
0
votes
1answer
42 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
71 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)
1
vote
1answer
132 views

Meaning of the characteristic polynomial of a matroid

From wikipedia The characteristic polynomial of a matroid $M$ (which is sometimes called the chromatic polynomial,[29] although it does not count colorings), is defined to be $$ p_M(\lambda) ...
2
votes
2answers
113 views

Equivalent definitions for a coloop?

From wikipedia, in a matroid, An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis. I wonder why the equivalence? From ...
0
votes
1answer
27 views

How do the dependent sets of a matroid characterize the matroid?

Wikipedia says: The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid. So I ...
1
vote
1answer
33 views

What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
1
vote
0answers
31 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
2
votes
0answers
42 views

Inequality in matroid theory

Working on a proof in matroid theory I found there is a smooth map from an open set of $(\mathbb{C}^{\ast})^{(d−1)(n−d−1)}$ to a disjoint union of tori $(S^{1})^{\binom{n}{d}-n}.$ As a direct ...
1
vote
0answers
18 views

Help Understanding Polymatroids

I have learned that polymatroids are of the form $$\left\lbrace x\in \Bbb R^N_{\ge 0}\mid \sum_{i\in A}^n x_i\le p(A), \forall A \subseteq \lbrace 1,\ldots,N \rbrace\right\rbrace$$ where $p$ is is non ...
2
votes
1answer
97 views

Some questions on matroid

I have an unknown questions as follows. Thank you in advance. Let $M=(E,I)$ be a matroid and let $B$ and $B′$ be two disjoint bases of $M$. Let $B$ be partitioned into sets $Y_1$ and $Y_2$. Show ...
1
vote
0answers
52 views

How to prove whether a given matroid is a Gammoid?

Statement : Given a matroid in some representation say $(E,I)$. How do we prove it is a gammoid? For example to prove a matroid is transversal, we try to create a bipartite graph. If we are unable ...