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
15 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
15 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
0answers
15 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
30 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
35 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
12 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
38 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
40 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
47 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
61 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
56 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
35 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
54 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
15 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
50 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
74 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
19 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
32 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
36 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
32 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
24 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
79 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
27 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
34 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
57 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
58 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
38 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
87 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
32 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
200 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
113 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
107 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
65 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
54 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
68 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
101 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 ...
2
votes
0answers
450 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
19 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
186 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
59 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
82 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 ...