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

**1**

vote

**0**answers

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

**3**

votes

**0**answers

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

**9**

votes

**0**answers

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

**3**

votes

**1**answer

146 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,...

**7**

votes

**1**answer

145 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

143 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

179 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

78 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

60 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

77 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

19 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

74 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

438 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

191 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

330 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 (...

**0**

votes

**0**answers

108 views

### Why are two rank 2 matroids isomorphic

Assume we have two matroids $M_1$ and $M_2$ in rank 2, which have equal grounds sets. If both matroids have the same amount of parallel classes $k$ and\
or loops $l$ (but placed in different placed of ...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

270 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

446 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

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

**3**

votes

**1**answer

169 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

139 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 $\...

**4**

votes

**0**answers

112 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

155 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

254 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$ ...

**61**

votes

**0**answers

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

106 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

152 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

202 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

71 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?

**9**

votes

**1**answer

398 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

129 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,...

**0**

votes

**1**answer

48 views

### Augmention property of matroid along perfect matching

Let M be a matroid of rank k, B a base, X a set of rank rank(X) < k, and P a perfect matching of the complete bipartite graph (X, B).
Is it true that there exists an edge (x, b) of P augmenting X (...

**3**

votes

**1**answer

127 views

### Base decomposition of matroids

I want to find a generalization of the idea that, in a graphic matroid, every base can be decomposed on the stars (edges adjacent to a vertex).
For example one could say that a matroid $M$ of rank $k$...

**2**

votes

**1**answer

135 views

### Which matroids have not unique unimodular representation?

Matroid $M$ is represented by real vectors, and we know that any base of $M$ generates the same lattice (this is called unimodular representation, I guess.) If we change the sign of any vector, we ...

**1**

vote

**0**answers

163 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

95 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

52 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

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

**7**

votes

**1**answer

172 views

### New base of matroid from old

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 $i$-th element of base $E_j$.
Is it true that you can always find a permutation $s: \{1,2,3\} \to \{1,2,3\}$ ...

**5**

votes

**1**answer

187 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

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

**1**

vote

**1**answer

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

**3**

votes

**0**answers

153 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

140 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

205 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

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

**5**

votes

**2**answers

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