the neighborhoods of vertices in one of the partite sets can be linearly ordered by inclusion. $\hfill$ $\blacksquare$

Note that a threshold graph can be obtained from a threshold bipartite graph by adding all possible edges in one of the partite sets (on either side).

\[bipartited2\] Let $G$ be a bipartite graph with bipartition $(X,Y)$. Given $u,v\in X$, $e(G_{u\to v}) = e(G)$ and $d_2(G_{u\to v})\geq d_2(G)$. If $N(u)\not\subseteq N(v)$ and $N(u) \not\subseteq N(v)$ then $d_2(G_{u\to v}) > d_2(G)$.

Same calculations as in the proof of Lemma \[lem:allcompressed\].

\[bipartitecompress\] Suppose that ${\mathcal{G}}$ is a family of bipartite graphs on a fixed vertex set $V$ with a fixed bipartition $(X,Y)$ such that for any $G'\in{\mathcal{G}}$ and $u,v\in X$ we also have $G'_{u\to v}\in {\mathcal{G}}$. In addition suppose that $G$ satisfies $$d_2(G) = \max\{d_2(G'): G'\in {\mathcal{G}}\}.$$ Then $G$ is bipartite threshold.

Suppose that $u,v\in X$ such that $N_G(u) \not\subseteq N_G(v)$ and $N_G(v) \not\subseteq N_G(u)$. Then $G_{u\to v} \in {\mathcal{G}}$ by assumption and by Lemma \[bipartited2\] $d_2(G_{u\to v}) > d_2(G)$, a contradiction. Thus, $N_G(u) \subseteq N_G(v)$ or $N_G(v) \subseteq N_G(u)$ and so by Lemma \[bipartiteinclusion\] the graph $G$ is threshold bipartite.

Partitions
----------

We can relate threshold bipartite graphs to partitions and matchings in 