**1**

vote

**0**answers

81 views

### Determine existence of matroid with some barrier given

Let $E$ be a finite ground set. Let $\mathcal{L}$ (as lower barrier) and $\mathcal{U}$ (upper) be subsets of $2^E$. How can we determine whether there is some matroid $\mathcal{M}=(E,\mathcal{I})$ ...

**7**

votes

**1**answer

66 views

### minimum number of bases of a matroid, that comes from a convex polytope

Given a d-dimensional polytope P with n points, then what is the minimum number of simplices that are spanned by vertices of P? This question led my research to matroids and so my question is: what is ...

**3**

votes

**0**answers

36 views

### Weighted matching and spanning set in $2$-polymatroids

A $2$-polymatroid $P$ is a pair $(S, f)$, where $S$ is a finite set and $f: 2^{S} \rightarrow \mathbb{Z}$ is a function satisfying the following:
$f(\varnothing) = 0$;
$f(X) \leq f(Y)$, for any $X ...

**3**

votes

**1**answer

203 views

### Is there a version of Robertson-Seymour's graph minor theorem known to apply to signed graphs?

Here a signed graph is one where each edge is signed either odd or even. A cycle is odd or even according to the sum of the signs of its edges. For a given signed graph, a resigning may be performed ...

**6**

votes

**1**answer

99 views

### New base of matroid from olds

Let M be a matroid of rank 3 and $E_1, E_2, E_3$ 3 basis of M. Let $e_{i,j}$ be the ith element of base $E_j$.
Is it true that you can always find a permutation s: {1,2,3} -> {1,2,3} such that ...

**5**

votes

**1**answer

125 views

### Matroids similar to the cycle matroid

Let $G=(V,E)$ be a graph (loops and multiple edges are permitted). Three following systems of dependent sets in $E$ define matroids:
1) Set $A\subset E$ is dependent if $A$ contains cycle. This is a ...

**4**

votes

**1**answer

188 views

### Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.

**0**

votes

**1**answer

56 views

### Do the support sets of subspaces give the representable matroids?

Fact: Start with $V$ a subspace of $\mathbb R^n$. Take the set of all supports of vectors in $V$. Throw out $\emptyset$. You now have the dependent sets of some matroid.
Not sure you ...

**0**

votes

**0**answers

32 views

### Non-uniform matroids as the matroid sum of uniform matroids

Can all non-uniform matroids be written as the direct sum / matroid sum of uniform matroids? If so,
What happens to the matrices representing the uniform matroids? If the non-uniform matroid is ...

**3**

votes

**0**answers

135 views

### A Result of Anders Bjorner: Matchings in countably infinite geometric lattices of finite height

Let $L$ be a countably infinite geometric lattice of finite height $r\ge3$. (A geometric lattice of height $r$ is an atomistic semimodular lattice such that every maximal chain has $r+1$ elements.)
...

**1**

vote

**1**answer

99 views

### Is the union of strongly base-orderable matroids strongly base-orderable?

A matroid is said to be strongly base-orderable if for any two bases $B_1,B_2$ there is a bijection $f:B_1 \to B_2$ such that for any $S\subseteq B_1$ set $(B_1 \setminus S) \cup f(S)$ is also a base.
...

**1**

vote

**0**answers

163 views

### Determining strong base-orderability of a matroid

A matroid is said to be strongly base-orderable when for any two bases $B_1,B_2$ there exists a bijection $f:B_1 \mapsto B_2$ such that for any $X\subseteq B_1$ set $B_1 - X+ f(X)$ is also a base.
...

**3**

votes

**0**answers

78 views

### Non-representable irreducible matroid of rank at least 5?

Can anyone tell me an example of a matroid of rank 5 or higher which is not a product of two lower rank matroids and is not the independence matroid of a finite set of vectors in a vector space over ...

**4**

votes

**2**answers

201 views

### Matroids relaxations of a given matroid

Let $\mathcal{M}$ be a rank-$d$ matroid on $[n]$. Say a matroid $\mathcal{N}$ is a relaxation of $\mathcal{M}$ if $\mathrm{rank}(\mathcal{N})=d$, $\mathrm{groundset}(\mathcal{N})=[n]$, and every ...

**5**

votes

**2**answers

294 views

### Decomposing polyhedral cones into “direct sums” and a polynomial

This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...

**5**

votes

**1**answer

268 views

### Small remarkable matroids

Working on phased matroids (a generalization of oriented matroid to the complex case) I've found an interesting formula for computing the inner Tutte group (and, hence, all the Tutte groups) ...

**5**

votes

**1**answer

288 views

### Vanishing patterns of minors of matrix

Let $M$ be a $m\times n$ matrix with entries in, say $\mathbb{C}$; assume $n\leq m$. Denote by $I\subseteq\{1,2,\ldots, n\}$ a subset of the columns of M. I am interested in positive results to the ...

**5**

votes

**2**answers

78 views

### The lattice of covectors of an oriented matroid

Let $M$ be an oriented matroid on the ground set $E$, and let $L(M)$ be its ranked poset of covectors. By definition, $L(M)$ is a sub-poset of the poset $\{0, \pm 1\}^E$, ordered by putting $0 < ...

**5**

votes

**1**answer

330 views

### Does this matroid have a name?

Sorry if this question is a dumb one.
I used a special family of matroids in my research. One of them, of rank 3, can be represented by the following matrix over $\mathbb F_5$ or over $\mathbb R$:
...

**1**

vote

**1**answer

264 views

### Positroids and Totally Nonnegative Complex Grassmanian

Recently I begin working on matroids, in particular to a generalization of oriented matroids to the complex case.
I found on arxiv the following interesting articles:
1)Alexander Postnikov: Total ...

**0**

votes

**0**answers

78 views

### Characterizing bases of 0-1-vectors in $\mathbb{R}^n$ in terms of their partial order

Given $n \in \mathbb{N}$ and $V \subseteq \{0,1\}^n$, can properties of $V$ with respect to the vector space $\mathbb{R}^n$ (not $\mathbb{Z}_2^n$),
$V$ is linearly independent
$\dim \mathrm{span} V ...

**2**

votes

**1**answer

205 views

### Looking for a canonical (matroid polytope) subdivision of the hypersimplex

A matroid polytope is the convex hull of the indicator vectors of the bases of a matroid, and a matroid polytope subdivision (MPS) is a polyhedral subdivision of a matroid polytope whose cells are ...

**2**

votes

**2**answers

157 views

### Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...

**4**

votes

**2**answers

256 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

**1**answer

106 views

### Basis of Cycle Subspace of a Graph

Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$.
For what set of edges does $\mathcal{C_e}$ contain a ...

**3**

votes

**1**answer

386 views

### Fundamental Cycles of a graphs

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$.
Now ...

**3**

votes

**2**answers

246 views

### Does this graph have a name?

Let $G$ be a connected graph on $n$ vertices and $\mathcal{T}$ be the set of all spanning trees of $G$.
Consider the graph whose vertices are the elements of $\mathcal{T}$
and
$T, T' \in ...

**2**

votes

**0**answers

122 views

### Hamiltonian Matroids

Similar to graphs, a Matroid $M$ is said to be Hamiltonian if there is a base $B$ of $M$ and $e \in M-B$ such that $B + e$ is a cycle of $M$. Is there any literature on this?
EDIT: Actually my ...

**5**

votes

**1**answer

248 views

### Checking if a matroid is binary(Detecting $U^2_4$ minor in a matroid)

I am wondering what is the (computationally) best way to tell if a matroid of size $n$ and rank $r$ is binary(or whether it has a $U^2_4$ minor) given either one of these:
1) An independence oracle
2) ...

**4**

votes

**1**answer

507 views

### Is there a graph-theoretical proof of Tutte's theorem on matroids?

First of all, I'm not a mathematician and I hope this question isn't too elementary, but I got no answers on math.SE, and since this is a reference request on a relatively advanced theorem, I thought ...

**2**

votes

**0**answers

169 views

### Schemes defined by a collection of Plücker coordinates

If $C \subset {[n]\choose k}$ is any collection of $k$-element sets, we can define a scheme $$ W(C) = \bigcap_{S\notin C} \{V \in Gr(k,n) : p_S(V)=0\} \qquad \subseteq Gr(k,n), $$ where $p_S$ is the ...

**3**

votes

**1**answer

179 views

### What is the name of this measure of matrix “degenerateness”

Given a spanning set, consider the minimum number of vectors that you must remove in order to make it no longer span. What is this number called?
If the vectors are columns in a matrix $\Phi$, then ...

**4**

votes

**0**answers

343 views

### Checking whether an element is in all inclusion-wise maximal common independent sets of two matroids

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.
It ...

**2**

votes

**1**answer

135 views

### Realizability of extensions of a free oriented matroid by an independent set

Question:
I am searching for a non-realizable matroid with few dependencies relative to the number of points. Precisely, I would like to find a non-realizable (over $\mathbb{R}$) oriented matroid $M$ ...

**2**

votes

**0**answers

404 views

### Incremental minimum spanning tree

Given a connected graph $G=(V,E)$ with a weight function $w:E\to\mathbb{R}$ and a subset $E_0\subseteq E$ such that the subgraph $(V,E_0)$ is connected, I am looking for a sequence $E_0\subseteq ...

**13**

votes

**1**answer

887 views

### Is there a Sudoku matroid?

This question is inspired from this one, where it is asked what is the minimum number of checks needed to verify that a Sudoku solution is correct. Let
$$
E=\{r_1, \dots, r_9\} \cup \{c_1, \dots, ...

**3**

votes

**2**answers

283 views

### are there pairs of combinatorial graphs that are both isospectral and have the same matroid?

Two graphs are isospectral if the combinatorial Laplacian on them has the same spectrum, equivalently, the adjacency matrix has the same the set of eigenvalues (including multiplicities). Two graphs ...

**3**

votes

**0**answers

167 views

### A non-matroidal notion of dependence on a set of ideals

Assume we are given a set of ideals $I_1, \dots, I_s$ in a commutative polynomial ring. Let's define a subset indexed by $A\subseteq [s] = \{ 1,2,\dots, s\}$ as dependent if there exists an $a\in A$ ...

**4**

votes

**1**answer

245 views

### Matroid representable over $\mathbb{R}$ but not over $\mathbb{Q}$?

Does there exist a matroid that is representable over $\mathbb{R}$ but not over $\mathbb{Q}$?
In particular, can one give a positive answer using a nonrational polytope, i.e., a combinatorial ...

**6**

votes

**2**answers

374 views

### Finding the matroids with a specified set of non-bases

I'm a grad student in algebraic geometry, and I've encountered a problem which requires me to produce an algorithm involving matroids. Since this isn't my area of expertise, I'm hoping someone knows ...

**14**

votes

**1**answer

500 views

### Smooth bases of matroids

Motivated by algebraic geometry, I've come up with a purely
combinatorial definition within the theory of matroids.
The question is: is this concept known?
If you like matroids but not algebraic ...

**3**

votes

**1**answer

340 views

### from affine matroid to measures

Let $S$ be an arbitrary finite spanning subset of $\mathbb{R}^d$ of cardinality $N$. Let
$W(S)$ be the formal $\mathbb{R}$-vector space generated by all $d$-dimensional
simplices (i.e. bases of the ...

**1**

vote

**1**answer

188 views

### When do the invariant factors of a direct sum of matrices correspond to those of its summands?

(Tried asking this on math stackexchange, but no takers so far.)
I'm trying to prove something about matroids, which I have reduced to the following question:
Suppose I have a matrix $M$ which is a ...

**6**

votes

**0**answers

325 views

### Higher K-theory of Orlik-Solomon algebras (and possible generalizations?)

This topic of this question is a bit outside my comfort zone, and I should say that my end goal is to really understand how much "graph theory" is captured by contraction-deletion relations. It seems ...

**0**

votes

**1**answer

217 views

### Is a non-disjoint union of connected matroids always connected?

This is perhaps an easy question, but...
Let $M$ be a matroid on a ground set $E$, and let $A$ and $B$ be non-disjoint subsets of $E$ such that $M|A$ and $M|B$ are both connected. Is $M|(A\cup B)$ ...

**11**

votes

**6**answers

3k views

### Good introductory text book on Matroid Theory?

I am looking for a good text book on Matroid theory. Ideally, one that might be better suited to engineers than pure mathematicians...but any book that is well written/organized would do.
I have ...

**31**

votes

**8**answers

3k views

### What are the external triumphs of matroid theory?

As a relatively new abstraction, matroids clearly enjoy a rich theory unto themselves and also offer a viewpoint that suggests interesting analogies and clarifies aspects of the foundations of ...

**11**

votes

**3**answers

829 views

### Representability of matroids over $\mathbb R$

Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in ...

**11**

votes

**1**answer

954 views

### Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...

**9**

votes

**2**answers

716 views

### Covering a random graph with spanning trees.

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...