# Questions tagged [matroids]

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.

380 questions
Filter by
Sorted by
Tagged with
1 vote
44 views

• 2,085
42 views

### Dimers from Postnikov diagrams

I am reading several papers on Postnikov diagrams, dimer models, and quivers. From the Postnikov diagram, we can draw a dimer model and an ice quiver. My question is as follows. Does every dimer model(...
• 103
36 views

### represent linear matroid as an affine matroid

There is an exercise in András Frank’s book Connections in Combinatorial Optimization, An easy exercise shows that every affine matroid can be represented as a linear matroid, and vice versa. I ...
36 views

• 3,181
20 views

### Lift and frame matroids.

I want to read more about lift matroid and frame matroid and their flats and relations to signed graphs, do you know any basic resources for this?
• 2,069
1 vote
56 views

### The rank of $X$ in $M^*(G).$

If $X$ is a set of edges in a graph $G,$ how can we know the rank of $X$ in $M^*(G)$ in terms of $G[X].$ Where $M^*(G)$ is the dual of the graphic matroid of $G.$ Some thoughts We know that for all ...
• 2,069
1 vote
22 views

### Characteristic polynomial and bounded regions.

I know that the number of bounded regions of a homogeneous hyperplane arrangement $\mathcal{A}$(a collection of n hyperplanes) in $\mathbb R^d$is ${ n - 1 \choose d}$ but how can this be expressed in ...
• 3,181
46 views

### Understanding contraction in hyperplane arrangements.

Here are two figures that shows a hyperplane arrangement's contraction (this is from McNulty book, "Matroids, a geometric introduction"): I am not sure why a became a line in the right ...
• 3,181
88 views

• 3,181
55 views

### Some properties in Projective Geometry

I am trying to understand the following two Propositions in James Oxley's book "Matroid Theory" Prop. 6.1.3 Let $M$ be a simple rank-r matroid and $\mathbb F$ be a field. The following ...
• 95
1 vote
101 views

### Vertices of Matchings in bipartite Graph are Matroid

Let $G=(V,E)$ be a bipartite graph with $V=A \cup B$ (disjoint) and $\mathcal{F}=\{V(N) \cap B\ |\ N\ is \ a\ matching\ in\ G\}$ . Now I have to prove that $(B,\mathcal{F})$ is a matroid. The first ...
• 43
1 vote
20 views

• 3,181
65 views

### Why every component of a loopless matroid is flat?

Why every component of a loopless matroid is flat? I know that the rank of a loop in a matroid is zero and I read that: A loop is an element of a matroid that is not contained in any independent set (...
• 3,181
107 views

### The relation between the closure and the contraction of a matroid M.

Here is the relation I am trying to justify: $cl_{ M/T}(X) = cl_M(X \cup T) - T$ for all $X \subseteq E - T.$ Why this relation true? Any proof will be greatly appreciated! **Here are all what I know ...
• 3,181
1 vote
114 views

### Why does the greedy algorithm work when simplifying fractions?

Suppose we have a fraction $\frac{A}{B}$ and want to find a (possibly different) way $\frac{a}{b}$ of writing the same fraction, where $a$ and $b$ are as small as possible. In primary school we learn ...
• 10.7k
44 views

### $e \in C,$ then $e$ is a loop of $M,$ or $C - e$ is a circuit of $M/e.$

Here is the relation I am trying to understand Let $C$ be a circuit of a matroid $M.$ For e in $E(M)$: If $e \in C,$ then $e$ is a loop of $M,$ or $C - e$ is a circuit of $M/e$ ( M contract e). Does ...
• 3,181
1 vote
164 views

### circuit and a cocircuit can not have an odd number of common elements.

Here is the question I am trying to solve: Show that, in a binary matroid, a circuit and a cocircuit can not have an odd number of common elements. Here are the required definitions: A binary matroid ...
1 vote
111 views

• 2,069
1 vote