组合数学 (Spring 2013)/Matching theory

From EtoneWiki
Jump to: navigation, search

Systems of Distinct Representatives (SDR)

A system of distinct representatives (SDR) (also called a transversal) for a sequence of (not necessarily distinct) sets is a sequence of distinct elements such that for all .

Hall's marriage theorem

If the sets have a system of distinct representatives , then it is obvious that . Moreover, for any subset ,

because are distinct.

Surprisingly, this obvious necessary condition for the existence of SDR is also sufficient, which is stated by the Hall's theorem, also called the mariage theorem.

Hall's Theorem
The sets have a system of distinct representatives (SDR) if and only if
for all .

The condition that for all is also called the Hall's condition.

Proof.

We only need to prove the sufficiency of Hall's condition for the existence of SDR. We do it by induction on . When , the theorem trivially holds. Now assume the theorem hold for any integer smaller than .

A subcollection of sets , , is called a critical family if .

Case.1: There is no critical family, i.e. for each , .

Take and choose an arbitrary as its representative. Remove from all other sets by letting for . Then for all ,

.

Due to the induction hypothesis, have an SDR, say . It is obvious that none of them equals because is removed. Thus, and form an SDR for .

Case.2: There is a critical family, i.e. , such that .

Suppose are such a collection of sets. Hall's condition certainly holds for these sets. Since , due to the induction hypothesis, there is an SDR for the sets, say .

Again, remove the elements from the remaining sets by letting for . By the Hall's condition, for any , writing that ,

,

thus

.

Due to the induction hypothesis, there is an SDR for , say . Combining it with the SDR for , we have an SDR for .

Hall's theorem is usually stated as a theorem for the existence of matching in a bipartite graph.

In a graph , a matching is an independent set for edges, that is, for any that , and are not adjacent to the same vertex.

In a bipartite graph , we say is a matching of (or a matching of ), if every vertex in (or ) is adjacent to some edge in , i.e., all vertices in (or ) are matched.

In a graph , for any vertex , let denote the set of neighbors of in ; and for any vertex set , we override the notation as , i.e. the set of vertices that are adjacent to one of the vertices in .

Hall's Theorem (graph theory form)
A bipartite graph has a matching of if and only if
for all .

Consider the collection of sets . A matching of is an SDR for these sets. Then clearly the theorem is equivalent to Hall's theorem.

Min-max theorems

In combinatorics (and also in other branches of mathematics), there is a family of theorems which relate the minimum of one thing to the maximum of something else. The following are some examples.

  • König-Egerváry theorem (König 1931; Egerváry 1931): in a bipartite graph, the maximum number of edges in a matching equals the minimum number of vertices in a vertex cover.
  • Menger's theorem (Menger 1927): the minimum number of vertices separating two given vertices in a graph equals the maximum number of vertex-disjoint paths between the two vertices.
  • Dilworth's theorem (Dilworth 1950): the minimum number of chains which cover a partially ordered set equals the maximum number of elements in an antichain.

König-Egerváry theorem

A matching in a graph is a set of edges such that no two edges shares a vertex. In other words, a matching is just an edge version of independent set.

A vertex cover in a graph is a vertex set such that every edge is adjacent to some , that is, all edges in the graph are "covered" by some vertex in the vertex cover .

The König-Egerváry theorem (also called the König's theorem) states the equality of the sizes of maximum matching and minimum vertex cover.

König-Egerváry Theorem (graph theory form)
In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

The König-Egerváry theorem can be reformulated in its matrix form. A bipartite graph can be represented as a matrix with 0-1 entries. For any and , if and only if . (Note that this definition is different from adjacency matrix for graphs.)

Then, a matching in corresponds to a set of independent 1's in : a set of 1's that do not share rows or columns. A vertex cover corresponds to a set of rows and columns covering all 1's in : a set of rows and columns that every 1-entry in belongs to at least one of these rows or columns.

It is easy to see the König-Egerváry theorem for bipartite graphs can be equivalently described as follows:

König-Egerváry Theorem (matrix form)
Let be an 0-1 matrix. The maximum number of independent 1's is equal to the minimum number of rows and columns required to cover all the 1's in .

We give a proof by the Hall's theorem.

Proof.

Let denote the maximum number of independent 1's in and be the minimum number of rows and columns to cover all 1's in . Clearly, , since any set of independent 1's requires together rows and columns to cover.

We now prove . Assume that some rows and columns cover all the 1's in , and , i.e. the covering is minimum. Because permuting the rows or the columns change neither nor (as reordering the vertices on either side in a bipartite graph changes nothing to the size of matchings and vertex covers), we may assume that the first rows and the first columns cover the 1's. Write in the form

,

where the submatrix has only zero entries. We will show that there are independent 1's in and independent 1's in , thus together has independent 1's, which will imply that , as desired.

Define

It is obvious that . We claim that the sequence has a system of distinct representatives, i.e., we can choose a 1 from each row, no two in the same column. Otherwise, Hall's theorem tells us that there exists some , such that , that is, the 1's in the rows contained by can be covered by less than columns. Thus, the 1's in can be covered by and less than columns, altogether less than rows and columns. Therefore, the 1's in can be covered by less than rows and columns, which contradicts the assumption that the size of the minimum covering of all 1's in is . Therefore, we show that has independent 1's.

By the same argument, we can show that has independent 1's. Since and share no rows or columns, the number of independent 1's in is .

Dilworth's theorem

Recall that a partially ordered set (or poset) consists of a set and a binary relation defined on , satisfying

  • reflexivity: ;
  • antisymmetry: and only if ;
  • transitivity: if and , then .

Two elements are said to be comparable if or ; and are incomparable if otherwise.

A poset is a totally ordered set, or a chain, if all pairs of elements in are comparable. A poset is an antichain if all pairs of elements in are incomparable.

Given a poset , we can partition it into chains. What is the minimum number of chains that we can break into? Dilworth's theorem tells us that it is equal to the size of the maximum antichain.

Dilworth's Theorem
Suppose that the largest antichain in the poset has size . Then can be partitioned into disjoint chains.
Proof.

Suppose has an antichain , and can be partitioned into disjoint chains . Then , since every chain can pass though an antichain at most once, that is, for all .

Therefore, we only need to prove that there exist an antichain of size , and a partition of into at most chains.

Define a bipartite graph where , and for any and , if and only if in the poset . By König-Egerváry theorem, there is a matching and a vertex set such that every edge in is adjacent to at least a vertex in , and .

Denote . Let be the set of uncovered elements in poset , i.e., the elements of that do not correspond to any vertex in . Clearly, . We claim that is an antichain. By contradiction, assume there exists such that . Then, by the definition of , there exist which corresponds to , and which corresponds to , such that . But since includes only those elements whose corresponding vertices are not in , none of can be in , which contradicts the fact that is a vertex cover of that every edges in are adjacent to at least a vertex in .

Let be a family of chains formed by including and in the same chain whenever . A moment thought would tell us that the number of chains in is equal to the unmatched vertices in (or ). Thus, .

Altogether, we construct an antichain of size and partition the poset into disjoint chains. The theorem is proved.

Application: Erdős-Szekeres Theorem

Let be a sequence of distinct real numbers.A subsequence of is an , with .

A sequence is increasing if , and decreasing if .

Recall that the Erdős-Szekeres theorem states the existence of long increasing subsequence or decreasing subsequence. Last time we prove this by the pigeonhole principle. Now we use the Dilworth's theorem to prove it, which is also the original proof due to Erdős-Szekeres.

Erdős-Szekeres Theorem
A sequence of more than different real numbers must contain either an increasing subsequence of length , or a decreasing subsequence of length .
Proof by Dilworth's theorem
(Original proof of Erdős-Szekeres)

Let be the sequence of distinct real numbers. Define the poset as

and if and only if and .

A chain must have and . Thus, each chain correspond to an increasing subsequence.

Let be an antichain. Without loss of generality, we can assume that . The only case that these elements are non-comparable is that , otherwise if for some , then , which contradicts the fact that it is an antichain. Thus, each antichain corresponds to a decreasing subsequence.

If has an antichain of size , then has a decreasing subsequence of size , and we are done.

Alternatively, if the largest antichain in is of size at most , then by Dilworth's theorem, can be partitioned into no more than disjoint chains, due to pigeonhole principle, one of which must be of length , which means has an increasing subsequence of size .

Application: Hall's Theorem

To recognize the power of Dilworth's theorem, we show that it contains Hall's theorem as a special case!

Hall's Theorem
The sets have a system of distinct representatives (SDR) if and only if
for all .
Proof by Dilworth's theorem

As we discussed before, the necessity of Hall's condition for the existence of SDR is easy. We prove its sufficiency by Dilworth's theorem.

Denote . Construct a poset by letting and for all . There are no other comparabilities.

It is obvious that is an antichain. We claim it is also the largest one. To prove this, let be an arbitrary antichain, and let . Then contains no elements of , since if and , then and cannot be an antichain. Thus,

and by Hall's condition , thus , as claimed.

Now, Dilworth's theorem implies that can be partitioned into chains. Since is an antichain and each chain can pass though an antichain on at most one element, each of the chains contain precisely one . And since is also an antichain, each of these chains contain at most one . Altogether, the chains are in the form:

.

Since the only comparabilities in our posets are and the above chains are disjoint, we have as an SDR.