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
1 vote
0 answers
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 ...
user avatar
  • 359
0 votes
0 answers
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 ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 359
2 votes
1 answer
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.)
user avatar
  • 359
4 votes
0 answers
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 ...
user avatar
  • 359
1 vote
0 answers
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 ...
user avatar
  • 33
1 vote
1 answer
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 ...
user avatar
  • 2,277
2 votes
1 answer
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 ...
user avatar
  • 359
1 vote
0 answers
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 ...
user avatar
2 votes
1 answer
151 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 $...
user avatar
2 votes
1 answer
101 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 ...
user avatar
14 votes
3 answers
531 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}(...
user avatar
  • 18.8k
5 votes
0 answers
265 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\...
user avatar
  • 2,371
2 votes
1 answer
115 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 ...
user avatar
6 votes
1 answer
273 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 ...
user avatar
  • 874
0 votes
1 answer
118 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. ...
user avatar
1 vote
0 answers
181 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 $...
user avatar
3 votes
1 answer
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 ...
user avatar
8 votes
1 answer
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....
user avatar
  • 6,834
2 votes
0 answers
105 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)...
user avatar
7 votes
2 answers
149 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\...
user avatar
  • 1,716
3 votes
2 answers
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? ...
user avatar
3 votes
2 answers
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 ...
user avatar
  • 1,716
1 vote
0 answers
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 ...
user avatar
6 votes
1 answer
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 ...
user avatar
  • 2,371
14 votes
1 answer
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$ ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 2,371
5 votes
1 answer
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$)...
user avatar
5 votes
1 answer
153 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$...
user avatar
  • 143
3 votes
2 answers
176 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\...
user avatar
  • 2,371
11 votes
0 answers
219 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$. ...
user avatar
15 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 ...
user avatar
2 votes
1 answer
48 views

Extending spanning sets on contractions of matroids

Suppose you have a matroid, and $T$ is a subset of a spanning set $S$. Now consider the contraction of the matroid to the set $T$ and suppose $X$ is a spanning subset of $T$ with respect to that ...
user avatar
  • 1,064
11 votes
1 answer
420 views

Is there Matrix-Tree theorem for counting the bases of a connected matroid?

The famous Kirchhoff's Matrix-Tree theorem counts the number of spanning trees of a connected graph, that is, the number of bases of its cycle matroid. But it appeals to vertices, that's why I do not ...
user avatar
  • 86.9k
7 votes
1 answer
312 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 ...
user avatar
  • 4,005
2 votes
0 answers
54 views

The best way for obtaining the canonical label of a matroid?

For a graph, we can canonical labelings with Nauty or other methods. But for a matroid, I do not find an easy way to labeling. Dillon Mayhewa, Gordon F. Royle introduced the hyperplane graph of a ...
user avatar
  • 41
5 votes
0 answers
182 views

Set-theoretic generation by circuit polynomials

Let $P$ be a prime ideal in $S=\mathbb{C}[x_1,\ldots , x_n],$ and write $[n] = \{ 1, \ldots , n \}.$ The algebraic matroid of $P$ can be defined according to circuit axioms as follows: $C\subset [n]$ ...
user avatar
  • 368
4 votes
0 answers
93 views

Maximal number of smallest circuits in a matroid

It is known (see here for example) that, in a simple graph of odd genus $g$ with $n$ vertices and $m$ edges, the number of cycles of lenght $g$ is at most $\frac{n(m-n+1)}{g}$. Since this can be be ...
user avatar
5 votes
1 answer
407 views

Extending submodular functions from a sublattice

This came about when I was studying the connection between matroids and strong greedoids, but it has broken through into a subject I am not particularly familiar with: submodular functions on lattices....
user avatar
10 votes
1 answer
346 views

Poset-troids …?

In many respects, spanning tree : graph :: linear extension : poset For instance, the number of spanning trees/linear extensions is a measure of the "richness" or "complexity" of the graph/poset. ...
user avatar
  • 18.8k
2 votes
1 answer
140 views

Upper-bounding $\dim \text{span}\{v_1,\dots,v_n\}$ in terms of $\dim \text{span}$ of subsets

I asked this question on Stack Exchange two weeks ago, and didn't get any answers, so I'm shamelessly reposting it here. Let $S=\{v_1,\dots, v_n\} \subset V$ be a set of nonzero vectors in a vector ...
user avatar
  • 874
1 vote
0 answers
97 views

Matroids with no relaxations (~ weak maps)

There's an operation in matroid theory which is called "relaxation". To keep things simple, let's consider a matroid $M$ with set of bases $\mathcal{B}$. If $M$ has a subset $H$ of $M$ that is both ...
user avatar
  • 1,716
2 votes
2 answers
196 views

How to generating all flats of the cycle matroid of a graph?

If $M$ is a matroid, I can use M.flats(k) in SageMath to list all the flats of rank $k$. But I hope that there is an algorithm or program to list all flats of the cycle matroid of a graph. And do not ...
user avatar
  • 41
4 votes
0 answers
242 views

Understanding this example of projective geometry in Algebraic matroids

In this paper by Evans and Hrushovski: Projective planes in algebraically closed fields, they characterize projective planes in algebraically closed fields. These are coordinated by the skew-fields ...
user avatar
  • 397
13 votes
2 answers
590 views

Does the basis graph of a matroid determine it?

Let $M$ be a matroid with set of basis $\mathcal{B}$. The basis graph of $M$ is a graph with set of vertices $\mathcal{B}$ and edges $(B,B')$ always that $B$ and $B'$ differ (as sets) by exactly one ...
user avatar
  • 1,716
2 votes
0 answers
58 views

Reference request: Matroid cryptomorphisms for arbitrary monomial ideals

For a matroid $M$ let $C$ be the circuit ideal of $M$, that is, the Stanley-Reisner ideal of independence complex of $M$. Then there are simple ideal-theoretic operations that take $C$ to the facet ...
user avatar
0 votes
0 answers
116 views

Paths in graphs as a vector space or matroid

If I have a simple graph $G$, and what to count the number of simple paths between two distinct vertices, can the paths be seen as independent sets of a vector space, or even somehow, a matroid? I ...
user avatar
  • 466
1 vote
1 answer
147 views

How to find all minimal dependent sets of a set of vectors effectively?

In my research, I need to find the set of all minimal dependent sets of a given set of vectors. One method is to check every subset of the given set. But this method is very slow when the set of ...
user avatar
  • 5,865
1 vote
1 answer
160 views

From Steiner systems to geometric lattices to matroids

I am looking for a specific matroid. I found a source that claimed to discuss these matroids, but then, only discusses geometric lattice. Even more, in that paper, the geometric lattice that seems to ...
user avatar
  • 9,471
1 vote
2 answers
199 views

Mapping of subcubes of a $(d+k)$-hypercube onto subcubes of a $d$-hypercube

Denote by $Q_n$ the $n$-dimensional hypercube. A vertex of $Q_n$ is represented by a vector of $n$ $\{0,1\}$-bits. An edge corresponding to two vertices whose vectors differ in one coordinate is ...
user avatar