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
22 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
14 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 ...
1
vote
0answers
41 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
11 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
24 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
31 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
45 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
34 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
52 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 ...
0
votes
0answers
22 views

all maximal chains of the set of covectors of an oriented matroid have length equal to rank of oriented matroid

I have print-screened the question and what I have so far, which is basically nothing! By the way, $\mathcal{V}^* (\mathcal{M})$ is the set of covectors of the oriented matroid. The following link ...
1
vote
0answers
24 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!
1
vote
0answers
38 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
17 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 ...
1
vote
1answer
131 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
99 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
95 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
0answers
20 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
63 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
14 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\}$"? ...
1
vote
1answer
45 views

an oriented matroids question

This is an oriented matroids question, so if there is anyone who is familiar with this area of study, I would greatly appreciate your help. Suppose $M$ is an $n\times m$ real matrix of rank $n$. The ...
3
votes
1answer
65 views

Relation between topes and sign vectors

I studying the following proposition and have a question about the very last part of its proof: $\textbf{Proposition}$ The set $\mathcal{T}$ of topes of an oriented matroid ...
1
vote
0answers
78 views

prove matroid conditions

can anybody please help me to prove bicircular matroid is a matroid, from the direct definition of bicircular graph, it is also called pseudoforest. So we define the independent set to be the edge ...
1
vote
0answers
129 views

Support of a vector

What is the support of a signed vector? By signed vector, I mean a vector which is determined by considering the signs of the coefficients of the entries of another vector.
1
vote
0answers
16 views

On the invariance of the set of signed vectors of a matroid.

Let $M$ be an $n \times m$ real matrix of rank $n$. We define the set of signed vectors $V(M)$ corresponding to $M$ by $V(M):=\left\{\operatorname{sign}(\vec{x}):\vec{x} \in \ker(M)\right\}$. Prove ...
1
vote
2answers
116 views

Applications of matroid theory.

I am considering learning about matroid thoery. I would like to know what the applications of matroid theory are before (if they exist). Regards
1
vote
1answer
49 views

Distinguishing Number of Fano Plane?

I'm trying to find an exact distinguishing number for the fano plane. Through trial I've got it to D(Fano) $\leq 4$. Any ideas?
2
votes
1answer
77 views

Is there an efficient way to compute 2-separations of matroids?

Edit: Pointers to helpful references would also be appreciated, of course. The topic of matroids is a relatively new one for me and I don't personally know any experts of this subject. Thus, if I do ...
0
votes
1answer
164 views

Proof of matroids

We have set $S$ and subset $I = 2^S \setminus \{S\}$. Show that $M=(S,I)$ is a matroid. Is it graphic, linear or a matching matroid? I am little struggling how to prove this, there should be 3 things ...
2
votes
2answers
90 views

Books about matroids

Could you recommend any approachable books/papers/texts about matroids (maybe a chapter from somewhere)? The ideal reference would contain multiple examples, present some intuitions and keep formalism ...
1
vote
1answer
114 views

Submodularity of the product of two non-negative, monotone increasing submodular functions

I'm trying to prove the submodularity of the product of two non-negative, monotone increasing submodular functions Formally, we have $f$ and $g$ are submodular functions, that is, ...
0
votes
0answers
89 views

Are matroids groups?

A mathematician handed me this note about what he said was about matroids and that matroids are groups (like algebraic groups). Is that true? What is this mathematics about? Is this even about ...
1
vote
1answer
35 views

Representing a cycle matroid over GF[3]

I am working through Oxley's Matroid Theory book. An exercise in the first section asks for representations of the cycle matroid of $(K_{5}\setminus\text{ two non-adjacent edges})$ over $GF[2]$ and ...
0
votes
1answer
58 views

Different definitions of (anti-)exchange for a closure operator

Wikipedia article for matroids says For all elements $a$, and $b$ of $E$ and all subsets $Y$ of $E$, if $a\in\operatorname{cl}(Y\cup b) \setminus Y$ then $b\in\operatorname{cl}(Y\cup a) ...
1
vote
1answer
65 views

Meaning of the interval property of a set system

From Wikipedia (Note that below I corrected a place which I think is a typo): A set system $(E, F)$ is a collection $F$ of subsets of a ground set $E$. $(E, F)$ is said to have the Interval ...
2
votes
1answer
110 views

Alternative definition of and opposite concept to a matroid?

From Wikipedia In terms of independence, 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 ...
4
votes
1answer
193 views

Smallest/Minimal bases of a topological space

The smallest possible cardinality of a base is called the weight of the topological space. I was wondering if all minimal bases have the same cardinality, and if every base contains a subset whose ...
1
vote
1answer
53 views

Submodular monotone functions

A few definitions: A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup ...
1
vote
2answers
68 views

Submodular functions

A few definitions: A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions: for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup ...
1
vote
2answers
149 views

Show that a matched set of nodes forms a matroid

Let $G=(V,E)$ denote a graph. We call a subset of nodes $V^\prime\subset V$ matched if there is a matching $M\subset E$ in $G$ such that $M$ contains all nodes in $V^\prime$. We define the family ...
2
votes
1answer
82 views

What structure does the set of all the matchings in a graph have?

In a graph, the class of all the sets of vertices that can be covered by some matching forms a matroid. I wonder what kind of structure the class of all the matchings in a graph can have? Or does it ...
1
vote
1answer
58 views

Equivalence on the underlying set of a matroid?

Given a matroid $(S, F)$, $\forall x,y,z \in S$, if $\{x\}, \{y\}, \{z\} \in F$, $\{x,y\} \notin F, \{y,z\} \notin F$, will $\{x, z\} \notin F$? I can't figure this out by definition of matroid. ...
0
votes
2answers
75 views

What does the definition of matroids mean?

Given a Matroid (E,I), I is a set of independent subsets of E, right? And independent subsets means that no two of these subsets must have an element in common, right? Now according to the ...
1
vote
1answer
112 views

What are matroids and in what cases are they useful?

I came across the concept of matroids while studying up on the concept of greedy algorithms specifically The minimum spanning tree problem . I got this definition ...
0
votes
0answers
95 views

Matroid Direct Sum

According to the direct sum theorem of matroid, (1) the union of 2 matroids whose ground sets are disjoint and (2)whose independent set is defined as the union of the independent sets of the two ...
1
vote
1answer
77 views

Sub-Modular Set Function?

For a fixed set $B$ and for sets $A_i ,\forall i \in \left \{ 1,2,\dots,n \right \}$ , I define $f(A_i)=\frac{|A_i \cap B|}{2|A_i|-|A_i\cap B|}$, where $|A_i|>0$ is the cardinality of set $A_i$. ...
3
votes
2answers
219 views

How to show the complete graph $K_5$ has no abstract dual

How do you show that the dual of the matroid obtained from the 5-vertex complete graph $K_5$ is not graphic, or equivalently, that $K_5$ has no abstract dual? I assume graphs considered here are ...
0
votes
1answer
39 views

What is the analog of a uniform matroid when the ground set is not finite?

If $E$ is a finite set and $k \in \mathbb{N}$, then the uniform matroid of rank $k$ is defined as the matroid generated by taking the collection of $k$ element subsets of $E$ as a basis. Is there an ...
0
votes
1answer
62 views

what does matroid structure mean in this answer?

what does matroid structure mean in the answer to this question? I looked it up in Wikipedia but don't know which part applies to this case. What does the reply mean by "verify something forms a ...
1
vote
0answers
50 views

Adding metric to matroids in order to describe graphs whose vertices are points in Euclidean space

My concern is about finding a mathematical model in order to describe graphs as combinatorial structures (with operations like edge addition, deletion and so on), and as elements in the Euclidean ...