USA TSTST

Suppose $|S|\ge 2$. For any $p\in S$, let $R(p)$ denote the stable rectangle with upper-right corner $p$. We say such $p$ is pivotal if $p+(1,1)\notin S$ and $|R(p)|$ is even.

Claim — If $|S|\ge 2$, then a pivotal $p$ always exists. Proof. Consider the top row of $S$. If it has length at least 2, one of the two rightmost points in it is pivotal. Otherwise, the top row has length 1. Now either the top point or the point below it (which exists as $|S|\ge 2$) is pivotal. $\square$ We describe how to complete the induction, given some pivotal $p\in S$. There is a partition $$S=R(p)\bigsqcup S_1\bigsqcup S_2$$ where $S_1$ and $S_2$ are the sets of points in $S$ above and to the right of $p$ (possibly empty). Claim — The desired inequality holds for stable subsets containing $p$. Proof. Let $E_1$ denote the number of even stable subsets of $S_1$; denote $E_2$, $O_1$, $O_2$ analogously. The stable subsets containing $p$ are exactly $R(p)\bigsqcup T_1\bigsqcup T_2$, where $T_1\subseteq S_1$ and $T_2\subseteq S_2$ are stable. Since $|R(p)|$ is even, exactly $E_1{E}_2+O_1{O}_2$ stable subsets containing $p$ are even, and exactly $E_1{O}_2+E_2{O}_1$ are odd. As $E_1\ge O_1$ and $E_2\ge O_2$ by inductive hypothesis, we obtain $E_1{E}_2+O_1{O}_2\ge E_1{O}_2+E_2{O}_1$ as desired. $\square$ By the inductive hypothesis, the desired inequality also holds for stable subsets not containing $p$, so we are done.