# 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

1
vote

0
answers

72
views

### Reconstructing a matroid by its minors

Proposition 3.1.27 in Oxley's Matroid Theory says that given a matroid $M$ and an element $e\in E(M)$ such that $e$ is not a loop or a coloop, the pair $(M/e, M\setminus e)$ uniquely determines $M$. ...

1
vote

0
answers

37
views

### Hyperplane arrangements and tropical linear spaces

I have been trying to understand Chapter 5.4 of this Brief Introduction to Tropical Geometry, but I am struggling because of my lack of mathematical background. I will ask a few questions after giving ...

5
votes

1
answer

104
views

### The Salvetti complex of a non-realizable oriented matroid

Given a real hyperplane arrangement, the Salvetti complex of the associated oriented matroid is homotopy equivalent to the complement of the complexification of the arrangement. In particular, its ...

0
votes

0
answers

38
views

### Weighted matroid intersection algorithm

From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen:
...

4
votes

1
answer

167
views

### Lattice description of matroid duality

Apologies for this very basic question in matroid theory, but I could not find anything about it online after a bit of searching.
There is a well-known bijective correspondence ("cryptomorphism&...

4
votes

0
answers

197
views

### A matroid parity exchange property

As part of my research, I encountered the following problem. Let $M = (E,I)$ be a matroid and let $P = \{P_1,\ldots,P_n\}$ be a partition of $E$ into (disjoint) pairs. For $A \subseteq P$, we say that ...

1
vote

0
answers

58
views

### Matroid for Laurent series

I am trying to find a matroid for profinite rings which are the inverse limit of their finite quotients, and whose linearly independent elements are of the form $L((t_1,\dots,t_n))$.
To set this up, ...

6
votes

2
answers

326
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. ...

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 &...

0
votes

0
answers

79
views

### Establishing a matroid for higher local fields K/L((t₁,..,tₙ))

In the theory of matroids, the Cohen structure theorem and theorem on transcendence degree that each field is algebraic over a field of the form k(x₁,..., xₙ), as well as Noether normalization, fall ...

0
votes

0
answers

55
views

### Constructive proof sought for a theorem of J. de Sousa related to Hall's Marriage Theorem

The following is the finite version of Theorem 7 in the article by J. de Sousa, "Disjoint Common Transversals," Combinatorial Mathematics and its Applications: Proceedings of a Conference ...

3
votes

1
answer

100
views

### Does a matroid base polytope contain its circumcenter?

Let $(X,\mathcal B)$ be a matroid on the ground set $X=(x_1,...,x_n)$ and with set of bases $\mathcal B$, and let $P\subset\Bbb R^n$ be its matroid base polytope (i.e. the convex hull of the ...

6
votes

2
answers

242
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,...

1
vote

0
answers

45
views

### Minimal matroid of rank r size n

We can define a partial order $\leq$ on loopless matroids, such that $M_1\leq M_2$ if $M_1$ and $M_2$ are on the same groundset and $B_1\subseteq B_2$, where $B_1$ and $B_2$ are the set of bases of $...

3
votes

0
answers

68
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 ...

2
votes

0
answers

50
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|, ...

1
vote

0
answers

26
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 ...

1
vote

0
answers

54
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 ...

1
vote

0
answers

42
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 ...

2
votes

1
answer

168
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 ...

2
votes

1
answer

97
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, $...

2
votes

1
answer

115
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$...

3
votes

1
answer

188
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 ...

6
votes

0
answers

204
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 ...

0
votes

0
answers

76
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
vote

0
answers

36
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

234
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)$ ...

1
vote

1
answer

118
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, ...

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 $\...

4
votes

0
answers

143
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\...

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
votes

0
answers

121
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, ...

1
vote

0
answers

108
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 ...

3
votes

1
answer

154
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 ...

2
votes

1
answer

117
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.)

5
votes

0
answers

218
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 ...

1
vote

0
answers

86
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 ...

2
votes

1
answer

123
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
votes

1
answer

401
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 ...

1
vote

0
answers

57
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 ...

2
votes

1
answer

233
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 $...

2
votes

1
answer

122
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 ...

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}(...

6
votes

0
answers

330
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\...

3
votes

1
answer

182
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 ...

6
votes

1
answer

347
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 ...

0
votes

1
answer

169
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. ...

1
vote

0
answers

380
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 $...

3
votes

1
answer

183
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 ...

8
votes

1
answer

403
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....