# 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
Filter by
Sorted by
Tagged with
1 vote
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$. ...
• 11
1 vote
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 ...
• 187
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 ...
• 2,527
38 views

### Weighted matroid intersection algorithm

From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen: ...
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&...
• 22.9k
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 ...
• 163
1 vote
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, ...
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. ...
• 163
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
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 ...
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 ...
• 1,388
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 ...
• 12.6k
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,...
• 3,493
1 vote
45 views

• 151k
143 views

1 vote
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 ...
• 433
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 ...
• 433
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.)
• 433
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 ...
• 433
1 vote
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 ...
• 33
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,883
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 ...
• 433
1 vote
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 ...
• 153
233 views

• 22.9k
330 views

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 ...
• 3,964