taserghar's blog

Dilworth Theorem
By taserghar, 13 years ago, In English
Please someone give me the clear idea about dilworth theorem for graph or DAG. I read about it in multiple places but more I am reading getting more confusing. So please someone help me to understand it properly.
Thanks in advance.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
http://en.wikipedia.org/wiki/Dilworth%27s_theorem
Applicated to a DAG, it says that we can find divide the set of vertices into subsets V1, ..., Vk, so that any two vertices in any subset are reachable one from another (in one direction, of course), and then choose , so that none of vi are reachable from any other.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    actually I read it but since I am a beginner I am bit confused about that. But I got that "for any partial order set, minimum number of chain need to cover the set is SIZE of the biggest anti-chain". Is that correct... ?
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
someone please explain how dilworth related to bipertite matching for graph problem...

→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    There is one-to-one correspondence between chain covers and bipartite matchings. If in a bipartite matching a vertex is not matched to any other then this vertex is a start of some chain, because there is no edge that comes to that vertex. Hence power of cover set equals to number of unmatched vertices. The more bipartite matching size is the less is the number of unmatched vertices and |Chain Cover Set| = |V| - |Max Bipartite Matching|.
    → Reply