# Questions tagged [matroid-theory]

Questions related to the field of Combinatorics called Matroid Theory. Relevant topics include matroids in Combinatorial Optimization, Lattice Theory, Algebraic Geometry, Polyhedral Theory, Rigidity, and Algorithms. For questions about Oriented Matroids, the oriented-matroids tag may be used.

114
questions

**10**

votes

**1**answer

279 views

### Poset-troids …?

In many respects,
spanning tree : graph :: linear extension : poset
For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. ...

**2**

votes

**1**answer

125 views

### Upper-bounding $\dim \text{span}\{v_1,\dots,v_n\}$ in terms of $\dim \text{span}$ of subsets

I asked this question on Stack Exchange two weeks ago, and didn't get any answers, so I'm shamelessly reposting it here.
Let $S=\{v_1,\dots, v_n\} \subset V$ be a set of nonzero vectors in a vector ...

**1**

vote

**0**answers

49 views

### Matroids with no relaxations (~ weak maps)

There's an operation in matroid theory which is called "relaxation".
To keep things simple, let's consider a matroid $M$ with set of bases $\mathcal{B}$. If $M$ has a subset $H$ of $M$ that is both ...

**2**

votes

**2**answers

110 views

### How to generating all flats of the cycle matroid of a graph?

If $M$ is a matroid, I can use M.flats(k) in SageMath to list all the flats of rank $k$. But I hope that there is an algorithm or program to list all flats of the cycle matroid of a graph. And do not ...

**0**

votes

**0**answers

35 views

### Matroids with controlled closure growth

Let $\delta > 0$ be some rational constant, and let $r \in \mathbb{N}$ be an integer. I'm looking for an infinite familiy of Matroids of rank $r$ so that
$$ |cl(A)| = C(1+\delta)^{rank(A)}.$$
Here ...

**3**

votes

**0**answers

198 views

### Understanding this example of projective geometry in Algebraic matroids

In this paper by Evans and Hrushovski: Projective planes in algebraically closed fields,
they characterize projective planes in algebraically closed fields. These are coordinated by the skew-fields ...

**10**

votes

**2**answers

451 views

### Does the basis graph of a matroid determine it?

Let $M$ be a matroid with set of basis $\mathcal{B}$. The basis graph of $M$ is a graph with set of vertices $\mathcal{B}$ and edges $(B,B')$ always that $B$ and $B'$ differ (as sets) by exactly one ...

**2**

votes

**0**answers

45 views

### Reference request: Matroid cryptomorphisms for arbitrary monomial ideals

For a matroid $M$ let $C$ be the circuit ideal of $M$, that is, the Stanley-Reisner ideal of independence complex of $M$. Then there are simple ideal-theoretic operations that take $C$ to the facet ...

**0**

votes

**0**answers

61 views

### Paths in graphs as a vector space or matroid

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...

**0**

votes

**1**answer

130 views

### How to find all minimal dependent sets of a set of vectors effectively?

In my research, I need to find the set of all minimal dependent sets of a given set of vectors. One method is to check every subset of the given set. But this method is very slow when the set of ...

**1**

vote

**1**answer

135 views

### From Steiner systems to geometric lattices to matroids

I am looking for a specific matroid. I found a source that claimed to discuss these matroids, but then, only discusses geometric lattice. Even more, in that paper, the geometric lattice that seems to ...

**1**

vote

**2**answers

167 views

### Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube

Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...

**3**

votes

**0**answers

45 views

### Matroids which are transitive on minimal basis exchanges

I am looking for matroids in which all minimal basis exchanges look the same, that is, the matroid is transitive on these. Let me explain what I mean by that.
Consider a finite matroid $M$. Define a ...

**5**

votes

**0**answers

31 views

### Disjoint Common Transversals of Two Families of Sets

Let $E$ be a finite set. Let $d,m,n\in\mathbb N$. Let $\mathcal A:=\{A_1,\dots,A_m\}$ and $\mathcal B:=\{B_1,\dots,B_n\}$ be two families of subsets of $E$. A partial transversal of $\mathcal A$ is ...

**5**

votes

**1**answer

152 views

### Do the Odd Cycles of a Graph Define a Matroid?

An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.
Question:
does the collection of "critical" sets of vertices, whose removal renders a ...

**5**

votes

**1**answer

205 views

### Toggles for non-broken-circuit sets in matroids

Let $M$ be a matroid with ground set $E$. If $t$ is a total order on $E$, and if $S$ is a nonempty subset of $E$, then $\max_t S$ will mean the $t$-largest element of $S$ (that is, the maximum of $S$ ...

**1**

vote

**1**answer

879 views

### A new generalisation of dimension? part 2

I worked this theory : A new generalization of the dimension?
I have a theorem about dimensions which is more general and simple than for matroids.
Definition 1: A structure $S$, is a pair $(X, \...

**1**

vote

**0**answers

68 views

### When does a collection of sets forming a geometric lattice give the flats of a matroid?

Say we have a matroid on a finite set $X$. The collection of its flats forms a geometric lattice under $\subseteq$, where the join is given by intersection.
This question is about the converse to ...

**5**

votes

**1**answer

190 views

### Name of a binary matroid coming from the cycle space of a graph

In some of my recent work, I have 'discovered' a binary matroid which I will describe below.
Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...

**10**

votes

**0**answers

198 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**5**

votes

**1**answer

278 views

### Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)

Let $\left(U, d\right)$ be a finite ultrametric space -- that is, $U$ is a finite set, and $d : U \times U \to \mathbb{R}_{\geq 0}$ is a metric on $U$ such that every $x, y, z \in U$ satisfy $d\left(x,...

**6**

votes

**1**answer

205 views

### Representability of matroids over finite fields

I have several questions regarding representability of matroids.
Question 1. Does there exist a finite matroid that is representable over an infinite field, but is not representable over any finite ...

**5**

votes

**0**answers

188 views

### Can we represent partitions by mutually parallel lines in the plane?

Lately I have become interested in the following idea: Suppose $n$ is a positive integer and $[n]=\{1,2,3,...,n\}$. Suppose we have 3 distinct partitions $b$, $g$, and $r$ of $[n]$. Assume that the ...

**6**

votes

**1**answer

377 views

### Prescribing the dimension of intersections of sub-vector spaces

I asked this question on Mathematics Stackexchange, but got no answer.
Let $K$ be a field and $n$ a positive integer. To a finite dimensional $K$-vector space $V$, equipped with a family $V_1,\dots,...

**4**

votes

**1**answer

113 views

### Interchanging deletion and contraction in matroids

Let $M$ be a matroid with ground set $E$.
Deletion and contraction in matroids commute with each other and with themselves, i.e. for all $e,f \in E$ one has
$(M/e)\setminus f = (M\setminus f)/e$, $\...

**4**

votes

**0**answers

123 views

### Is this condition equivalent to being a matroid quotient?

Here is the condition, which arose in contemplating polytopes associated to matroid quotients:
Let $M$ and $N$ be matroids on $E$. If $X \subseteq Y \subseteq E$ such that $X$ is indepedent in $N$ ...

**4**

votes

**0**answers

84 views

### Totally Unimodular matrix edited from ordinary matrix

Given a matrix $M\in\{0,1\}^{m\times n}$ is there an algorithm to tell if we can convert some of $1$s to $-1$s and make $M$ Totally Unimodular and output such a Totally Unimodular in polynomial in $mn$...

**1**

vote

**0**answers

24 views

### Weight-optimal Union of Edge-disjoint Spanning Trees

I am looking for information about graphs, that are the union of $k$ edge-disjoint spanning trees "EDSP" of finite symmetric graphs. I am especially interested in theorems and algorithms related to ...

**1**

vote

**0**answers

78 views

### “Robust” partitioning of matroid unions

Let $M$ be a matroid.
(Assume that $M$ is a graphic matroid if it helps.)
Let $M^2 = M \vee M$ be a union of $M$ by itself.
See e.g. this lecture note for the definition of matroid union.
From the ...

**5**

votes

**3**answers

489 views

### Dimension and model theory

Consider an elementary class $\mathcal{K}$. It is quite common in model theory that a structure $K$ in $\mathcal K$ comes with a closure operator $$\text{cl}: \mathcal{P}(K) \to \mathcal{P}(K), $$ ...

**27**

votes

**2**answers

1k views

### Have you seen my matroid?

Let $M(n,k)$ be the matroid on the ground set $\{\pm 1,\ldots,\pm n\}$ for which a set is independent if and only if it contains at most $k$ pairs $\pm i$. Note that the signed permutation group (the ...

**5**

votes

**2**answers

234 views

### What upper bounds are known on the number of non-isomorphic cycle matroids?

For $n\in\mathbb{N}^{+}$, let $c_{n}$ denote the number of simple non-isomorphic cycle matroids of graphs on $n$ vertices. That is, let
$$A(n)=\{M(G)\;;\;G\text{ is a graph on }n\text{ vertices}\},$$
...

**7**

votes

**2**answers

406 views

### Matroids of rank two

I am interested in matroids of rank two and would like to understand how interesting/big this class of matroids is.
I know that the 2-uniform matroid on (k+2) elements is not representable on F_k (...

**2**

votes

**1**answer

68 views

### Criterion for the existence of a basis in a matroid intersecting given sets

I'm concerned with the following problem:
We are given a set $\mathcal{A} \subseteq 2^S$ of subsets of the ground set $S=E(M)$ of a matroid $M$. I would like to know whether there is a basis $B$ of ...

**4**

votes

**1**answer

576 views

### Definition of the Bergman fan

Let $M$ be a matroid on the set $\{1,\dots,m\}$. The Bergman fan $\tilde{B}(M)$ is defined in literature to be the set in $\mathbb{R}^{m}$ consisting of the vectors $v=(w_1,\dots,w_m)$ such that for ...

**9**

votes

**3**answers

516 views

### When is “metric dimension” well defined?

A subset $B$ of a metric space $(M,d)$ is called a metric generating set if and only if $$[\forall b \in B, d(x,b)=d(y,b)] \implies x = y \,. $$ A metric generating set $B$ is called a metric basis ...

**7**

votes

**0**answers

121 views

### When are two pregeometries equivalent?

Some model theorists / combinatorial geometers like to think about pregeometries (matroids with a weak finiteness condition) associated to first-order theories. But the usual way of constructing a ...

**4**

votes

**1**answer

223 views

### Non-isomorphic matroids with the same Tutte Polynomial

Im currently reading Matroids: a geometric introduction by Gordon and McNulty. Chapter 9 talks about Tutte polynomials.
My question is this Suppose we have two matroids M1 and M2. Both matroids have ...

**4**

votes

**1**answer

173 views

### A transversal matroid whose dual is not transversal

In Oxley's Matroid Theory, Problem 14.8.5, it states that it is (or at least was in 1992) an open problem to determine when the dual matroid of a transversal matroid is also transversal. I had assumed ...

**1**

vote

**0**answers

109 views

### Does this expression involving the order complex of a poset ring a bell?

Let $\mathcal{L}$ be a meet-semilattice, and denote by $\Delta(\mathcal{L})$ the poset of chains in $\mathcal{L}\setminus\{\hat 0\}$, where $\hat 0$ is the minimum element of $\mathcal{L}$.
Let $\...

**5**

votes

**0**answers

168 views

### How to define a span of a subset in matroid

Let $M$ be a matroid on a finite set $E$ and $A\subset E$. I want to define a span of $A$, but not as a subset of $M$ (which could be defined as a union of all $B\supset A$ satisfying ${\rm rank}\, B={...

**13**

votes

**1**answer

181 views

### Status of the basis exchange condition for symplectic matroids

Let $J_n := \{1,2,3,\ldots,n,1^*,2^*,\ldots,n^*\}$ with the involution $x\mapsto x^*$ exchanging $i$ and $i^*$ for $1\leq i\leq n$. The following is supposed to be standard, but to avoid any doubt as ...

**3**

votes

**1**answer

307 views

### Minimal spanning set of binary vectors

For a fixed integer $m$, does there exist a set of $a=\Theta(m)$ vectors $\mathcal{V}= \{v_1, v_2, \dots, v_a\}$ in binary Field (i.e $v_i \in \mathbb{F}_2^m$) with Hamming distance of at least $d$ ...

**88**

votes

**3**answers

3k views

### Why do combinatorial abstractions of geometric objects behave so well?

This question is inspired by a talk of June Huh from the recent "Current Developments in Mathematics" conference: http://www.math.harvard.edu/cdm/.
Here are two examples of the kind of combinatorial ...

**3**

votes

**1**answer

115 views

### Matroids of hypercubes

Let $M_k$ be the (oriented) matroid of the $2^k$ points $B_k = \{-1, 1\}^k$ in $\mathbb R^k$. In other words, the (oriented) circuits of $M_k$ are the minimal (signed) linear dependences among $B_k$.
...

**5**

votes

**2**answers

169 views

### matroids representable over root of unity partial fields that are not the 6th root of unity partial field

On reading about matroids representable over partial fields, one learns about the 6th root of unity partial field, but other even-th root of unity partial fields seem to be absent from the standard ...

**4**

votes

**1**answer

220 views

### Over the complex numbers, is there an example of an algebraic but non-representable matroid?

According to Wikipedia
https://en.wikipedia.org/wiki/Algebraic_matroid
"For fields of characteristic zero (such as the real numbers) linear and algebraic matroids coincide"
I cannot find the two ...

**0**

votes

**1**answer

77 views

### Any existing relations between association schemes and matroids

Can anyone point out (if any) references which contain any possible links between association schemes and matroids?

**10**

votes

**1**answer

440 views

### The current status of the conjecture on algebraic matroids

Can anyone point out some articles for the conjecture: the dual of an algebraic matroid is algebraic?
Thank you!

**6**

votes

**0**answers

146 views

### Matroid Representation of the Antichains of a Poset

Introduction
I am studying a problem in which the antichains of a poset are of key importance. They are naturally geometrically embedded as vectors in the space $\mathbb{R}^P$, where $P$ is the poset,...