The matroid-theory tag has no wiki summary.

**0**

votes

**0**answers

31 views

### Single element extensions of subspace arrangement over finite field

Matroids have single element extensions found by Crapo[2] to create ground set size $n+1$ matroids from ground set size $n$ matroids. Do subspace arrangements over a finite field $\mathbb{F}_q$ have ...

**-2**

votes

**0**answers

48 views

### Showing that it is a matroid with axioms [closed]

Given is $E = \{1, 2, 3, 4\}$ and $U = \{\{1\}, \{2\}, \{1,2\}\}$. Now I have to show wether $(E,U)$ is a matroid or not with the 3 axioms. I am understanding the problem and the axioms, but I'm ...

**2**

votes

**2**answers

111 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

114 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

76 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 ...

**4**

votes

**1**answer

225 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 ...

**2**

votes

**2**answers

212 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

80 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 ...

**6**

votes

**1**answer

165 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) ...

**3**

votes

**1**answer

380 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

136 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

147 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

234 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

117 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

180 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 ...

**8**

votes

**1**answer

572 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

180 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

152 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

195 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

270 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

419 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

295 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

149 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 ...

**3**

votes

**0**answers

180 views

### Oriented matroids and posets?

Is there a characterization of oriented matroids in terms of order theory, similar to that of matroids as geometric lattices?
Does this question make sense at all? I have seen (for instance in ...

**6**

votes

**0**answers

297 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

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

**7**

votes

**5**answers

2k 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 ...

**28**

votes

**8**answers

2k 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

630 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

721 views

### Menger theorem via matroids

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

**8**

votes

**2**answers

628 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 ...

**3**

votes

**1**answer

373 views

### union of matroid intersection

The following is classical theorem of Ore and Ryser, generalising famous Hall marriage theorem.
Assume that $n$ guys and $m$ girls live in a town, some guys like some girls. Three statements are ...

**6**

votes

**1**answer

319 views

### Representability of polymatroids over $GF(2)$

A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$,
2) $A \subset B$ implies $d(A) \leq d(B)$, and
3) $d(A \cap B) + d(A \cup B) \leq ...

**2**

votes

**1**answer

217 views

### Upper bound on number of lines in a linear space given degree bounds

Let $(S,\mathcal{L})$ be a linear space and $q$ be a prime power such that
Every point in $S$ lies on at most $q+1$ lines, and
Every line in $\mathcal{L}$ contains at most $q+1$ points, and at ...

**7**

votes

**2**answers

448 views

### Realization space of matroids

Let $M$ be a matroid admitting a coordinatization over a complex vector space. If we know that the complex coordinatization space for $M$ is connected, then may we conclude that the matroid admits a ...

**11**

votes

**2**answers

895 views

### Has anyone implemented a recognition algorithm for totally unimodular matrices?

One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every ...

**3**

votes

**3**answers

384 views

### Checking whether a set family forms a matroid.

Given a set family, what is the best way (empirically) to check whether the set family is equivalent to set of independent sets of some matroid. The input can be either the set family explicitly or ...

**23**

votes

**1**answer

1k views

### Category Theoretic Interpretation of Matroids?

Hello everyone! First time poster, long time lurker here. I have a really basic question that has been bugging me for sometime. Specifically, I'm not exactly sure what the 'correct' category ...

**2**

votes

**1**answer

334 views

### What interesting class of Matroids are there that contains the class of Gammoids?

I am looking for a (already-studied or interesting) class of Matroids such that
- Class of Gammoids are contained in it
One example would be Strongly-base-orderable Matroids. I would also be grateful ...

**7**

votes

**4**answers

1k views

### Pronunciation: Crapo

A similar question reminds me: When giving talks, I often want to refer to the work of Henry Crapo. I have asked several mathematicians, and none of them were sure how to pronounce his last name. Any ...

**5**

votes

**2**answers

362 views

### Complexity of determining if two graphs have same cycle matroid?

Consider the following question:
Input: Two graphs G1 and G2
Question: Is the cycle matroid M(G1) isomorphic to the cycle matroid M(G2)
What is the complexity of this question?
It is well known ...