Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
3answers
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
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
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
2answers
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
0answers
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
1answer
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
1answer
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
3answers
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
0answers
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
1answer
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
1answer
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
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 $\...
4
votes
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
2answers
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 ...