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
    I see your point. If we prove that an antichain is a vertex cover and a chain cover is a pairing, then we can show that |min.vertex cover| <= |max.pairing|. The opposite is obvious, thus |min.vertex cover| = |max.pairing|. There seems to be a problem, though: it's not always possible to construct a pairing that covers the entire set of vertices: consider a bipartite graph with parts A and B where |A| = 1 and |B| = 5, the size of the max. pairing is 1. The chain cover, however needs to cover the entire set of vertices. So its sort of problematic to prove that a chain cover is always a pairing.2011-08-29
  • 0
    That's why I gave the hint about complements... What can you say about the set of vertices that are *not* in a maximal antichain?2011-08-29
  • 0
    They are all connected to at least one element in the max. anticahin, which means the max. antichain is also a vertex cover of the graph.2011-08-30
  • 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.

  • 2
    http://www.robertborgersen.info/Presentations/GS-05R-1.pdf2011-08-30
  • 0
    @Alon, that's nice. I'm surprised Borgerson gives no reference to Reichmeider.2011-08-30