Many 2-level polytopes from matroids

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

Authors Francesco Grande, Juanjo Rué

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

zbMATH Keywords

asymptotic enumerationmatroid theoryanalytic combinatorics2-level polytopes

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) (52B40) Combinatorial aspects of matroids and geometric lattices (05B35) 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 $ccdot{n}^{-5/2}cdoth{o}^{-n}$, where $capprox0.03791727$ and $h{o}^{-1}approx4.88052854$.

Recommendations

• On the number of common bases of two matroids

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 1111371 (Why is no real title available?)
• scientific article; zbMATH DE number 1538119 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• A Combinatorial Decomposition Theory
• Analytic combinatorics
• Asymptotic study of subcritical graph classes
• Combinatorial geometries, convex polyhedra, and Schubert cells
• Compressed polytopes and statistical disclosure limitation
• Constructions for projectively unique polytopes
• Coxeter matroids. With illustrations by Anna Borovik
• Enumeration and limit laws for series-parallel graphs
• Face numbers of centrally symmetric polytopes produced from Split graphs
• Geometric algorithms and combinatorial optimization.
• Graph theory. Foreword by Crispin St. J. A. Nash-Williams.
• Intersections of translates of convex bodies
• On Kalai's conjectures concerning centrally symmetric polytopes
• On a certain class of polytopes associated with independence systems.
• Random Trees
• Singularity Analysis of Generating Functions
• Sums of squares, moment matrices and optimization over polynomials
• Theory of Matroids
• Theta bodies for polynomial ideals
• Theta rank, levelness, and matroid minors
• Triangulations. Structures for algorithms and applications
• Two poset polytopes

Cited in

(4)

• Two-level polytopes with a prescribed facet
• Rank 2 affine MV polytopes
• Bounds on the number of 2-level polytopes, cones, and configurations
• Binary scalar products

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)