# Tagged Questions

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)
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...