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.

Filter by
Sorted by
Tagged with
101 votes
3 answers
6k views

Why do combinatorial abstractions of geometric objects behave so well?

This question is inspired by a talk of June Huh from the recent "Current Developments in Mathematics" conference. Here are two examples of the kind of combinatorial abstractions of geometric ...
Sam Hopkins's user avatar
  • 22.7k
6 votes
2 answers
771 views

Number of bases of a matroid

I would like to know the minimum number of bases of a matroid of rank $k$ and $n$ elements, knowing that each singleton is independent. At least for small ranks.
Quentin Fortier's user avatar
15 votes
3 answers
777 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}(...
Sam Hopkins's user avatar
  • 22.7k
12 votes
3 answers
2k views

Representability of matroids over $\mathbb R$

Let $M$ be a matroid, for example viewed as being given by a finite set $X$ and a rank function $d : P(X) \to {\mathbb N}$ such that 1) $d(\varnothing)=0$, $d(\lbrace x \rbrace)=1$, for all $x \in X$,...
Andreas Thom's user avatar
  • 25.3k
9 votes
3 answers
800 views

When is "metric dimension" well defined?

A subset $B$ of a metric space $(M,d)$ is called a metric generating set if and only if $$[\forall b \in B, d(x,b)=d(y,b)] \implies x = y \,. $$ A metric generating set $B$ is called a metric basis ...
Chill2Macht's user avatar
  • 2,622
7 votes
1 answer
433 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 ...
Student's user avatar
  • 5,008
6 votes
2 answers
515 views

Finding the matroids with a specified set of non-bases

I'm a grad student in algebraic geometry, and I've encountered a problem which requires me to produce an algorithm involving matroids. Since this isn't my area of expertise, I'm hoping someone knows ...
Nicolas Ford's user avatar
  • 1,520
6 votes
2 answers
239 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,...
Igor Makhlin's user avatar
  • 3,493
4 votes
0 answers
195 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 ...
John's user avatar
  • 161
3 votes
2 answers
211 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\...
Ethan Splaver's user avatar