Eigenpolytope Universality and Graphical Designs
From MaRDI portal
complexityeigenpolytopesgale dualitygraph Laplaciangraph samplinggraphical designspolytopesquadrature rules
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Gale and other diagrams (52B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Abstract computational complexity for mathematical programming problems (90C60)
Abstract: We extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show that there is a bijection between graphical designs and the faces of eigenpolytopes associated to the graph. This bijection proves the existence of graphical designs with positive quadrature weights, and upper bounds the size of a graphical design. We further show that any combinatorial polytope appears as the eigenpolytope of a positively weighted graph. Through this universality, we establish two complexity results for graphical designs: it is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, and it is #P-complete to count the number of minimal graphical designs.
Recommendations
Cites work
- A new polynomial-time algorithm for linear programming
- Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron.
- Codes, cubes, and graphical designs
- Convex Polytopes
- Eigenpolytopes of Distance Regular Graphs
- Generalized designs on graphs: Sampling, spectra, symmetries
- Geometric algorithms and combinatorial optimization
- Graphical designs and extremal combinatorics
- Graphical designs and gale duality
- Hard Enumeration Problems in Geometry and Combinatorics
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 6016068 (Why is no real title available?)
- scientific article; zbMATH DE number 3121295 (Why is no real title available?)
- scientific article; zbMATH DE number 4089320 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1303522 (Why is no real title available?)
- scientific article; zbMATH DE number 1054726 (Why is no real title available?)
- scientific article; zbMATH DE number 1961535 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Iterative methods in combinatorial optimization.
- Lectures on Polytopes
- On the Complexity of Computing the Volume of a Polyhedron
- On the null space of a Colin de Verdière matrix
- Some NP-complete problems in linear programming
- Stable high-order quadrature rules with equidistant points
- Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
- The Colin de Verdière number and graphs of polytopes
- The Complexity of Vertex Enumeration Methods
Cited in
(4)
This page was built for publication: Eigenpolytope Universality and Graphical Designs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6195955)
