6
$\begingroup$

An excercise says "deduce Konig's Theorem on bipartite graphs from Dilworth's theorem on posets".

Let G be a bipartite graph, G=(A,B). Order the edges left to right. A maximum antichain is a largest independent set in the graph.

I can see a maximum antichain must have every vertex in G incident with it. But it doesn't follow that every edge is incident with it. That may not be true.

So how does one proceed?

$\endgroup$
1
  • 1
    $\begingroup$ There's a little book by Reichmeider that goes into this and related matters in great detail. Unfortunately, the book is long out of print, but some libraries have it. $\endgroup$ Aug 10, 2013 at 6:15

2 Answers 2

4
$\begingroup$

Create a poset by setting $a \le b$ for every $a \in A$ and $b \in B$ such that $ab \in E(G)$. Let any two elements in $A$ or $B$ be incomparable. In other words, orient each edge so that it goes from $A$ to $B$ and make a partial order based off of this orientation.

Dilworth's Theorem: the minimum cardinality of a collection of chains with union $G$ is the maximum cardinality of an antichain.

Recall that each chain must include $1$ or $2$ members, and we want as many chains with $2$ members as possible. Thus a minimum collection of chains with union $G$ contains a maximum matching and any leftover vertices.

An antichain here is the complement of a vertex cover. It contains no edges, so its complement must meet all edges. Making an antichain maximum makes the vertex cover a minimum.

The rest is just arithmetic.

$\endgroup$
0
$\begingroup$

View any n-node bipartite graph G as a bipartite poset. The nodes of one part are maximal elements, and nodes of the other part are minimal. Every vertex disjoint path covering of the poset of size n-k uses k chains of size 2, which is actually a matching. Each antichain of size n-k corresponds to an independent set in G, and the rest of k nodes forms a vertex cover.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .