# 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
Filter by
Sorted by
Tagged with
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
879 views

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 ...
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 ...
377 views

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$ ...
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$...
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 ...
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 ...
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),$$ ...
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 ...
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}\},$$ ...
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 (...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
109 views

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 ...
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$ ...
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 ...
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$. ...
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 ...
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 ...
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?
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,...