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.

Filter by
Sorted by
Tagged with
10
votes
1answer
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
1answer
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
0answers
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
2answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
3answers
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
2answers
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
2answers
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
2answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
3answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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,...