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
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 ...
2
votes
1answer
60 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 ...
0
votes
1answer
44 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
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
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 ...
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
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
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?
1
vote
2answers
184 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
88 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
61 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. ...
3
votes
2answers
232 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 ...
1
vote
0answers
52 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 ...
2
votes
0answers
91 views

How matroids can help me locating trees inside a graph?

Background I am working on a project at present involving graph analysis. I basically need to mathematically model trees inside my graph. How can this be done using Matroids? What I am looking for ...
2
votes
1answer
72 views

Show that $\mathcal{F}_{G}$ is an Independence System, but in general is no Matroid

Let $k\in\mathbb{N}$ and $G$ be a graph. Define $$\mathcal{F}_{G}:=\{F\subset E(G): \Delta((V(G),F))\leq k\}$$ I want to show, that $(E(G),\mathcal{F}_{G})$ is always an Independence System but in ...
4
votes
1answer
629 views

Assuming $G=(V(G),E(G))$ is a graph what does $\Delta(G)$ mean?

Perhaps someone is kind enough to explain to me the meaning of this mathematical symbol, that I found in Discrete Mathematics (Matroid Theory)? Let $G=(V(G),E(G))$ be a graph. What does ...
1
vote
1answer
165 views

Proof for Matroids: Independence Oracle is polynomial equivalent to Basis Super-Set Oracle

Task: Given an Independence Oracle and a Basis Super-Set Oracle I want to proove, that they are polynomial equivalent for Matroids. First I tried to update my knowledge about the topic. Let ...
3
votes
1answer
97 views

Show that the complements of maximum matchings (extended down) form a matroid

Let $G$ be a Graph. Let $\mathcal{F}\subset\mathcal{P}(V(G))$ be a family of sets of nodes. For every set $X\in\mathcal{F}$ it is true, that there is a maximum matching $M$ which does not contain any ...
1
vote
1answer
85 views

Proving that a cycle basis has the properties of a matroid

I'm given an assignment to prove that a cycle basis has the properties of a matroid. But I'm having problems trying to understand the paragraph below excerpted from here Let a matroid be a set of ...
0
votes
0answers
237 views

Cycle Basis = Matroids? How is it even possible?

Can anyone explain to me why a cycle basis hones the properties of a matroid? Especially points 2 & 3. How can a subset of I also be a member of I? Isn't a cycle basis supposed to be consisted of ...