19
votes
Have you seen my matroid?
One can use Whitney's theorem to show that the characteristic polynomial is
$$ \sum_{i=0}^k{n\choose i}q^{k-i}(q-2)^{n-i} +
\sum_{i=k+1}^n{n\choose i}(q-2)^{n-i}. $$
I doubt that this can be ...
- 50.8k
17
votes
Accepted
Is matroid realizability computable?
Contra my suspicions, the Internet is telling me that Vámos proved in "A necessary and sufficient condition for a matroid to be linear" (citation below) that it is decidable if a matroid is ...
- 24.2k
15
votes
Accepted
Have you seen my matroid?
Let $U$ be the uniform matroid of rank $k$ on $n$. Since $U$ is orientable one can consider the Lawrence oriented matroid $\Lambda(U)$ associated with any orientation of $U$ (the Lawrence construction ...
- 984
15
votes
Why do combinatorial abstractions of geometric objects behave so well?
Perhaps this, for now, is more an issue of perspective. Yes, for matroids, spheres and Coxeter groups the realizable cases were known before using results in algebraic geometry, but this is natural as ...
- 732
12
votes
A new generalisation of dimension? part 2
Let me try to situate your definition in context.
A closure operator on a set $X$ is a function $\text{cl}\colon \mathcal{P}(X)\to \mathcal{P}(X)$ such that for all $A,B\subseteq X$, we have:
$A\...
- 5,031
12
votes
Accepted
Does the basis graph of a matroid determine it?
I think this question is answered in the paper A Graphical Representation of Matroids by C. A. Holzmann, P. G. Norton, and M. D. Tobey. From the abstract:
"A base graph of a matroid is the graph ...
- 7,875
12
votes
Accepted
Is there Matrix-Tree theorem for counting the bases of a connected matroid?
A broader class of matroids for which you have a Matrix Tree theorem are the regular matroids (those representable over every field): see, e.g., https://arxiv.org/abs/1404.3876.
EDIT: Let me actually ...
- 24.2k
10
votes
Why do combinatorial abstractions of geometric objects behave so well?
As Uri Bader remarked one has to be careful with the term "combinatorial abstraction". In the cases mentioned by Sam and in other cases the geometric objects are certain algebraic varieties but the ...
- 24.7k
10
votes
Is matroid realizability computable?
Sam Hopkins has answered what I think is your stated question. But in the comments, it seems that you're also interested in the following question: Given a matroid $M$ and field $F$, is it decidable ...
- 82.6k
10
votes
Accepted
Log-concavity of matroids: characterization of equality?
I think the following shows it's never possible for there to be equality.
Indeed, Ardila-Denham-Huh https://arxiv.org/abs/2004.13116 recently showed for any matroid $M$ that $T_M(x,0)$ has log-concave ...
- 783
9
votes
Why do combinatorial abstractions of geometric objects behave so well?
I'm not exactly addressing your question about combinatorial abstractions of geometric objects, but you seem to be taking Lie theory as a given natural geometric arena.
On the contrary, the ...
- 3,020
9
votes
Accepted
Prescribing the dimension of intersections of sub-vector spaces
I find this easier to think about if we dualize everything: replace $d(S)$ with $\dim V - d(S)$ and each subspace with its annihilator in $V'$. Recall that the annihilator of a sum is the intersection ...
- 9,617
9
votes
Does the basis graph of a matroid determine it?
Let $M$ be the matroid corresponding to the cycle graph $C_3$ with edges $\{a,b,c\}$, so that the bases of $M$ are $\{a,b\}$, $\{a,b\}$, $\{b,c\}$; let $M'$ be the matroid corresponding to the ...
- 24.2k
8
votes
Accepted
Representability of matroids over finite fields
The main results of Rado's Note on Independence Functions settle all three questions. The first few lines of Effective Versions of Two Theorems of Rado give a perfect recap of those results, so here ...
- 984
8
votes
Another characterization of matroids
Yes though this is commonly stated using clutters and their associated minors, (identify your ASC with its clutter of facets) basically you're describing a forbidden minor characterization of a ...
- 2,506
7
votes
Accepted
A transversal matroid whose dual is not transversal
Consider the rank-$4$ transversal matroid, $M$, shown in the diagram below. The figure on the left shows a presentation of $M$ via a bipartite graph. The ground set of $M$ is $\{a,b,c,d,e,f\}$. The ...
- 500
7
votes
Accepted
Minimum number of independent pairs in a matroid
As observed by Geva Yashfe, the answer is $2^n$. This can be achieved when each of $A$ and $\overline{A}:=E\setminus A$ are bases, with $A = \{a_1,\ldots,a_n\}$, $\overline{A} = \{b_1,\ldots,b_n\}$, ...
- 32.1k
7
votes
Log-concavity of matroids: characterization of equality?
I have nothing to add to Hunter's answer to your main question, but I thought it might be helpful to comment more generally on where the difficulty lies in extracting such information from a Kähler ...
7
votes
Accepted
Birkhoff's representation theorem vs matroid-geometric lattice correspondence
Antimatroids
are a good example. We have the syllogism "Antimatroids are to
matroids as join-distributive lattices are to geometric lattices."
Two other examples are the characterizations of ...
- 50.8k
7
votes
Accepted
Distributive lattice of subspaces
Just to not leave this open, a proof can be found in Proposition 7.1 of Chapter 1 of Quadratic Algebras by Alexander Polishchuk and Leonid Positselski as alluded to by Mariano on MSE https://math....
- 38.6k
7
votes
"Minimal" connected matroids
I think you want Theorem 2.1 On the Ehrhart Polynomial of Minimal Matroids
by Ferroni. Note Theorem 2.1 cites previous work that may be of interest, but I know of these matroids from this recent ...
- 7,875
7
votes
Accepted
Number of binary matroids of rank $r$ on a ground set with $n$ elements
You can compute these numbers for small $n$ and $r$ using Pólya's Enumeration Theorem (which is just a specific application of the orbit-stabiliser theorem).
A simple binary matroid of rank at most $r$...
- 12.7k
6
votes
Matroids of rank two
Up to simplification (suppressing loops and parallel elements), every rank two matroid is just a rank two uniform matroid.
Note that the vectors $(1, a_1), \dots, (1, a_n)$ represent the uniform ...
- 32.1k
6
votes
What upper bounds are known on the number of non-isomorphic cycle matroids?
There are $2^{\binom{n}{2}}$ labelled graphs on $n$ vertices. Since isomorphic graphs have isomorphic graphic matroids, $c_n$ is at most the number of non-isomorphic graphs on $n$ vertices (see OEIS ...
- 32.1k
6
votes
Category theoretic interpretation of matroids?
The following related article was recently published:
Heunen, C. & Patta, V., The Category of Matroids, Appl Categor Struct (2018) 26: 205. https://doi.org/10.1007/s10485-017-9490-2
In section 9, ...
- 13.6k
6
votes
Accepted
Does the purported proof of Rota's conjecture provide an algorithm for calculating the forbidden minors of matroids over arbitrary finite fields?
As far as I understand, the purported proof does not give an algorithm that given a finite field $\mathbb{F}$, computes the excluded minors for $\mathbb{F}$-representability. This is because it ...
- 32.1k
6
votes
Constructing a $0/1$ polytope from an abstract simplicial complex
For a graph $G$, the stable set polytope $\mathcal{P}(G)$ is the polytope which is the convex hull of the indicator functions of stable (i.e., independent) sets of $G$. Since the stable sets are a ...
- 24.2k
6
votes
Birkhoff's representation theorem vs matroid-geometric lattice correspondence
In their recent papert "The fundamental theorem of finite semidistributive lattices" (https://doi.org/10.1007/s00029-021-00656-z and https://arxiv.org/abs/1907.08050) Reading, Speyer, and ...
- 24.2k
6
votes
Accepted
Book for matroid polytopes
You might like the book Coxeter Matroids by Borovik, Gelfand, and White.
In some sense, this book is actually about generalizations of matroids. One generalization is from matroids to flag matroids (...
- 7,875
6
votes
Book for matroid polytopes
Matroid polytopes are a standard topic in the field of combinatorial optimization, and as such I would recommend the beautiful text Combinatorial Optimization - Polyhedra and Efficiency by Lex ...
- 32.1k
Only top scored, non community-wiki answers of a minimum length are eligible