Caltech Logo

Discrete Analysis Seminar

Tuesday, January 31, 2023
3:00pm to 4:00pm
Add to Cal
Linde Hall 187
Structure and Complexity of Graphical Designs for Weighted Graphs through Eigenpolytopes
Catherine Babecki, Department of Mathematics, University of Washington,

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.

For more information, please contact Math Department by phone at 626-395-4335 or by email at [email protected].