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.
183
questions
102
votes
3
answers
6k
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.
Here are two examples of the kind of combinatorial abstractions of geometric ...
- 22.9k
52
votes
8
answers
5k
views
What are the external triumphs of matroid theory?
As a relatively new abstraction, matroids clearly enjoy a rich theory unto themselves and also offer a viewpoint that suggests interesting analogies and clarifies aspects of the foundations of ...
- 17.5k
46
votes
3
answers
3k
views
Category theoretic interpretation of matroids?
First time poster, long time lurker here. I have a really basic question that has been bugging me for sometime. Specifically, I'm not exactly sure what the 'correct' category theoretic definition of ...
- 2,362
29
votes
2
answers
2k
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 ...
- 2,527
17
votes
6
answers
6k
views
Good introductory text book on Matroid Theory?
I am looking for a good text book on Matroid theory. Ideally, one that might be better suited to engineers than pure mathematicians...but any book that is well written/organized would do.
I have ...
- 599
16
votes
4
answers
1k
views
Is matroid realizability computable?
I attended a talk which generalized matroid realizability over a field to matroid realizability over division rings, and showed that the question of realizability is undecidable. However, they used a ...
- 295
16
votes
2
answers
3k
views
Has anyone implemented a recognition algorithm for totally unimodular matrices?
One of the consequences of Seymour's characterization of regular matroids is the existence of a polynomial time recognition algorithm for totally unimodular matrices (i.e. matrices for which every ...
- 12.3k
16
votes
1
answer
1k
views
Is there a Sudoku matroid?
This question is inspired from this one, where it is asked what is the minimum number of checks needed to verify that a Sudoku solution is correct. Let
$$
E=\{r_1, \dots, r_9\} \cup \{c_1, \dots, ...
- 31.5k
15
votes
2
answers
722
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 ...
- 1,879
15
votes
3
answers
782
views
Log-concavity of matroids: characterization of equality?
Let $M$ be a (loopless) matroid of rank $r$.
The characteristic polynomial $\chi_M(x)$ is defined by $\chi_M(x)=\sum_{F \in \mathcal{L}(M)}\mu(\hat{0},F) \cdot x^{\mathrm{rk}(F)}$, where $ \mathcal{L}(...
- 22.9k
15
votes
1
answer
449
views
Another characterization of matroids
Has anyone seen the following characterization of matroids?
Let $\Delta$ be a simplicial complex on finite ground set $E$. Then $\Delta$ is a matroid complex if and only if, for every $X\subseteq E$ ...
- 1,440
15
votes
1
answer
673
views
Smooth bases of matroids
Motivated by algebraic geometry, I've come up with a purely
combinatorial definition within the theory of matroids.
The question is: is this concept known?
If you like matroids but not algebraic ...
- 27.7k
14
votes
5
answers
809
views
Birkhoff's representation theorem vs matroid-geometric lattice correspondence
This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
- 3,493
13
votes
1
answer
2k
views
Menger's theorem via matroids
Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...
- 103k
13
votes
1
answer
308
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 ...
- 30.2k
12
votes
3
answers
2k
views
Representability of matroids over $\mathbb R$
Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,...
- 25.3k
12
votes
1
answer
659
views
Is there Matrix-Tree theorem for counting the bases of a connected matroid?
The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
- 103k
11
votes
2
answers
867
views
Covering a random graph with spanning trees.
Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$. Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is ...
- 4,902
11
votes
0
answers
242
views
Existence of a strong antichain
Call an antichain (set of pairwise incomparable elements) $A$ of a poset $P$ strong if for every $p,q \in P$ with $p \leq q$ there exists an $a\in A$ which is comparable with both $p$ and $q$.
...
- 111
10
votes
2
answers
631
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!
user42154
10
votes
1
answer
397
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 ...
- 103k
10
votes
1
answer
391
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. ...
- 22.9k
10
votes
0
answers
243
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 ...
9
votes
2
answers
916
views
Realization space of matroids
Let $M$ be a matroid admitting a coordinatization over a complex vector space. If we know that the complex coordinatization space for $M$ is connected, then may we conclude that the matroid admits a ...
9
votes
2
answers
537
views
Book for matroid polytopes
I have made a study of polytopes with the books of Ziegler and "Integer Programming" of Conforti, my main goal is to study matroid polytopes; to study matroids I have thought about the book &...
- 201
9
votes
3
answers
801
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 ...
- 2,622
8
votes
7
answers
3k
views
Pronunciation: Crapo
A similar question reminds me: When giving talks, I often want to refer to the work of Henry Crapo. I have asked several mathematicians, and none of them were sure how to pronounce his last name. Any ...
- 151k
8
votes
2
answers
743
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 over any ...
- 603
8
votes
2
answers
199
views
Constructing a $0/1$ polytope from an abstract simplicial complex
Let us fix $\Delta$ a finite simplicial complex, and label the vertices of $\Delta$ as $\{1,2,\ldots,n\}$. For each $F\in \Delta$ let us consider the point in $\mathbb{R}^n$ given by:
$$e_F := \sum_{i\...
- 1,879
8
votes
1
answer
556
views
Representability of polymatroids over $GF(2)$
A polymatroid is a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that
1) $d(\varnothing)=0$,
2) $A \subset B$ implies $d(A) \leq d(B)$, and
3) $d(A \cap B) + d(A \cup B) \leq d(...
- 25.3k
8
votes
1
answer
404
views
p-adic versions of log concavity for graphs (or matroids)
It was recently shown using techniques inspired by algebraic geometry (by Huh and Adiprasito-Huh-Katz) that the chromatic polynomial of a graph (or matroid) has coefficients that satisfy log-concavity....
- 7,646
7
votes
1
answer
459
views
Matroid representable over $\mathbb{R}$ but not over $\mathbb{Q}$?
Does there exist a matroid that is representable over $\mathbb{R}$ but not over $\mathbb{Q}$?
In particular, can one give a positive answer using a nonrational polytope, i.e., a combinatorial ...
- 1,440
7
votes
1
answer
531
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,336
7
votes
1
answer
356
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 ...
- 623
7
votes
1
answer
185
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 ...
- 83
7
votes
1
answer
188
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\}$ ...
- 603
7
votes
1
answer
442
views
Combinatorial meaning of Kazhdan-Lusztig-Stanley polynomial
This question is motivated by
Why do combinatorial abstractions of geometric objects behave so well?
The algebraic geometry of Kazhdan-Lusztig-Stanley polynomials
Kazhdan-Lusztig-Stanley polynomials ...
- 5,038
7
votes
0
answers
134
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 ...
- 61.6k
7
votes
0
answers
166
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,...
- 305
6
votes
3
answers
1k
views
matroids axioms and independence system
A finite matroid $M$ is a pair $(E,I)$ where $E$ is a finite set and $I$ is a family of independent set with the following properties:
1) There is at least an independent system
2) Every subset of ...
- 103
6
votes
2
answers
243
views
"Minimal" connected matroids
I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently,...
- 3,493
6
votes
2
answers
478
views
A minimum set hitting every base of a matroid
We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, in ...
- 115
6
votes
2
answers
929
views
Decomposing polyhedral cones into "direct sums" and a polynomial
This question consists of two parts. I'm not breaking it up into two separate ones because posing the second question would essentially require me two rewrite the first one. Also, to some extent, the ...
- 3,493
6
votes
1
answer
293
views
Distributive lattice of subspaces
Let $V$ be a finite dimensional vector space. Let $\Lambda$ be a collection of subspaces of $V$ such that, if $X$ and $Y$ are in $\Lambda$, then $X\cap Y$ and $X+Y$ are in $\Lambda$. This makes $\...
- 151k
6
votes
1
answer
340
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 ...
- 63
6
votes
1
answer
573
views
Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbidden minors of matroids over arbitrary finite fields?
About six years ago there was a proof announced and later outlined in a notice from AMS. However right now I can only seem to find forbidden minor characterizations for matroids linearly ...
- 2,506
6
votes
2
answers
515
views
Finding the matroids with a specified set of non-bases
I'm a grad student in algebraic geometry, and I've encountered a problem which requires me to produce an algorithm involving matroids. Since this isn't my area of expertise, I'm hoping someone knows ...
- 1,510
6
votes
2
answers
779
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.
- 603
6
votes
2
answers
327
views
A generalized matroid exchange property
Let $(E,I)$ be a matroid, and let $A,B \in I$ be disjoint independent sets in the matroid. Moreover, let $B_1,\ldots, B_k$ be a partition of $B$. I could not decide if the following is always true. ...
- 163
6
votes
1
answer
291
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 ...
- 291