Sum-of-squares rank upper bounds for matching problems

The matching problem is one of the most studied combinatorial optimization problems in the context of extended formulations and convex relaxations. In this paper we provide upper bounds for the rank of the sum-of-squares/Lasserre hierarchy for a family of matching problems. In particular, we show that when the problem formulation is strengthened by incorporating the objective function in the constraints, the hierarchy requires at most ⌈ k2⌉ levels to refute the existence of a perfect matchingin an odd clique of size 2k + 1.