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

1
vote
1answer
26 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
26 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
11 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
28 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
21 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
46 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
0answers
22 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
37 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
34 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
37 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
20 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
38 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
44 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
20 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
44 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
47 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
52 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
67 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 ...
0
votes
1answer
60 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
37 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
60 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)
0
votes
0answers
17 views

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid?

Must the weight function be nonnegative for the greedy algorithm to be optimal for both a matroid and a greedoid? For a matroid, the codomain of the weight function is $[0,\infty)$, from Wikipedia ...
1
vote
1answer
56 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
81 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
25 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
28 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
27 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\}) \}$$ ...
0
votes
0answers
33 views

Two definitions of matroid

From Wikipedia, a finite matroid $M$ is a pair $(E,F)$, where $E$ is a finite set and $F$ is a family of subsets of $E$ either with the following properties: The empty set is in $F$. if $X \in ...
0
votes
0answers
9 views

Rank feasible subset of a greedoid

From Wikipedia, given a greedoid $(E,F)$, with ground set $E$ and the class $F$ of feasible sets, A subset $X$ of $E$ is rank feasible if the largest intersection of $X$ with any feasible set has ...
2
votes
0answers
39 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
16 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 ...
0
votes
0answers
34 views

questions on rooted forest

Let $D = (V;E)$ be a connected directed graph and let G be its subjacent graph. Let $I_1$ be the family of independent sets of the graphic matroid $M[G]$. Let $I_2$ be the collection of subsets $Y$ E ...
0
votes
0answers
28 views

Matroid quotients

It is known (for example see Oxley "Matroid theory") that for any matroid $M$ and its quotient $N$ there exists a sequence of matroids $M=M_0,M_1,…,M_r=N$ such that for each $i$, $M_{i+1}$ is an ...
2
votes
1answer
88 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
30 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 ...
0
votes
0answers
38 views

matroids axioms and independence system

A finite matroid $M$ is a pair $(E,I)$ where $E$ is a finite set and $I$ is a family of independent set with the following properties: 1) There is at least an independent system 2) Every subset of ...
0
votes
1answer
63 views

Contraction of loops in matroids

If $M=(E,I)$ is a matroid, and $e$ is not a loop (a loop is an element of the matroid which is not an element of any independent set), we may define the matroid obtained by contracting $e$ to be the ...
1
vote
1answer
60 views

Circuits in a linear oriented matroid

Given $E$ a finite subset of a real vector space $V$, a circuit of the associated matroid is a minimal linearly dependent subset of $E$. For each circuit $\underline X$, a minimal linear dependence ...
1
vote
1answer
41 views

Rotors in graphs and rank polynomial (Tutte polynomial)

I am studying the $Rank$ $polynomial$ through matroid theory. I have seen that the rank polynomial doesn't determine the graph. In fact, as the the cycle matroid of a graph can distinguish the graph ...
1
vote
1answer
98 views

How many regions are created by the set of all hyperplanes defined by a set of points?

If we have a set of points X in d-dimensional euclidean space, and we look at the set of all n-dimensional hyperplanes that are defined by any subset Y of X (in the sense of being the unique ...
2
votes
1answer
34 views

every rank 2 oriented matroid is realizable

Does anyone know where I can find the proof for why every rank $2$ oriented matroid is realizable? Thank you!
2
votes
0answers
51 views

convexity in oriented matroid theory

I would like to try to solve the following problems. If someone knows how to prove at least part (a), could you show me the proof? I am having a LOT of trouble understanding oriented matroid theory. ...
1
vote
0answers
19 views

elements of oriented matroids belonging either to positive circuits or positive cocircuits

I need to prove the following, which seems trivial because it follows from the Farkas lemma (you may know this as the 3 or 4 painting lemma). Can someone show me how to prove this, please? I'm a bit ...
2
votes
1answer
228 views

Proving Cographic matroid is indeed a matroid

Given a connected graph $G=(V,E)$ let us define $M(G)=(E,I)$ where $I=\{E'\subseteq E | (V,E\backslash E') \text{ is connected}\}$. When proving $M(G)$ is a Matroid we must show: if $A,B\in I$ ...
4
votes
1answer
117 views

Where can I find a proof of Tutte's theorem?

I dislike the proof of Kuratowski's theorem in my textbook, but the book mentions a theorem of William Tutte: Theorem: A graph $G$ is planar if and only if the conflict graph of each cycle of ...
5
votes
1answer
109 views

Why are there exactly two cocircuits for a given basis $B$ and $e\in B$?

I am very unfamiliar with the topic of oriented matroids and am just learning about it. I want to prove the following result which is needed to define fundamental cocircuits. Alas, I did not succeed ...
0
votes
1answer
33 views

Representing Matroids Graphically

Is it possible to represent M a matroid on E = {a,b,c,d,e} with bases ac,ad,ae, bc, bd, be, ce, de. graphically? I'm familiar with the methods with larger bases but not bases of size 2. Any help ...
1
vote
1answer
66 views

Why is it true $\operatorname{rank}_{\underline{\mathcal{M}}}(E^0)=0$

This is a question which is related to a previous one. It is about the proof of Theorem 0.7.10 in this PhD-Thesis. The question reduces to the following. Let $M=(E,\mathcal{A})$ be a matroid, that is: ...
1
vote
0answers
21 views

question about matroid lingo

If you have an independent set of vectors $\left\{v_{i_1},\ldots , v_{i_{n-1}} \right\}$, what does it mean for a vector to be "supported on the complement of $\left\{i_1, \ldots , i_{n-1} \right\}$"? ...