I am doing a discrete mathematics course as a graduate student.Our instructor first proved Dilworth's theorem which states that:
Th. Let $P$ be a finite poset. Then the maximum size of an antichain in $P$ is equal to the minimum number of disjoint chains required to cover $P$.
Now he gave a theorem known as Konig-Egervary theorem as an exercise.The statement is as follows:
Th. Let $A$ be a $(0,1)$-matrix.Then the minimum number of lines required to cover all $1$'s in $A$ is equal to the maximum number of $1$'s in $A$ no two of which are on a line.
By line,we mean row or column.Now he told us that we have to use Dilworth's theorem by taking a suitable poset.He also gave us a hint.The hint is as follows:
$x_{ij}=1\iff (i,j)\in P$ and $P$ is equipped with $\leq$ such that $(i_1,j_1)\leq (i_2,j_2)\iff i_1=i_2$ and $j_1\leq j_2$ or $j_1=j_2$ and $i_1\leq i_2$.
But, unfortunately I found that this relation is not transitive on $P$ beccause $(1,1)\leq (1,2)\leq (2,2)$ but $(1,1)\not\leq (2,2)$ if the $(0,1)$-matrix is $A=\begin{pmatrix}1 & 1\\0 & 1\\\end{pmatrix}$.So this hint seems to be of no use.So,what should be the suitable poset $P$ on which we have to apply Dilworth's theorem?