On the expansion of combinatorial polytopes

DOI10.1007/3-540-55808-X_4MaRDI QIDQ5096818zbMATH OpenFDO

Authors Milena Mihail

Publication date 18 August 2022

Published in Mathematical Foundations of Computer Science 1992 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-55808-X_4

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Logic programming (68N17) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 2196285
• 0/1-Polytopes. Typical and extremal properties
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid

Cites work

• Adjacency on polymatroids
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating the permanent of graphs with large factors
• Combinatorial applications of an inequality from statistical mechanics
• Eigenvalues and expanders
• Hamiltonicity in (0-1)-polyhedra
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Maximum matching and a polyhedron with 0,1-vertices
• On the Tree Graph of a Matroid
• Pancyclic properties of the graph of some 0-1 polyhedra
• Random generation of combinatorial structures from a uniform distribution
• The Complexity of Enumeration and Reliability Problems
• The dissection of rectangles into squares
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees

Cited in

(10)

• Revlex-initial 0/1-polytopes
• 0/1-Polytopes. Typical and extremal properties
• On Constructing Expanders for Any Number of Vertices
• scientific article; zbMATH DE number 2196285 (Why is no real title available?)
• Expansion of random 0/1 polytopes
• A spectral approach to polytope diameter
• Computing the edge expansion of a graph using semidefinite programming
• On the edge expansion of random polytopes
• Edge expansion of a graph: SDP-based computational strategies
• When is the graph of a random 0/1 polytope a clique?

This page was built for publication: On the expansion of combinatorial polytopes

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