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.
170
questions
3
votes
0
answers
42
views
How many linear matroids are transversal
It is known that almost all matroids are not linear matroids (a.k.a. not representable matroids). This was shown by Nelson:
arXiv: Almost all matroids are non-representable
A transversal matroid is a ...
- 7,465
2
votes
0
answers
38
views
Properties of the "girth function" of a matroid
Given an independent set representation of a matroid $M=(E,\mathcal{F})$ its ``rank function'' $r$ defined on the powerset of $E$ is:
$$
\forall X \subseteq E, \quad r(X) = \max_{Y \subseteq X}\{|Y|, ...
- 6,722
1
vote
0
answers
20
views
Adding columns to a binary matroid to make it graphic
It is well-known that graphic matroids are binary. Now suppose we have a binary non-graphic matroid $M$ with representing matrix $A$ over the field $\mathbb{Z}_2$. Is there a known way to add a small ...
- 6,722
1
vote
0
answers
40
views
Are all real-representable matroids binary?
I doubt this is true but I was not able to find a clear answer to the question. Surely this is due to my erratic knowledge of matroid theory.
(I know the $U_4^2$-forbidden characterization, but I am ...
- 6,722
0
votes
0
answers
43
views
Greedy algorithm for color-balanced spanning tree
Given a graph $G = (V, E)$, we can partition $E$ to $p$ disjoint colors, i.e., $E = S_1 \cup S_2 \cup \cdots \cup S_p $. The goal of color-balanced spanning tree problem is to find a spanning tree $T$...
- 23
1
vote
0
answers
31
views
Homology of infinite matroids of finite rank
Bjorner has a great paper about the homology of independence complexes of finite matroids, which is the usual context in matroid theory as far as I understand. However, I've also been told that often ...
- 1,712
2
votes
1
answer
76
views
Is the 3-sum of two graphic matroids a graphic matroid?
A regular matroid is a matroid which is representable over any field. It is a famous theorem of Seymour's that the any regular matroid is obtained by performing 1,2, and 3 sums on graphic, cographic ...
- 153
2
votes
1
answer
71
views
How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?
I am trying to prove a simple local search algorithm could solve exactly this problem:
$\underset{S \in I(M), |S|=k}{max} c(S)$
where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $...
- 23
2
votes
1
answer
93
views
Minimum number of matroid circuits containing a fixed element
Let $M$ be a matroid with an $n$-element ground set $E$. I'll assume that $M$ is connected, co-simple (so its dual has no loops or parallel elements) and has no loops. Fix a particular element $e\in E$...
- 61
2
votes
1
answer
99
views
Algorithm for finding a minimum weight circuit in a weighted binary matroid
For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...
- 23
6
votes
0
answers
182
views
A Plücker coordinate matroid
Let $V$ be an $n$-dimensional vector space over a field $F$. Let
$\mathrm{Gr}(V,d)$ be the set (Grassmann variety) of all
$d$-dimensional subspaces of $V$. We can regard
$\mathrm{Gr}(V,d)$ as a subset ...
- 46.8k
0
votes
0
answers
69
views
Topology of independence set of a vector space
This seems like something that would have a well-known treatment somewhere, but I'm not sure where to look. If we have a vector space $V$ (or maybe even a module), we can consider an abstract ...
- 1,712
1
vote
0
answers
29
views
Associating a matroid to a uniform hypergraph
For a fixed ground set $[n]=\{1,\ldots,n\}$, and for any matroid $M$ on $[n]$, specified as a collection of bases $B_M$, the corresponding matroid basis polytope $P_M$ is defined to be the convex hull ...
3
votes
1
answer
159
views
When Alexander dual of a simplicial complex is a matroid?
Let $C$ be a simplicial complex on a finite set $V$: that means $C$ is a collection of subsets of $V$ such that if $\sigma\in C$ and $\tau\subseteq \sigma$, then $\tau\in C$.
The Alexander dual $D(C)$ ...
- 241
1
vote
1
answer
109
views
Connectivity of a matroid is at least its rank?
The connectivity $\eta(X)$ of a simplicial complex $X$ is defined as the
$$1+\min_j\{j \mid \tilde{H}_j(X)\neq 0\}.$$
If no such $j$ exists, then $\eta(X):=\infty$.
(See here for this definition, ...
- 241
6
votes
1
answer
230
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 $\...
- 145k
4
votes
0
answers
125
views
Rowmotion of matroids
If $Z$ is a finite poset, then we say that a collection $\mathcal{A}$ is an antichain if whenever $y,z\in\mathcal{A}$, if $y\leq z$, then $y=z$. If $R\subseteq Z$, then let $L(R)$ be the set of all $x\...
- 25.5k
14
votes
5
answers
719
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,173
3
votes
0
answers
113
views
Matroid of monomials of linear forms
Consider the linear matroid $M(k, d)$ on the monomials of degree $d$ in $k$ general linear forms $L_1, \ldots, L_k$ in two variables, over $\mathbb{C}$. For simplicity take $k=3$ and the forms $X, Y, ...
- 710
1
vote
0
answers
95
views
$r(M)$-subsets of a 3-connected matroid $M$
It is proved in Lowrance, Oxley, Semple, and Welsh - On properties of almost all matroids that almost all matroids are 3-connected asymptotically. Also, it is conjectured that almost all matroids are ...
- 421
3
votes
1
answer
143
views
Nontrivial upper bounds for the nullity of hyperplanes in paving matroids
$\DeclareMathOperator\null{null}$Let $H$ be a hyperplane of the paving matroid $M$ with $r(M)=n$. How large can $\null(H)$ be?
We know that $\null(H)=|H|-r(H)=|H|-(n-1)$. So everything boils down to ...
- 421
2
votes
1
answer
105
views
Counting certain bases of a paving matroids
Let $M=(E,I)$ be a paving matroid with rank $n$. Let $A\subset E$ be an $n-1$ subset. How many bases of $M$ containing $A$ exist? (Note that every $n-1$ subset of $E$ is independent.)
- 421
5
votes
0
answers
194
views
Lower bounds for the number of bases of a paving matroid
Let $M$ be a paving matroid with $m$ elements and rank $n$. Is there any lower bound for the number of bases of $M$? There is an upper bound for the number of hyperplanes (see here, page 97) but since ...
- 421
1
vote
0
answers
82
views
Conjecture for the number of ordinary lines [closed]
Let S(n) be the minimum number of ordinary lines determined over every set of n non-collinear points.
S(11)=6 S(14)=7
A=(3/7)*n
{B} = {B|3 ≤ B < n, B ∈ Odd prime}, {D} = {D|4 ≤ D <n, D ∈ Square ...
- 33
2
votes
1
answer
92
views
Non-representable matroids and Ingleton's inequality
Let $r$ be the rank function of a matroid. If the matroid is representable (over a field), then $r$ must satisfy Ingleton's inequalities. On the other hand, there are matroids that satisfy Ingleton's ...
- 2,721
2
votes
1
answer
394
views
Rank of sumsets in matroids
Assume that $G$ is a (finite) abelian group and $M$ is a matroid whose ground set is $G$. Let $X$ and $Y$ be subsets of $G$, and $H$ is the stabilizer of $X+Y$. That is $X+Y+H=X+Y$. We denote the rank ...
- 421
1
vote
0
answers
54
views
Go from one partition of the ground set to another using basis exchanges
Suppose I have a matroid $M = (E, \mathcal{I})$. It is a known fact that given any two bases $X_0$ and $X_n$, we can transform $X_0$ into $X_n$ by repeatedly applying the basis exchange axiom. So ...
- 153
2
votes
1
answer
192
views
Dimension of circuit space of a matroid
If $G$ is a graph with edge set $E$, let $W$ be the $\mathbb{Z}/2$-vector space generated by the elements of $E$. If $A = \{a_1, \dots, a_n\} \subset E$, let $\bar{A} = a_1 + \dots + a_n \in V$; then $...
- 85
2
votes
1
answer
113
views
Counting families of subsets of a fixed finite set closed under taking subsets
Let's fix a finite set $E, \#E = n$. I am interested in families $\cal S$ of subsets of $E$ with the property that if $A \in {\cal S}$ and $B \subset A$ then $B \in {\cal S}$. My question is: How many ...
- 30k
14
votes
3
answers
626
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}(...
- 20.6k
5
votes
0
answers
270
views
What do the circuits of this matroid look like?
Given any hypergraph $H=(V,E)$ we call a family of sets $I\subseteq E$ "indifferent" iff there exists a map $\phi:I\to V$ such that: $\forall X\in I(\phi(X)\in X)$ and $\forall X,Y\in I(X\...
- 2,416
3
votes
1
answer
132
views
Fast sampling of matroids
In his classic paper, Donald E. Knuth described how random matroids of fixed rank can be generated.
What is the currently the fastest (in terms of mixing behaviour) known way to sample matroids of ...
- 268
6
votes
1
answer
324
views
A Hadamard product of binary (or ternary) matroids
I would like to know if anyone has studied the following ``Hadamard product" of binary (or ternary) matroids. (There is a notion of Hadamard product of matroids studied e.g. here but I think that ...
- 898
0
votes
1
answer
136
views
Prove that a definition of $\mathcal{I}$ does not satisfy the exchange property
For a graph $G=(V,E)$ ($V$ set of vertices and $E$ set of edges ), $\mathcal{I}$ is defined as all of the subsets $E´\subseteq E$ where the components of $(V,E´)$ that are connected are simple paths. ...
- 13
1
vote
0
answers
290
views
Basis exchange property proof without use of rank and span
I want to prove that if $B_1$ and $B_2$ are distinct bases in a matroid $M$ then for any $y\in B_2$ where $y$ is not also in $B_1$ there exists $x \in B_1$ where $x$ is not also in $B_2$, such that $...
- 13
3
votes
1
answer
145
views
Does every geometric lattice of rank $r$ contain the Boolean $B_r$ as a sublattice?
A finite lattice is geometric if it is semimodular and atomistic. Geometric lattices can have arbitrarily high rank $r$, as evidenced by the Boolean lattice $B_r$ (power set of $r$ elements with the ...
- 3,214
8
votes
1
answer
380
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,302
2
votes
0
answers
120
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
7
votes
2
answers
174
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,818
3
votes
2
answers
528
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
233
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,818
1
vote
0
answers
185
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 ...
- 81
6
votes
1
answer
486
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,416
14
votes
1
answer
332
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,390
4
votes
1
answer
330
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,416
5
votes
1
answer
285
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,521
5
votes
1
answer
164
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
191
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,416
11
votes
0
answers
231
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
3
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