Many 2-level polytopes from matroids (Q908212)

This paper studies 2-level matroids in terms of UMR trees. The authors recall that all 2-level matroids can be written in terms of direct and 2-sums of uniform matroids, and use this to construct UMR trees. The aim of the paper is to use the combinatorial structures of these UMR trees to enumerate inequivalent 2-level polytopes, which are exactly the polytopes defined by 2-level matroids. A uniform matroid of rank \(k\) with a ground set of size \(n\) is written \(U_{n, k} \). In this notation, two special cases of uniform matroids are given: \(\mathcal M _n = U _{n, 1}\) and \(\mathcal R_ n = U_{n, n-1} \). Both of these are graphical matroids: \(\mathcal M _n\) corresponds to the multigraph on two vertices and \(n\) edges, and \(\mathcal R_ n\) corresponds to the one with \(n\) edges and \(n\) vertices. A UMR tree associated to a 2-level matroid \(\mathcal M\) is the decomposition of \(\mathcal M\) into its 2-connected uniform components. Each vertex of the tree is labeled by an \(\mathcal M_n\) type matroid (corresponding to the M in the acronym), an \(\mathcal R _n\) type matroid (corresponding to the R in the acronym), or a different uniform matroid \(U_{n,k}\) with \( n \geq 4\); \(2 \leq k \leq n - 2\) (corresponding to the U in the acronym). The authors go on to recall generating functions associated to multisets and the analytic structures of the same. They also recall the dissymmetry theorem for trees, which relates the combinatorial classes of trees to these generating functions. They show that there is an isomorphism between the set of (isomorphism classes of) 2-connected, 2-level matroids (and thus, inequivalent 2-level polytopes) and UMR trees, robust under certain permutations on the ground set. As the UMR trees lend themselves more easily to counting, by the dissymmetry theorem, the authors use this structure to enumerate the 2-level polytope. Namely, they present an algorithm for decomposing pointed UMR trees and calculate generating functions associated to the decomposed trees, corresponding to the \(U\), \(M\), and \(R\) vertices. In this manner, the authors come up with a lower bound for the number of 2-matroids of size \((n - 1)\): \(c \cdots n^{-5/2} \cdots \rho-n\), where \(c \approx 0.03791727\) and \(\rho -1 \approx 4.88052854\).