论文标题
关于缔合方案之间的连接以及多面体和阳性半决赛的分析
On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
论文作者
论文摘要
我们探讨了关联方案与半标准编程（SDP）的分析之间的一些联系，该凸的基于lovás-schrijver升降和项目层次结构中组合优化问题的凸松弛。我们对稳定套件的放松的分析导致了一些常规图的集合和稳定数量的界限，让人联想到Delsarte和Hoffman的经典界限，以及深层传播图的概念 - 高度对称的图形 - 我们从某些协会架构中自然而然地显示出我们出现的高度对称图。我们还研究了HyperGraph匹配问题的放松，并确切确定或在这些放松的提升和项目等级上提供边界。我们对这些结果的证明也激发了基于超匹配的均匀相干配置的研究，这是一种关联方案，除了它通常是非共同的。然后，我们说明在这种情况下通过收缩从非共同均匀的相干配置中获得交换次化学的有用性。
We explore some connections between association schemes and the analyses of the semidefinite programming (SDP) based convex relaxations of combinatorial optimization problems in the Lovász--Schrijver lift-and-project hierarchy. Our analysis of the relaxations of the stable set polytope leads to bounds on the clique and stability numbers of some regular graphs reminiscent of classical bounds by Delsarte and Hoffman, as well as the notion of deeply vertex-transitive graphs -- highly symmetric graphs that we show arise naturally from some association schemes. We also study relaxations of the hypergraph matching problem, and determine exactly or provide bounds on the lift-and-project ranks of these relaxations. Our proofs for these results also inspire the study of a homogeneous coherent configuration based on hypermatchings, which is an association scheme except it is generally non-commutative. We then illustrate the usefulness of obtaining commutative subschemes from non-commutative homogeneous coherent configurations via contraction in this context.
