论文标题
本本植物普遍性和图形设计
Eigenpolytope Universality and Graphical Designs
论文作者
论文摘要
我们表明，图形的本本分层是通用的，因为每个polytope均以仿射等效的形式成为某些阳性加权图的特征分析器。接下来，我们将图形设计的理论扩展到了图形的正交规则，以呈正加权图。通过对多面体的大风二元性，我们显示了图形设计与本征多型的面部之间的两次射击。该培训证明了具有正数重量的图形设计的存在，并且上限是最小图形设计的大小。将这种两者的两者与本本植物的通用性联系起来，我们建立了三个复杂性结果：确定是否要小于提到的上限的图形设计是非常完整的。
We show that the eigenpolytopes of graphs are universal in the sense that every polytope, up to affine equivalence, appears as the eigenpolytope of some positively weighted graph. We next extend the theory of graphical designs, which are quadrature rules for graphs, to positively weighted graphs. Through Gale duality for polytopes, we show a bijection between graphical designs and the faces of eigenpolytopes. This bijection proves the existence of graphical designs with positive quadrature weights, and upper bounds the size of a minimal graphical design. Connecting this bijection with the universality of eigenpolytopes, we establish three complexity results: it is strongly NP-complete to determine if there is a graphical design smaller than the mentioned upper bound, it is NP-hard to find a smallest graphical design, and it is #P-complete to count the number of minimal graphical designs.
