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
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$. ...
J. Allen's user avatar
1 vote
0 answers
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 ...
mijucik's user avatar
  • 187
5 votes
1 answer
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 ...
Nicholas Proudfoot's user avatar
0 votes
0 answers
38 views

Weighted matroid intersection algorithm

From Combinatorial Optimization, Theory and Algorithms, Sixth Edition, 2018, by Bernhard Korte and Jens Vygen: ...
Ray Butterworth's user avatar
4 votes
1 answer
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&...
Sam Hopkins's user avatar
  • 22.9k
4 votes
0 answers
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 ...
John's user avatar
  • 163
1 vote
0 answers
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, ...
user avatar
6 votes
2 answers
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. ...
John's user avatar
  • 163
9 votes
2 answers
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 &...
Wrloord's user avatar
  • 201
0 votes
0 answers
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 ...
user avatar
0 votes
0 answers
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 ...
Tri's user avatar
  • 1,388
3 votes
1 answer
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 ...
M. Winter's user avatar
  • 12.6k
6 votes
2 answers
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,...
Igor Makhlin's user avatar
  • 3,493
1 vote
0 answers
45 views

Minimal matroid of rank r size n

We can define a partial order $\leq$ on loopless matroids, such that $M_1\leq M_2$ if $M_1$ and $M_2$ are on the same groundset and $B_1\subseteq B_2$, where $B_1$ and $B_2$ are the set of bases of $...
Chao Xu's user avatar
  • 583
3 votes
0 answers
68 views

How many linear matroids are transversal

It is known that almost all matroids are not linear matroids (a.k.a. not representable matroids). This was shown by Nelson: arXiv: Almost all matroids are non-representable A transversal matroid is a ...
John Machacek's user avatar
2 votes
0 answers
50 views

Properties of the "girth function" of a matroid

Given an independent set representation of a matroid $M=(E,\mathcal{F})$ its ``rank function'' $r$ defined on the powerset of $E$ is: $$ \forall X \subseteq E, \quad r(X) = \max_{Y \subseteq X}\{|Y|, ...
Felix Goldberg's user avatar
1 vote
0 answers
26 views

Adding columns to a binary matroid to make it graphic

It is well-known that graphic matroids are binary. Now suppose we have a binary non-graphic matroid $M$ with representing matrix $A$ over the field $\mathbb{Z}_2$. Is there a known way to add a small ...
Felix Goldberg's user avatar
1 vote
0 answers
54 views

Are all real-representable matroids binary?

I doubt this is true but I was not able to find a clear answer to the question. Surely this is due to my erratic knowledge of matroid theory. (I know the $U_4^2$-forbidden characterization, but I am ...
Felix Goldberg's user avatar
1 vote
0 answers
42 views

Homology of infinite matroids of finite rank

Bjorner has a great paper about the homology of independence complexes of finite matroids, which is the usual context in matroid theory as far as I understand. However, I've also been told that often ...
xir's user avatar
  • 1,964
2 votes
1 answer
168 views

Is the 3-sum of two graphic matroids a graphic matroid?

A regular matroid is a matroid which is representable over any field. It is a famous theorem of Seymour's that the any regular matroid is obtained by performing 1,2, and 3 sums on graphic, cographic ...
Karagounis Z's user avatar
2 votes
1 answer
97 views

How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?

I am trying to prove a simple local search algorithm could solve exactly this problem: $\underset{S \in I(M), |S|=k}{max} c(S)$ where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $...
Honglian's user avatar
2 votes
1 answer
115 views

Minimum number of matroid circuits containing a fixed element

Let $M$ be a matroid with an $n$-element ground set $E$. I'll assume that $M$ is connected, co-simple (so its dual has no loops or parallel elements) and has no loops. Fix a particular element $e\in E$...
Colin Defant's user avatar
3 votes
1 answer
188 views

Algorithm for finding a minimum weight circuit in a weighted binary matroid

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times. Also for a matroid $M = (E, I)$ one can use the ...
Patrik Pavic's user avatar
6 votes
0 answers
204 views

A Plücker coordinate matroid

Let $V$ be an $n$-dimensional vector space over a field $F$. Let $\mathrm{Gr}(V,d)$ be the set (Grassmann variety) of all $d$-dimensional subspaces of $V$. We can regard $\mathrm{Gr}(V,d)$ as a subset ...
Richard Stanley's user avatar
0 votes
0 answers
76 views

Topology of independence set of a vector space

This seems like something that would have a well-known treatment somewhere, but I'm not sure where to look. If we have a vector space $V$ (or maybe even a module), we can consider an abstract ...
xir's user avatar
  • 1,964
1 vote
0 answers
36 views

Associating a matroid to a uniform hypergraph

For a fixed ground set $[n]=\{1,\ldots,n\}$, and for any matroid $M$ on $[n]$, specified as a collection of bases $B_M$, the corresponding matroid basis polytope $P_M$ is defined to be the convex hull ...
The Discrete Guy's user avatar
3 votes
1 answer
234 views

When Alexander dual of a simplicial complex is a matroid?

Let $C$ be a simplicial complex on a finite set $V$: that means $C$ is a collection of subsets of $V$ such that if $\sigma\in C$ and $\tau\subseteq \sigma$, then $\tau\in C$. The Alexander dual $D(C)$ ...
Connor's user avatar
  • 251
1 vote
1 answer
118 views

Connectivity of a matroid is at least its rank?

The connectivity $\eta(X)$ of a simplicial complex $X$ is defined as the $$1+\min_j\{j \mid \tilde{H}_j(X)\neq 0\}.$$ If no such $j$ exists, then $\eta(X):=\infty$. (See here for this definition, ...
Connor's user avatar
  • 251
6 votes
1 answer
293 views

Distributive lattice of subspaces

Let $V$ be a finite dimensional vector space. Let $\Lambda$ be a collection of subspaces of $V$ such that, if $X$ and $Y$ are in $\Lambda$, then $X\cap Y$ and $X+Y$ are in $\Lambda$. This makes $\...
David E Speyer's user avatar
4 votes
0 answers
143 views

Rowmotion of matroids

If $Z$ is a finite poset, then we say that a collection $\mathcal{A}$ is an antichain if whenever $y,z\in\mathcal{A}$, if $y\leq z$, then $y=z$. If $R\subseteq Z$, then let $L(R)$ be the set of all $x\...
Joseph Van Name's user avatar
14 votes
5 answers
809 views

Birkhoff's representation theorem vs matroid-geometric lattice correspondence

This question is motivated by the superficial observation that Birkhoff's representation theorem and the cryptomorphism between matroids and geometric lattices are sort of similar. The former says ...
Igor Makhlin's user avatar
  • 3,493
3 votes
0 answers
121 views

Matroid of monomials of linear forms

Consider the linear matroid $M(k, d)$ on the monomials of degree $d$ in $k$ general linear forms $L_1, \ldots, L_k$ in two variables, over $\mathbb{C}$. For simplicity take $k=3$ and the forms $X, Y, ...
Jake Levinson's user avatar
1 vote
0 answers
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 ...
Shahab's user avatar
  • 433
3 votes
1 answer
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 ...
Shahab's user avatar
  • 433
2 votes
1 answer
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.)
Shahab's user avatar
  • 433
5 votes
0 answers
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 ...
Shahab's user avatar
  • 433
1 vote
0 answers
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 ...
Scibee's user avatar
  • 33
2 votes
1 answer
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 ...
Hans's user avatar
  • 2,883
2 votes
1 answer
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 ...
Shahab's user avatar
  • 433
1 vote
0 answers
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 ...
Karagounis Z's user avatar
2 votes
1 answer
233 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 $...
Joe Boninger's user avatar
2 votes
1 answer
122 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 ...
Felipe Voloch's user avatar
15 votes
3 answers
782 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.9k
6 votes
0 answers
330 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\...
Ethan Splaver's user avatar
3 votes
1 answer
182 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 ...
Tobias Windisch's user avatar
6 votes
1 answer
347 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 ...
Ben's user avatar
  • 1,010
0 votes
1 answer
169 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. ...
Ingrid maria's user avatar
1 vote
0 answers
380 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 $...
Ingrid maria's user avatar
3 votes
1 answer
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 ...
Jukka Kohonen's user avatar
8 votes
1 answer
403 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....
Asvin's user avatar
  • 7,646