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
25 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
42 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
30 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
43 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
13 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
47 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
60 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
18 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
26 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
24 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
31 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
8 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
32 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
14 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
28 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
22 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
62 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
24 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
33 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
45 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
57 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
37 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
73 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
23 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 ...
2
votes
1answer
31 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
50 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
18 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
150 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
110 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
103 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
32 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
64 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
19 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
51 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
67 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
90 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
284 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
18 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
150 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
54 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
80 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
182 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
101 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
129 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
99 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
40 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
61 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
73 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
121 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 ...