Codegree and regularity of stable set polytopes

The codegree <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">codeg</mml:mi> <mml:mo>(</mml:mo> <mml:mi>𝒫</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> of a lattice polytope <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>𝒫</mml:mi> </mml:math> is a fundamental invariant in discrete geometry. In the present paper, we investigate the codegree of the stable set polytope <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>𝒫</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:math> associated with a simple graph <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> . Specifically, we establish the inequalities <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="block"> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi mathvariant="normal">codeg</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>𝒫</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:mi>χ</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> </mml:mrow> </mml:math> where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>χ</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> denote the clique number and the chromatic number of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> , respectively. Furthermore, an explicit formula for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi mathvariant="normal">codeg</mml:mi> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>𝒫</mml:mi> <mml:mi>G</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is given when <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>G</mml:mi> </mml:math> is either a line graph or an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>h</mml:mi> </mml:math> -perfect graph. Finally, as an application of these results, we provide upper and lower bounds on the regularity of the toric ring associated with <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>𝒫</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:math> .