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
2
votes
0
answers
128
views
What's known about the matroid induced by the Plücker coordinates of the representation of a matroid?
Let $M$ be a linear matroid with ground set $E$ and independent subsets $\mathcal I$, represented by $\rho: E \rightarrow V$.
This induces a map
$$
\hat\rho: \mathcal I \rightarrow \mathbf P(\Lambda V)...
- 193
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
3
votes
2
answers
720
views
Open problems in matroid theory
I read Oxley's book on matroid theory and found the theory fascinating. At the end, Oxley stated some open problems and conjectures in matroid theory.
Are there any modern lists about such problems?
...
- 109
3
votes
2
answers
272
views
Inequality of $h$-vectors of shellable simplicial complexes
I've been studying the article of Bjorner entitled "Homology and shellability of matroid complexes". At a certain point he states an exercise that says:
Let $\Delta$ be a shellable ...
- 1,879
1
vote
0
answers
212
views
Cohomology of realization space of matroid
Do we know any thing about cohomology of realization space of matroid (the space of all set of vectors in $\mathbb{C}^k$ which captures the independence structure of matroid $M$), more simple, for ...
- 91
6
votes
1
answer
571
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
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
4
votes
1
answer
409
views
What is the significance of ear decompositions for non-graphic matroids?
On Wikipedia there is subsection in the article on ear decompositions of graphs titled "Matroids":
Now as defined above, the circuits of a matroid can not always be listed to satisfy the ...
- 2,506
5
votes
1
answer
357
views
Exchanges between independent sets of a matroid
Let $I, J$ be two bases of a matroid. For every $x$ in $I$, there is some $y$ in $J$ such that, if we exchange $x$ with $y$, then both resulting sets ($I \setminus x \cup y$ and $J \setminus y \cup x$)...
- 3,585
5
votes
1
answer
168
views
Minimum number of independent pairs in a matroid
Given a matroid $M$ with ground set $E$ of size $2n$, suppose there exists $A\subseteq E$ of size $n$ such that both $A$ and $E\setminus A$ are independent. What is the minimum number of $B\subseteq E$...
- 143
3
votes
2
answers
212
views
When do the circuits of a matroid have a connected intersection graph?
When does a matroid $M$ have a set of circuits $\mathcal{C}$ with a connected intersection graph i.e. when is the graph $G$ with$V(G)=\mathcal{C}$ and adjacencies $\{A,B\}\in E(G)\iff A\cap B\neq\...
- 2,506
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
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
2
votes
1
answer
55
views
Extending spanning sets on contractions of matroids
Suppose you have a matroid, and $T$ is a subset of a spanning set $S$.
Now consider the contraction of the matroid to the set $T$ and suppose $X$ is a spanning subset of $T$ with respect to that ...
- 1,388
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
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
2
votes
0
answers
57
views
The best way for obtaining the canonical label of a matroid?
For a graph, we can canonical labelings with Nauty or other methods. But for a matroid, I do not find an easy way to labeling.
Dillon Mayhewa, Gordon F. Royle introduced the hyperplane graph of a ...
- 51
5
votes
0
answers
214
views
Set-theoretic generation by circuit polynomials
Let $P$ be a prime ideal in $S=\mathbb{C}[x_1,\ldots , x_n],$ and write $[n] = \{ 1, \ldots , n \}.$ The algebraic matroid of $P$ can be defined according to circuit axioms as follows: $C\subset [n]$ ...
- 388
4
votes
0
answers
103
views
Maximal number of smallest circuits in a matroid
It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$.
Since this can be be ...
- 3,024
5
votes
1
answer
441
views
Extending submodular functions from a sublattice
This came about when I was studying the connection between matroids and strong
greedoids, but it has broken through into a subject I am not particularly
familiar with: submodular functions on lattices....
- 33.2k
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
2
votes
1
answer
154
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,010
1
vote
0
answers
146
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 ...
- 1,879
3
votes
2
answers
374
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 ...
- 51
4
votes
0
answers
263
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 ...
- 407
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
2
votes
0
answers
66
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 ...
- 974
0
votes
0
answers
160
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 ...
- 612
1
vote
1
answer
197
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 ...
- 6,121
1
vote
1
answer
218
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 ...
- 12.6k
1
vote
2
answers
235
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 ...
- 774
3
votes
0
answers
60
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 ...
- 12.6k
5
votes
0
answers
55
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 ...
- 1,388
5
votes
1
answer
226
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 ...
- 12.7k
5
votes
1
answer
273
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$ ...
- 33.2k
1
vote
1
answer
994
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, \...
- 3,801
1
vote
0
answers
89
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 ...
- 1,513
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
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 ...
5
votes
1
answer
329
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,...
- 33.2k
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
5
votes
0
answers
275
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 ...
- 1,267
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
4
votes
1
answer
279
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$, $\...
- 43
4
votes
0
answers
277
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$ ...
- 1,702
4
votes
0
answers
92
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$...
- 13.7k
1
vote
0
answers
29
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 ...
- 12.7k
1
vote
0
answers
84
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 ...
- 75
5
votes
3
answers
634
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), $$ ...
- 8,186
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