Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs
提出一种利用晶体学对称性将三角多项式优化转化为多项式优化问题的新方法，通过广义切比雪夫多项式和矩阵不等式松弛计算下界，并应用于估计集合回避图的色数谱界。
Abstract We provide a new approach to the optimization of trigonometric polynomials with crystallographic symmetry. This approach widens the bridge between trigonometric and polynomial optimization. The trigonometric polynomials considered are supported on weight lattices associated to crystallographic root systems and are assumed invariant under the associated reflection group. On one hand the invariance allows us to rewrite the objective function in terms of generalized Chebyshev polynomials of the generalized cosines; On the other hand the generalized cosines parameterize a compact basic semi algebraic set, this latter being given by an explicit polynomial matrix inequality. The initial problem thus boils down to a polynomial optimization problem that is straightforwardly written in terms of generalized Chebyshev polynomials. The minimum is to be computed by a converging sequence of lower bounds as given by a hierarchy of relaxations based on the Hol–Scherer Positivstellensatz and indexed by the weighted degree associated to the root system. This new method for trigonometric optimization was motivated by its application to estimate the spectral bound on the chromatic number of set avoiding graphs. We examine cases of the literature where the avoided set affords crystallographic symmetry. In some cases we obtain new analytic proofs for sharp bounds on the chromatic number while in others we compute new lower bounds numerically.