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
11
votes
3answers
330 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}(...
5
votes
0answers
260 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\...
2
votes
1answer
102 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 ...
8
votes
1answer
213 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
1answer
107 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
0answers
97 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
1answer
65 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
1answer
317 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....
2
votes
0answers
89 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)...
7
votes
2answers
122 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\...
3
votes
2answers
237 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? ...
3
votes
2answers
149 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
0answers
148 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 ...
6
votes
1answer
336 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 ...
14
votes
1answer
253 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$ ...
4
votes
1answer
210 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 ...
5
votes
1answer
137 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$)...
5
votes
1answer
145 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$...
3
votes
2answers
156 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\...
11
votes
0answers
209 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$. ...
15
votes
3answers
914 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 ...
2
votes
1answer
46 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 ...
11
votes
1answer
329 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 ...
7
votes
1answer
242 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 ...
2
votes
0answers
51 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 ...
5
votes
0answers
168 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]$ ...
4
votes
0answers
82 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 ...
0
votes
0answers
26 views

what kind of functions can be optimized over matroid polytope

We know that we can optimize linear functions over matroid polytope in polynomial time. Is this the only class of functions that can be optimized in polynomial time? Do we have any impossibility ...
5
votes
1answer
346 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....
10
votes
1answer
313 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. ...
2
votes
1answer
136 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 ...
1
vote
0answers
64 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 ...
2
votes
2answers
129 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 ...
4
votes
0answers
221 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 ...
12
votes
2answers
501 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 ...
2
votes
0answers
55 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 ...
0
votes
0answers
82 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 ...
0
votes
1answer
136 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 ...
1
vote
1answer
145 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 ...
1
vote
2answers
176 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 ...
3
votes
0answers
48 views

Matroids which are transitive on minimal basis exchanges

I am looking for matroids in which all minimal basis exchanges look the same, that is, the matroid is transitive on these. Let me explain what I mean by that. Consider a finite matroid $M$. Define a ...
5
votes
0answers
38 views

Disjoint Common Transversals of Two Families of Sets

Let $E$ be a finite set. Let $d,m,n\in\mathbb N$. Let $\mathcal A:=\{A_1,\dots,A_m\}$ and $\mathcal B:=\{B_1,\dots,B_n\}$ be two families of subsets of $E$. A partial transversal of $\mathcal A$ is ...
5
votes
1answer
167 views

Do the Odd Cycles of a Graph Define a Matroid?

An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite. Question: does the collection of "critical" sets of vertices, whose removal renders a ...
5
votes
1answer
215 views

Toggles for non-broken-circuit sets in matroids

Let $M$ be a matroid with ground set $E$. If $t$ is a total order on $E$, and if $S$ is a nonempty subset of $E$, then $\max_t S$ will mean the $t$-largest element of $S$ (that is, the maximum of $S$ ...
1
vote
1answer
911 views

A new generalisation of dimension? part 2

I worked this theory : A new generalization of the dimension? I have a theorem about dimensions which is more general and simple than for matroids. Definition 1: A structure $S$, is a pair $(X, \...
1
vote
0answers
73 views

When does a collection of sets forming a geometric lattice give the flats of a matroid?

Say we have a matroid on a finite set $X$. The collection of its flats forms a geometric lattice under $\subseteq$, where the join is given by intersection. This question is about the converse to ...
6
votes
1answer
238 views

Name of a binary matroid coming from the cycle space of a graph

In some of my recent work, I have 'discovered' a binary matroid which I will describe below. Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...
10
votes
0answers
214 views

Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes: A pure simplicial complex $\Delta$ is the ...
5
votes
1answer
289 views

Greedy simplices in an ultrametric space (generalized Bhargava $p$-orderings)

Let $\left(U, d\right)$ be a finite ultrametric space -- that is, $U$ is a finite set, and $d : U \times U \to \mathbb{R}_{\geq 0}$ is a metric on $U$ such that every $x, y, z \in U$ satisfy $d\left(x,...
6
votes
1answer
244 views

Representability of matroids over finite fields

I have several questions regarding representability of matroids. Question 1. Does there exist a finite matroid that is representable over an infinite field, but is not representable over any finite ...