Many 2-level polytopes from matroids

DOI10.1007/S00454-015-9735-5MaRDI QIDQ908212zbMATH OpenOpenAlexFDO

Publication date 3 February 2016

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.2233

2-level polytopes analytic combinatorics asymptotic enumeration matroid theory

Exact enumeration problems, generating functions (05A15) Combinatorial aspects of matroids and geometric lattices (05B35) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Polytopes and polyhedra (52B99)

Abstract: The family of 2-level matroids, that is, matroids whose base polytope is 2-level, has been recently studied and characterized by means of combinatorial properties. 2-level matroids generalize series-parallel graphs, which have been already successfully analyzed from the enumerative perspective. We bring to light some structural properties of 2-level matroids and exploit them for enumerative purposes. Moreover, the counting results are used to show that the number of combinatorially non-equivalent (n-1)-dimensional 2-level polytopes is bounded from below by

c c d o t n^{- 5 / 2} c d o t h o^{- n}

, where

c a p p r o x 0.03791727

and

h o^{- 1} a p p r o x 4.88052854

.

Review text

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\).

Recommendations

On the number of common bases of two matroids

Cites work

Cited in

(4)

This page was built for publication: Many 2-level polytopes from matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q908212)