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

152 questions
Filter by
Sorted by
Tagged with
1 vote
86 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 ...
52 views

### Lovasz extension and underlying matroid

Let $F \colon 2^V \rightarrow \mathbf{R}$ be a set function for some ground set $V = \{ 1, \dots, n\}$. The domain of $F$ is $\{ 0,1\}^n$ , under the usual identification of a set $S$ with its ...
125 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 ...
93 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.)
163 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
81 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 ...
1 vote
67 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 ...
381 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
49 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 ...
151 views

265 views

92 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 ...
357 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....
105 views

378 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? ...
200 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 vote
162 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 ...
390 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 ...
282 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$ ...
279 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 ...
207 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$)...
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$...