In this document https://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture9.pdf they prove the integrality of the matching polytope using the integrality of the perfect matching polytope.

The only part I don't understand is on page 4-5, when they claim that $\tilde x(\tilde \delta(U)) \geq \tilde x(\tilde \delta(X' \setminus W')) + \tilde x(\tilde \delta(W \setminus X))$. I don't understand why this doesn't hold with equality, since the values on copied edges in the duplicated graph are identical.

Can someone clarify this proof? Is it a mistake?

  • 1
    $\begingroup$ It is my notes that are based on Schrijver's book. You can of course look at Schrijver's book. I don't recall the details now but even if it is an equality the proof goes through, right? $\endgroup$ Jul 20, 2020 at 22:42
  • $\begingroup$ Yes, the proof would go through if it were an equality. In Schrijver's book on pg. 440, he proves the integrality of the matching polytope and states this inequality without proof. So the evidence points to it being an inequality. $\endgroup$ Jul 21, 2020 at 6:20
  • $\begingroup$ I've tried to follow your proof but I can't understand what $\delta(E[A, W \setminus X])$ means. How you can take the delta of a set of edges? $\endgroup$ Jul 21, 2020 at 6:23
  • 1
    $\begingroup$ It is a typo. There should not be a $\delta$ in $\delta(E[A,W\setminus X])$ - it should simply be $E[A,W\setminus X]$ which is the set of edges with one end point in $A$ and the other in $W \setminus X$. $\endgroup$ Jul 23, 2020 at 16:40
  • $\begingroup$ Thank you for clarifying that $\endgroup$ Jul 24, 2020 at 5:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy