1
$\begingroup$

I am trying to derive König's theorem from Dilworth's theorem, but it seems like I'm stuck. I know that I have to define some kind of binary relation on the set of a bipartite graph's vertices, then use Dilworth's theorem. However, every relation I've come up with so far either did not satisfy some properties needed for Dilworth's theorem or seemed to be completely useless. Can anyone point me in the right direction?

Thanks.

3 Answers 3

1

Try making $a \geq b$ precisely when $a \in A$ is connected to $b \in B$ in the graph, where $A$ and $B$ are the two parts of the vertex set. What can you make from a chain cover of the resulting poset? What can you make from an antichain? You may have to take some complements...

  • 0
    Yet we can't say that the maximal pairing is always a chain cover for the set: consider a graph in which both partitions contain exactly one element and the elements are not connected at all. Clearly, the maximum pairing's size is 0, yet the set is covered by two chains (each consisting of one element).2011-08-30
1

Dilworth's Theorem relates the size of smallest chain cover to the size of largest antichain. It claims that both the numbers are same. So to use Dilworth's Theorem to derive König's theorem one need to construct a Partially ordered set from the Bipertite graph. You can consider the edges of the bipartite graph as elements of the Partially ordered set (poset). We say two edges are related if they share a common vertices. This yields us the relation R for the poset.

  • Now a matching in bipartite graph is a collection of disjoint edges. It corresponds to an antichain in the poset. Because no two edges are related. Thus maximum matching corresponds to the largest antichain in the poset.
  • We are now left with proving that a chain cover in the poset somehow corresponds to a vertex cover in the Bipertite graph. Consider a chain C in the poset that we created out of bipartite graph. Its elements are edges such that every pair shares a common vertex. In a bipartite graph this is possible only if all the edges of chain share a common vertex(one can prove it using induction on the size of chain). Therefore for every chain we can get a common vertex. Collect all these vertices for every chain in a single set. It is easy to see that this gives us a collection of vertices that cover all the edges; hence it is a vertex cover. Thus the smallest chain cover corresponds to the minimum vertex cover.
  • This completes the proof because according to Dilworth's theorem smallest chain cover has same size as largest antichain. This is same as saying maximum matching and minimum vertex cover has same size.
0

There is a very nice (but hard to find) book by Philip F. Reichmeider, The Equivalence of Some Combinatorial Matching Theorems, which discusses König, Dilworth, Hall, max-flow-min-cut, etc., etc., and would be a great reference for your studies.

  • 0
    @Alon, that's nice. I'm surprised Borgerson gives no re$f$erence to Reichmeider.2011-08-30