Given a Delta-regular bipartite graph, it can be decomposed into Delta perfect matchings.
(The proof is via Hall's theorem: show that there exists a perfect matching in any regular bipartite graph, remove this perfect matching from the graph, and repeat.)
Suppose there was a non-integer vertex x* of BPM, note that since it is defined by some set of tight constraints with integer coefficients, this vector x* must be rational. Now you can scale the numbers by some integer C to get an integer vector Cx*. But this integer vector can be viewed as a bipartite multigraph where every vertex i has degree C(\sum_j x*_ij) = C(1) = C. Now we can use the fact above: this vector Cx* can be written as the sum of C perfect matchings.
Hence x* can be written as 1/C*this sum of perfect matchings, or a convex combination of perfect matchings, which means that it cannot itself be a vertex (extreme point) of the BPM.
(The proof is via Hall's theorem: show that there exists a perfect matching in any regular bipartite graph, remove this perfect matching from the graph, and repeat.)
Suppose there was a non-integer vertex x* of BPM, note that since it is defined by some set of tight constraints with integer coefficients, this vector x* must be rational. Now you can scale the numbers by some integer C to get an integer vector Cx*. But this integer vector can be viewed as a bipartite multigraph where every vertex i has degree C(\sum_j x*_ij) = C(1) = C. Now we can use the fact above: this vector Cx* can be written as the sum of C perfect matchings.
Hence x* can be written as 1/C*this sum of perfect matchings, or a convex combination of perfect matchings, which means that it cannot itself be a vertex (extreme point) of the BPM.
No comments:
Post a Comment