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 rank $r$ uniformly in a ground set of size $n$?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
The paper Enumerating Matroids of Fixed Rank by Pendavingh and van der Pol will probably be of interest to you. Although it does not address the question of rapid mixing, I suspect that the methods they use to obtain their bounds on the number of matroids of fixed rank $r$ on an $n$ element set can be transformed into fast sampling algorithms. Their work relies on the classic result of Knuth that you already mentioned, together with some new ideas. In particular, they prove that every matroid $M$ can be reconstructed from $n$, $r$, and a certain antichain $\mathcal{V}(M)$.
answered Feb 23, 2021 at 1:01
-
1$\begingroup$ If I recall, Pendavingh and van der Pol use estimations based on entropy-based probabilistic methods. I can't see how this may lead to a way to randomly generate matroids $\endgroup$ Commented Feb 23, 2021 at 19:09