Finite Playground

Perfect matching equivalence

There are so many things can be written…

Anyway, the following observation is really interesting; details can be found in the book “matching theory” by Lovasz and Plummer.

Consider a general graph $G$.  An equivalence relationship can be defined on the nodes of the graph as follows: two nodes $x$ and $y$ are equivalent if $G-x-y$ has no perfect matching(!).

Dilworth Theorem and equivalence to Konig-Egervary Theorem

Dilworth’s Theorem. If $P$ is a finite poset, then the maximum size of an antichain in $P$ equals the minimum number of chains needed to cover the elements of $P$.

Proof. Induction on $|P|$. We separate into two cases.

(a) Some maximum antichain $A$ omits both a maximal element and a minimal element of $P$. Then neither $D[A]$ or $U[A]$ contains all of $P$; the maximality of $A$ implies $P = D[A] \cup U[A]$. Both $D[A]$ and $U[A]$ has width $w(P)$ because they contain $A$, and they only intersect in $A$. Apply induction hypothesis on both sets, we obtain $k$ chains covering $D[A]$ and $k$ chains covering $U[A]$; combining these chains form $k$ chains covering $P$.

(b) Every maximum antichain of $P$ consists of all maximal elements or all minimal elements. Thus $w(P-\{x,y\}) \le k-1$ if $x$ is a minimal element and $y$ is a maximal element below $x$. Apply induction hypothesis on $P-\{x,y\}$ gives us $k-1$ chains; add chain $\{x,y\}$ to get a covering of $P$.

Theorem.  Dilworth’s Theorem is equivalent to Konig-Egervary Theorem.

Proof.  Dilworth to Konig-Egervary: View an $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 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.

Konig-Egervary to Dilworth: Consider an arbitrary poset $P$ of size $n$. Define a bipartite graph $G$ as follow: For each element $x \in P$, create two nodes $x^-$ and $x^+$. The two parts of the graph are $\{x^- : x \in P\}$ and $\{x^+ : x \in P\}$. The edge set is $\{x^- y^+ : x <_P y\}$.

Every matching in $G$ yields a chain-covering in $P$ as follow: We start we $n$ chain, each contains a unique element. If $x^- y^+$ is in the matching then $x$ and $y$ are combined in the same chain. Therefore because each node in $G$ appears in at most on edge of the matching, a matching of $k$ edges forms a covering of $n-k$ chains.

Given a vertex cover $R$ in $G$ of size $k$, define a corresponding antichain $A = \{x \in P : x^-, x^+ \notin R\}$; this is indeed an antichain because if there is a relation $x <_P y$ in $A$ then edge $x^- y^+$ will be presented, and vertex cover $R$ needs to contain at least one of $x^-, y^+$.

Claim. No minimal vertex cover of $G$ uses both $\{x^-,x^+\}$, because by transitivity the sets $\{z^- : z \in D(x)\}$ and $\{y^+ : y \in U(x)\}$ induce a complete bipartite subgraph in $G$. A vertex cover of a complete bipartite graph must use all of one part. Since $x^-,x^+$ have all the neighbors in these two sets, we can remove one of $x^-,x^+$ that is not in the right part and decrease the size of the vertex cover.

Thus a minimum vertex cover of size $k$ yields an antichain of size $n-k$.

Maximum matching in general graphs

RandMatching(G), G 為 n-node m-edge graph.
1. 令$M_0$為任意 matching. 令$p = 2^m$.
2. 執行底下迴圈$k=10m \log n$次, 迴圈參數為$i$:
2.1 隨機選取一個邊$e$.
2.2 令$M'$$\frac{p}{1+p}$的機率是$M_i \cup \{e\}$, 有$\frac{1}{1+p}$的機率是$M_i \setminus \{e\}$.
2.3 假如$M'$是個 matching, 則令$M_{i+1} = M'$; 不然就還是讓$M_{i+1} = M_i$.
3. 輸出$M_k$, 程式結束.