组合数学 (Fall 2011)/Ramsey theory and 组合数学 (Fall 2011)/Flow and matching: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
imported>WikiSysop
 
Line 1: Line 1:
== Ramsey's Theorem ==
== Flow and Cut==
=== Ramsey's theorem for graph ===
{{Theorem|Ramsey's Theorem|
:Let <math>k,\ell</math> be positive integers. Then there exists an integer <math>R(k,\ell)</math> satisfying:
:If <math>n\ge R(k,\ell)</math>, for any coloring of edges of <math>K_n</math> with two colors red and blue, there exists a red <math>K_k</math> or a blue <math>K_\ell</math>.
}}
{{Proof|
We show that <math>R(k,\ell)</math> is finite by induction on <math>k+\ell</math>. For the base case, it is easy to verify that
:<math>R(k,1)=R(1,\ell)=1</math>.
For general <math>k</math> and <math>\ell</math>, we will show that
:<math>R(k,\ell)\le R(k,\ell-1)+R(k-1,\ell)</math>.
Suppose we have a two coloring of <math>K_n</math>, where <math>n=R(k,\ell-1)+R(k-1,\ell)</math>. Take an arbitrary vertex <math>v</math>, and split <math>V\setminus\{v\}</math> into two subsets <math>S</math> and <math>T</math>, where
:<math>\begin{align}
S&=\{u\in V\setminus\{v\}\mid uv \text{ is blue }\}\\
T&=\{u\in V\setminus\{v\}\mid uv \text{ is red }\}
\end{align}</math>
Since
:<math>|S|+|T|+1=n=R(k,\ell-1)+R(k-1,\ell)</math>,
we have either <math>|S|\ge R(k,\ell-1)</math> or <math>|T|\ge R(k-1,\ell)</math>. By symmetry, suppose <math>|S|\ge R(k,\ell-1)</math>. By induction hypothesis, the complete subgraph defined on <math>S</math> has either a red <math>K_k</math>, in which case we are done; or a blue <math>K_{\ell-1}</math>, in which case the complete subgraph defined on <math>S\cup{v}</math> must have a blue <math>K_\ell</math> since all edges from <math>v</math> to vertices in <math>S</math> are blue.
}}


{{Theorem|Ramsey's Theorem (graph, multicolor)|
=== Flows ===
:Let <math>r, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R(r;k_1,k_2,\ldots,k_r)</math> satisfying:
An instance of the maximum flow problem consists of:
:For any <math>r</math>-coloring of a complete graph of <math>n\ge R(r;k_1,k_2,\ldots,k_r)</math> vertices, there exists a monochromatic <math>k_i</math>-clique with the <math>i</math>th color for some <math>i\in\{1,2,\ldots,r\}</math>.
* a directed graph <math>G(V,E)</math>;
}}
* two distinguished vertices <math>s</math> (the '''source''') and <math>t</math> (the '''sink'''), where the in-degree of <math>s</math> and the out-degree of <math>t</math> are both 0;
* the '''capacity function'''  <math>c:E\rightarrow\mathbb{R}^+</math> which associates each directed edge <math>(u,v)\in E</math> a nonnegative real number <math>c_{uv}</math> called the '''capacity''' of the edge.


{{Theorem|Lemma (the "mixing color" trick)|
The quadruple <math>(G,c,s,t)</math> is called a '''flow network'''.
:<math>R(r;k_1,k_2,\ldots,k_r)\le R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r))</math>
}}
{{Proof|
We transfer the <math>r</math>-coloring to <math>(r-1)</math>-coloring by identifying the <math>(r-1)</math>th and the <math>r</math>th colors.  


If <math>n\ge R(r-1;k_1,k_2,\ldots,k_{r-2},R(2;k_{r-1},k_r))</math>, then for any <math>r</math>-coloring of <math>K_n</math>, there either exist an <math>i\in\{1,2,\ldots,r-2\}</math> and a <math>k_i</math>-clique which is monochromatically colored with the <math>i</math>th color; or exists clique of <math>R(2;k_{r-1},k_r)</math> vertices which is monochromatically colored with the mixed color of the original <math>(r-1)</math>th and <math>r</math>th colors, which again implies that there exists either a <math>k</math>-clique which is monochromatically colored with the original <math>(r-1)</math>th color, or a <math>\ell</math>-clique which is monochromatically colored with the original <math>r</math>th color. This implies the recursion.
A function <math>f:E\rightarrow\mathbb{R}^+</math> is called a '''flow''' (to be specific an '''<math>s</math>-<math>t</math> flow''') in the network <math>G(V,E)</math> if it satisfies:
}}
* '''Capacity constraint:''' <math>f_{uv}\le c_{uv}</math> for all <math>(u,v)\in E</math>.
* '''Conservation constraint:''' <math>\sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw}</math> for all <math>v\in V\setminus\{s,t\}</math>.


=== Ramsey number ===
The '''value''' of the flow <math>f</math> is <math>\sum_{v:(s,v)\in E}f_{sv}</math>.  
The smallest number <math>R(k,\ell)</math> satisfying the condition in the Ramsey theory is called the '''Ramsey number'''.  


Alternatively, we can define <math>R(k,\ell)</math> as the smallest <math>N</math> such that if <math>n\ge N</math>, for any 2-coloring of <math>K_n</math> in red and blue, there is either a red <math>K_k</math> or a blue <math>K_\ell</math>. The Ramsey theorem is stated as:
Given a flow network, the maximum flow problem asks to find the flow of the maximum value.
:"''<math>R(k,\ell)</math> is finite for any positive integers <math>k</math> and <math>\ell</math>.''"


The core of the inductive proof of the Ramsey theorem is the following recursion
The maximum flow problem can be described as the following linear program.
:<math>\begin{align}
:<math>
R(k,1) &=R(1,\ell)=1\\
\begin{align}
R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell).
\text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\
\end{align}</math>
\begin{align}
\text{subject to} \\
\\
\\
\\
\end{align}
\quad &
\begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\
\sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\
f_{uv}&\ge 0 &\quad& \forall (u,v)\in E
\end{align}
\end{align}
</math>


From this recursion, we can deduce an upper bound for the Ramsey number.
=== Cuts ===
{{Theorem|Theorem|
{{Theorem|Definition|
:<math>R(k,\ell)\le{k+\ell-2\choose k-1}</math>.
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>S\subset V</math>. We call <math>(S,\bar{S})</math> an '''<math>s</math>-<math>t</math> cut''' if <math>s\in S</math> and <math>t\not\in S</math>.
}}
:The '''value''' of  the cut (also called the '''capacity''' of the cut) is defined as <math>\sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
{{Proof|It is easy to verify the bound by induction.
}}
}}


------
A fundamental fact in flow theory is that cuts always upper bound flows.


The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.
{{Theorem|Lemma|
:Let <math>(G(V,E),c,s,t)</math> be a flow network. Let <math>f</math> be an arbitrary flow in <math>G</math>, and let <math>(S,\bar{S})</math> be an arbitrary <math>s</math>-<math>t</math> cut. Then
::<math>\sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
:that is, the value of any flow is no greater than the value of any cut.
}}
{{Proof|By the definition of <math>s</math>-<math>t</math> cut, <math>s\in S</math> and <math>t\not\in S</math>.  


{{Theorem|Theorem (Spencer 1975)|
Due to the conservation of flow,
:<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
:<math>\sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,.</math>
On the other hand, summing flow over edges,
:<math>\sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,.</math>
Therefore,
:<math>\sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le  \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,,</math>
}}
}}


Its proof uses the Lovász local lemma in the probabilistic method.
=== Augmenting paths ===
{{Theorem
{{Theorem|Definition (Augmenting path)|
|Lovász Local Lemma (symmetric case)|
:Let <math>f</math> be a flow in <math>G</math>. An '''augmenting path to <math>u_k</math>''' is a sequence of distinct vertices <math>P=(u_0,u_1,\cdots, u_k)</math>, such that  
:Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
:* <math>u_0=s\,</math>;
:#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
:and each pair of consecutive vertices <math>u_{i}u_{i+1}\,</math> in <math>P</math> corresponds to either a '''forward edge''' <math>(u_{i},u_{i+1})\in E</math> or a '''reverse edge''' <math>(u_{i+1},u_{i})\in E</math>, and
:# each event <math>A_i</math> is independent of all but at most <math>d</math> other events, and
:* <math>f(u_i,u_{i+1})<c(u_i,u_{i+1})\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a forward edge <math>(u_{i},u_{i+1})\in E</math>, and  
:::<math>ep(d+1)\le 1</math>.
:* <math>f(u_{i+1},u_i)>0\,</math> when <math>u_{i}u_{i+1}\,</math> corresponds to a reverse edge <math>(u_{i+1},u_{i})\in E</math>.
:Then
:If <math>u_k=t\,</math>, we simply call <math>P</math> an '''augmenting path'''.
::<math>\Pr\left[\bigwedge_{i=1}^n\overline{A_i}\right]>0</math>.
}}
}}


We can use the local lemma to prove a lower bound for the diagonal Ramsey number.
Let <math>f</math> be a flow in <math>G</math>. Suppose there is an augmenting path <math>P=u_0u_1\cdots u_k</math>, where <math>u_0=s</math> and <math>u_k=t</math>. Let <math>\epsilon>0</math> be a positive constant satisfying
{{Proof|
*<math>\epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1})</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math>;
To prove a lower bound <math>R(k,k)>n</math>, it is sufficient to show that there exists a 2-coloring of <math>K_n</math> without a monochromatic <math>K_k</math>. We prove this by the probabilistic method.
*<math>\epsilon \le f(u_{i+1},u_i)</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>.
Due to the definition of augmenting path, we can always find such a positive <math>\epsilon</math>.  


Pick a random 2-coloring of <math>K_n</math> by coloring each edge uniformly and independently with one of the two colors. For any set <math>S</math> of <math>k</math> vertices, let <math>A_S</math> denote the event that <math>S</math> forms a monochromatic <math>K_k</math>. It is easy to see that <math>\Pr[A_s]=2^{1-{k\choose 2}}=p</math>.
Increase <math>f(u_i,u_{i+1})</math> by <math>\epsilon</math> for all forward edges <math>(u_{i},u_{i+1})\in E</math> in <math>P</math> and decrease <math>f(u_{i+1},u_i)</math> by <math>\epsilon</math> for all reverse edges <math>(u_{i+1},u_i)\in E</math> in <math>P</math>. Denote the modified flow by <math>f'</math>. It can be verified that <math>f'</math> satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow <math>f'</math>
:<math>\sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}>\sum_{v:(s,v)\in E}f_{sv}</math>.
Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.


For any <math>k</math>-subset <math>T</math> of vertices, <math>A_S</math> and <math>A_T</math> are dependent if and only if <math>|S\cap T|\ge 2</math>. For each <math>S</math>, the number of <math>T</math> that <math>|S\cap T|\ge 2</math> is at most <math>{k\choose 2}{n\choose k-2}</math>, so the max degree of the dependency graph is <math>d\le{k\choose 2}{n\choose k-2}</math>.
{{Theorem|Lemma|
 
:A flow <math>f</math> is maximum if and only if there are no augmenting paths.
Take <math>n=Ck2^{k/2}</math> for some appropriate constant <math>C>0</math>.
:<math>
\begin{align}
\mathrm{e}p(d+1)
&\le \mathrm{e}2^{1-{k\choose 2}}\left({k\choose 2}{n\choose k-2}+1\right)\\
&\le 2^{3-{k\choose 2}}{k\choose 2}{n\choose k-2}\\
&\le 1
\end{align}
</math>
Applying the local lemma, the probability that there is no monochromatic <math>K_k</math> is
:<math>\Pr\left[\bigwedge_{S\in{[n]\choose k}}\overline{A_S}\right]>0</math>.
Therefore, there exists a 2-coloring of <math>K_n</math> which has no monochromatic <math>K_k</math>, which means
:<math>R(k,k)>n=Ck2^{k/2}</math>.
}}
}}
{{Proof|We have already proved the "only if" direction above. Now we prove the "if" direction.


{{Theorem|Theorem|
Let <math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>. Clearly <math>s\in S</math>, and since there is no augmenting path <math>t\not\in S</math>. Therefore, <math>(S,\bar{S})</math> defines an <math>s</math>-<math>t</math> cut.  
:<math>\Omega\left(k2^{k/2}\right)\le R(k,k)\le{2k-2\choose k-1}=O\left(k^{-1/2}4^{k}\right)</math>.
}}


{| class="wikitable"
We claim that
! ''<math>k</math>'',''<math>l</math>''
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
! 1
that is, the value of flow <math>f</math> approach the value of the cut <math>(S,\bar{S})</math> defined above. By the above lemma, this will imply that the current flow <math>f</math> is maximum.
! 2
! 3
! 4
! 5
! 6
! 7
! 8
! 9
! 10
|-
! 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
| 1
|-
! 2
| 1
| 2
| 3
| 4
| 5
| 6
| 7
| 8
| 9
| 10
|-
! 3
| 1
| 3
| 6
| 9
| 14
| 18
| 23
| 28
| 36
| 40–43
|-
! 4
| 1
| 4
| 9
| 18
| 25
| 35–41
| 49–61
| 56–84
| 73–115
| 92–149
|-
! 5
| 1
| 5
| 14
| 25
| 43–49
| 58–87
| 80–143
| 101–216
| 125–316
| 143–442
|-
! 6
| 1
| 6
| 18
| 35–41
| 58–87
| 102–165
| 113–298
| 127–495
| 169–780
| 179–1171
|-
! 7
| 1
| 7
| 23
| 49–61
| 80–143
| 113–298
| 205–540
| 216–1031
| 233–1713
| 289–2826
|-
! 8
| 1
| 8
| 28
| 56–84
| 101–216
| 127–495
| 216–1031
| 282–1870
| 317–3583
| 317-6090
|-
! 9
| 1
| 9
| 36
| 73–115
| 125–316
| 169–780
| 233–1713
| 317–3583
| 565–6588
| 580–12677
|-
! 10
| 1
| 10
| 40–43
| 92–149
| 143–442
| 179–1171
| 289–2826
| 317-6090
| 580–12677
| 798–23556
|}


=== Ramsey's theorem for hypergraph ===
To prove this claim, we first observe that
{{Theorem|Ramsey's Theorem (hypergraph, multicolor)|
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}</math>.
:Let <math>r, t, k_1,k_2,\ldots,k_r</math> be positive integers. Then there exists an integer <math>R_t(r;k_1,k_2,\ldots,k_r)</math> satisfying:
This identity is implied by the flow conservation constraint, and holds for any <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.
:For any <math>r</math>-coloring of <math>{[n]\choose t}</math> with <math>n\ge R_t(r;k_1,k_2,\ldots,k_r)</math>,  there exist an <math>i\in\{1,2,\ldots,r\}</math> and a subset <math>X\subseteq [n]</math> with <math>|X|\ge k_i</math> such that all members of <math>{X\choose t}</math> are colored with the <math>i</math>th color.
}}


<math>n\rightarrow(k_1,k_2,\ldots,k_r)^t</math>
We then claim that
*<math>f_{uv}=c_{uv}</math> for all <math>u\in S,v\not\in S, (u,v)\in E</math>; and
*<math>f_{vu}=0</math> for all <math>u\in S,v\not\in S, (v,u)\in E</math>.
If otherwise, then the augmenting path to <math>u</math> apending <math>uv</math> becomes a new augmenting path to <math>v</math>, which contradicts that <math>S</math> includes all vertices to which there exist augmenting paths.


{{Theorem|Lemma (the "mixing color" trick)|
Therefore,
:<math>R_t(r;k_1,k_2,\ldots,k_r)\le R_t(r-1;k_1,k_2,\ldots,k_{r-2},R_t(2;k_{r-1},k_r))</math>
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>.
As discussed above, this proves the theorem.
}}
}}


It is then sufficient to prove the Ramsey's theorem for the two-coloring of a hypergraph, that is, to prove <math>R_t(k,\ell)=R_t(2;k,\ell)</math> is finite.
== Max-Flow Min-Cut ==


{{Theorem|Lemma|
=== The max-flow min-cut theorem ===
:<math>R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>
{{Theorem|Max-Flow Min-Cut Theorem|
:In a flow network, the maximum value of any <math>s</math>-<math>t</math> flow equals the minimum value of any <math>s</math>-<math>t</math> cut.
}}
}}
{{Proof|
{{Proof|
Let <math>n=R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>. Denote <math>[n]=\{1,2,\ldots,n\}</math>.
Let <math>f</math> be a flow with maximum value, so there is no augmenting path.


Let <math>f:{[n]\choose t}\rightarrow\{{\color{red}\text{red}},{\color{blue}\text{blue}}\}</math> be an arbitrary 2-coloring of <math>{[n]\choose t}</math>. It is then sufficient to show that there either exists an <math>X\subseteq[n]</math> with <math>|X|=k</math> such that all members of <math>{X\choose t}</math> are colored red by <math>f</math>; or exists an <math>X\subseteq[n]</math> with <math>|X|=\ell</math> such that all members of <math>{X\choose t}</math> are colored blue by <math>f</math>.
Again, let
:<math>S=\{u\in V\mid \exists\text{an augmenting path to }u\}</math>.
As proved above, <math>(S,\bar{S})</math> forms an <math>s</math>-<math>t</math> cut, and
:<math>\sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}</math>,
that is, the value of flow <math>f</math> equals the value of cut <math>(S,\bar{S})</math>.  


We remove <math>n</math> from <math>[n]</math> and define a new coloring <math>f'</math> of <math>{[n-1]\choose t-1}</math> by
Since we know that all <math>s</math>-<math>t</math> flows are not greater than any <math>s</math>-<math>t</math> cut, the value of flow <math>f</math> equals the minimum value of any <math>s</math>-<math>t</math> cut.
:<math>f'(A)=f(A\cup\{n\})</math> for any <math>A\in{[n-1]\choose t-1}</math>.
By the choice of <math>n</math> and by symmetry, there exists a subset <math>S\subseteq[n-1]</math> with <math>|X|=R_t(k-1,\ell)</math> such that all members of <math>{S\choose t-1}</math> are colored with red by <math>f'</math>. Then there either exists an <math>X\subseteq S</math> with <math>|X|=\ell</math> such that <math>{X\choose t}</math> is colored all blue by <math>f</math>, in which case we are done; or exists an <math>X\subseteq S</math> with <math>|X|=k-1</math> such that <math>{X\choose t}</math> is colored all red by <math>f</math>. Next we prove that in the later case <math>{X\cup{n}\choose t}</math> is all red, which will close our proof. Since all <math>A\in{S\choose t-1}</math> are colored with red by <math>f'</math>, then by our definition of <math>f'</math>, <math>f(A\cup\{n\})={\color{red}\text{red}}</math> for all <math>A\in {X\choose t-1}\subseteq{S\choose t-1}</math>. Recalling that <math>{X\choose t}</math> is colored all red by <math>f</math>, <math>{X\cup\{n\}\choose t}</math> is colored all red by <math>f</math> and we are done.
}}
}}


== Applications of Ramsey Theorem ==
=== Flow Integrality Theorem ===
=== The "Happy Ending" problem ===
{{Theorem|Flow Integrality Theorem|
{{Theorem|The happy ending problem|
:Let <math>(G,c,s,t)</math> be a flow network with integral capacity <math>c</math>. There exists an integral flow which is maximum.
:Any set of 5 points in the plane, no three on a line, has a subset of 4 points that form the vertices of a convex quadrilateral.
}}
{{Proof|
Let <math>f</math> be an integral flow of maximum value. If there is an augmenting path, since both <math>c</math> and <math>f</math> are integral, a new flow can be constructed of value 1+the value of <math>f</math>, contradicting that <math>f</math> is maximum over all integral flows. Therefore, there is no augmenting path, which means that <math>f</math> is maximum over all flows, integral or not.
}}
}}
See the article
[http://www.maa.org/mathland/mathtrek_10_3_00.html] for the proof.


We say a set of points in the plane in [http://en.wikipedia.org/wiki/General_position '''general positions'''] if no three of the points are on the same line.
=== Applications: Menger's theorem ===
 
Given an undirected graph <math>G(V,E)</math> and two distinct vertices <math>s,t\in V</math>, a set of edges <math>C\subseteq E</math> is called an '''<math>s</math>-<math>t</math> cut''', if deleting edges in <math>C</math> disconnects <math>s</math> and <math>t</math>.
{{Theorem|Theorem (Erdős-Szekeres 1935)|
:For any positive integer <math>m\ge 3</math>, there is an <math>N(m)</math> such that any set of at least <math>N(m)</math> points in general position in the plane (i.e., no three of the points are on a line) contains <math>m</math> points that are the vertices of a convex <math>m</math>-gon.
}}
{{Proof|
Let <math>N(m)=R_3(m,m)</math>. For <math>n\ge N(m)</math>, let <math>X</math> be an arbitrary set of <math>n</math> points in the plane, no three of which are on a line. Define a 2-coloring of the 3-subsets of points <math>f:{X\choose 3}\rightarrow\{0,1\}</math> as follows: for any <math>\{a,b,c\}\in{X\choose 3}</math>, let <math>\triangle_{abc}\subset X</math> be the set of points covered by the triangle <math>abc</math>; and <math>f(\{a,b,c\})=|\triangle_{abc}|\bmod 2</math>, that is, <math>f(\{a,b,c\})</math> indicates the oddness of the number of points covered by the triangle <math>abc</math>.


Since <math>|X|\ge R_3(m,m)</math>, there exists a <math>Y\subseteq X</math> such that <math>|Y|=m</math> and all members of <math>{Y\choose 3}</math> are colored with the same value by <math>f</math>.  
A simple path from <math>s</math> to <math>t</math> is called an '''<math>s</math>-<math>t</math> path'''. Two paths are said to be '''edge-disjoint''' if they do not share any edge.


We claim that the <math>m</math> points in <math>Y</math> are the vertices of a convex <math>m</math>-gon. If otherwise, by the definition of convexity, there exist <math>\{a,b,c,d\}\subseteq Y</math> such that <math>d\in\triangle_{abc}</math>. Since no three points are in the same line,
{{Theorem|Theorem (Menger 1927)|
:<math>\triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\}</math>,
:Let <math>G(V,E)</math> be an arbitrary undirected graph and <math>s,t\in V</math> be two distinct vertices. The minimum size of any <math>s</math>-<math>t</math> cut equals the maximum number of edge-disjoint <math>s</math>-<math>t</math> paths.
where all unions are disjoint. Then <math>|\triangle_{abc}|=|\triangle_{abd}|+|\triangle_{acd}|+|\triangle_{bcd}|+1</math>, which implies that <math>f(\{a,b,c\}), f(\{a,b,d\}), f(\{a,c,d\}), f(\{b,c,d\})\,</math> cannot be equal, contradicting that all members of <math>{Y\choose 3}</math> have the same color.
}}
}}
{{proof|
Construct a directed graph <math>G'(V,E')</math> from <math>G(V,E)</math> as follows: replace every undirected edge <math>uv\in E</math> that <math>s,t\not\in\{u,v\}</math> by two directed edges <math>(u,v)</math> and <math>(v,u)</math>; replace every undirected edge <math>sv\in E</math> by <math>(s,v)</math>, and very undirected edge <math>vt\in E</math> by <math>(v,t)</math>. Then assign every directed edge with capacity 1.


=== Yao's lower bound on implicit data structures ===
It is easy to verify that in the flow network constructed as above, the followings hold:
{{Theorem|Lemma|
*An integral <math>s</math>-<math>t</math> flow corresponds to a set of <math>s</math>-<math>t</math> paths in the undirected graph <math>G</math>, where the value of the flow is the number of <math>s</math>-<math>t</math> paths.
:Let <math>n\ge 2</math> be a power of 2 and <math>N\ge 2n</math>. Suppose the universe is <math>[N]</math> and the size of the data set is <math>n</math>.
*An <math>s</math>-<math>t</math> cut in the flow network corresponds to an <math>s</math>-<math>t</math> cut in the undirected graph <math>G</math> with the same value.
:If the data structure is a sorted table, any search algorithm requires at least <math>\log n</math> accesses to the data structure in the worst case.
The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.
}}
}}
{{Proof|
We will show by an adversarial argument that <math>\log n</math> accesses are required to search for the key value <math>x=n</math> from the universe <math>[N]=\{1,2,\ldots,N\}</math>. The construction of the adversarial data set <math>S</math> is by induction on <math>n</math>.


For <math>n=2</math> and <math>N\ge 2n-1=3</math> it is easy to see that two accesses are necessary.
=== Applications: König-Egerváry theorem ===
Let <math>G(V,E)</math> be a graph. An edge set <math>M\subseteq E</math> is called a '''matching''' if no edge in <math>M</math> shares any vertex. A vertex set <math>C\subseteq V</math> is called a '''vertex cover''' if for any edge <math>uv\in E</math>, either <math>u\in C</math> or <math>v\in C</math>.


Let <math>n>2</math>. Assume the induction hypothesis to be true for all smaller <math>n</math>; we will prove it for the size of data set <math>n</math>, size of universe <math>N\ge 2n</math> and the search key <math>x=n</math>.
{{Theorem|Theorem (König 1936)|
:In any bipartite graph <math>G(V_1,V_2,E)</math>, the size of a ''maximum'' matching equals the size of a ''minimum'' vertex cover.
}}
We now show how a reduction of bipartite matchings to flows.  


Suppose that the first access position is <math>k</math>. The adversary chooses the table content <math>T[k]</math>. The adversary's strategy is:
Construct a flow network <math>(G'(V,E'),c,s,t)</math> as follows:
:<math>
* <math>V=V_1\cup V_2\cup\{s,t\}</math> where <math>s</math> and <math>t</math> are two new vertices.
\begin{align}
* For ever <math>uv\in E</math>, add <math>(u,v)</math> to <math>E'</math>; for every <math>u\in V_1</math>, add <math>(s,u)</math> to <math>E'</math>; and for every <math>v\in V_2</math>, add <math>(v,t)</math> to <math>E'</math>.
T[k]=
* Let <math>c_{su}=1</math> for every <math>u\in V_1</math> and <math>c_{vt}=1</math> for every <math>v\in V_2</math>. Let <math>c_{uv}=\infty</math> for every bipartite edges <math>(u,v)</math>.
\begin{cases}
k & k\le \frac{n}{2},\\
N-(n-k) & k> \frac{n}{2}.
\end{cases}
\end{align}
</math>
By symmetry, suppose it is the first case that <math>k\le \frac{n}{2}</math>.  Then the key <math>x=n</math> may be in any position <math>i</math>, where <math>n/2+1\le i\le n</math>. In fact, <math>T[ n/2+1]</math> through <math>T[n]</math> is a sorted table of size <math>n'=n/2</math> which may contain any <math>n'</math>-subset of <math>\{n/2+1, n/2+2,\ldots,N\}</math>, and hence, in particular, any <math>n'</math>-subset of the universe
:<math>U'=\{n/2+1, n/2+2,\ldots,N-n/2\}</math>.
The size <math>N'</math> of <math>U'</math> satisfies
:<math>N'=N-n/2-n/2\ge 2n-n\ge 2n'</math>,
and the desired key <math>n</math> has the relative value <math>x'=n- n/2=n'</math> in the universe <math>U'</math>.  


By the induction hypothesis, <math>\log n'=-1+\log n</math> more accesses will be required. Hence the total number of accesses is at least <math>1+\log n'=\log n</math>.
{{Theorem|Lemma|
 
:The size of a maximum matching in <math>G</math> is equal to the value of a maximum <math>s</math>-<math>t</math> flow in <math>G'</math>.
If the first access is <math>k> \frac{n}{2}</math>, we symmetrically get that <math>T[1]</math> through <math>T[n/2]</math> is a sorted table of size <math>n'=n/2</math> which may contain any <math>n'</math>-subset of the universe
:<math>U'=\{n/2+1, n/2+2,\ldots,N-n/2\}</math>.
The rest is the same.
}}
}}
{{proof|
Given an integral <math>s</math>-<math>t</math> flow <math>f</math> in <math>G'</math>, let <math>M=\{uv\in E\mid f_{uv}=1\}</math>. Then <math>M</math> must be a matching since for every <math>u\in V_1</math>. To see this, observe that there is at most one <math>v\in V_2</math> that <math>f_{uv}=1</math>, because of that <math>f_{su}\le c_{su}=1</math> and conservation of flows. The same holds for vertices in <math>V_2</math> by the same argument. Therefore, each flow corresponds to a matching.


Given a matching <math>M</math> in bipartite graph <math>G</math>, define an integral flow <math>f</math> as such: for <math>uv\in E</math>, <math>f_{uv}=1</math> if <math>uv\in M</math> and <math>f_{uv}=0</math> if otherwise; for <math>u\in V_1</math>, <math>f_{su}=1</math> if <math>uv\in M</math> for some <math>v</math> and <math>f_{su}=0</math> if otherwise; for <math>v\in V_2</math>, <math>f_{vt}=1</math> if <math>uv\in M</math> for some <math>u</math> and <math>f_{vt}=0</math> if otherwise.


We have seen that on a sorted table, there is no search algorithm outperforming the binary search in the worst case.
It is easy to check that <math>f</math> is valid <math>s</math>-<math>t</math> flow in <math>G'</math>. Therefore, there is an one-one correspondence between flows in <math>G'</math> and matchings in <math>G</math>. The lemma follows naturally.
Our question is:
}}
:''Is there any other order than the increasing order, on which there is a better search algorithm?''


An '''implicit data structure''' use no extra space in addition to the original data set, thus a data structure can only be represented ''implicitly'' by the order of the data items in the table. That is, each data set is stored as a permutation of the set. Formally, an implicit data structure is a function
We then establish a correspondence between <math>s</math>-<math>t</math> cuts in <math>G'</math> and vertex covers in <math>G</math>.
:<math>f:{U\choose n}\rightarrow[n!]</math>,
where each <math>\pi\in[n!]</math> specify a permutation of the sorted table. Thus, the sorted table is the simplest implicit data structure, in which <math>f(S)</math> is the identity for all <math>S\in{U\choose n}</math>.


== Ramsey Theory==
Suppose <math>(S,\bar{S})</math> is an <math>s</math>-<math>t</math> cut in <math>G'</math>.
=== Van der Waerden's Theorem ===
{{Theorem|Lemma|
{{Theorem|Theorem (Van der Waerden 1927)|
:The size of a minimum vertex cover in <math>G</math> is equal to the value of a minimum <math>s</math>-<math>t</math> cut in <math>G'</math>.
:For every choice of positive integers <math>r</math> and <math>t</math>, there exists an integer <math>W(r,t)</math> such that for every <math>r</math>-coloring of <math>[n]</math> where <math>n\ge W(r,t)</math>, there exists a monochromatic arithmetic progression of length <math>t</math>.
}}
}}
 
{{proof|
=== Hales–Jewett Theorem ===
Let <math>(S,\bar{S})</math> be an <math>s</math>-<math>t</math> cut of minimum capacity in <math>G'</math>. Then <math>\sum_{u\in S, v\not\in S\atop (u,v)\in E'}c_{uv}</math> must be finite since <math>S=\{s\}</math> gives us an <math>s</math>-<math>t</math> cut whose capacity is <math>|V_1|</math> which is finite. Therefore, no edge <math>uv\in E</math> has <math>u\in V_1\cap S</math> and <math>v\in V_2\setminus S</math>, i.e., for all <math>uv\in E</math>, either <math>u\in V_1\setminus S</math> or <math>v\in V_2\cap S</math>. Therefore, <math>(V_1\setminus S)\cup(V_2\cap S)</math> is a vertex cover in <math>G</math>, whose size is
{{Theorem|Theorem (Hales-Jewett 1963)|
:<math>|(V_1\setminus S)\cup(V_2\cap S)|=|V_1\setminus S|+|V_2\cap S|=\sum_{u\in V_1\setminus S}c_{su}+\sum_{v\in V_2\cap S}c_{ut}=\sum_{u\in S,v\not\in S\atop (u,v)\in E'}c_{uv}</math>.
:Let <math>A</math> be a finte alphabet of <math>t</math> symbols and let <math>r</math> be a positive integer. Then there exists an integer <math>\mathrm{HJ}(r,t)</math> such that for every <math>r</math>-coloring of the cube <math>A^n</math> where <math>n\ge \mathrm{HJ}(r,t)</math>, there exists a combinatorial line, which is monochromatic.
The last term is the capacity of the minimum <math>s</math>-<math>t</math> cut <math>(S,\bar{S})</math>.
}}
}}


{{Theorem|Theorem (Hales-Jewett 1963)|
The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.
:Let <math>A</math> be a finte alphabet of <math>t</math> symbols and let <math>m,r</math> be positive integers. Then there exists an integer <math>\mathrm{HJ}(m,r,t)</math> such that for every <math>r</math>-coloring of the cube <math>A^n</math> where <math>n\ge \mathrm{HJ}(r,t)</math>, there exists a combinatorial <math>m</math>-space, which is monochromatic.
}}

Revision as of 03:38, 17 August 2011

Flow and Cut

Flows

An instance of the maximum flow problem consists of:

  • a directed graph [math]\displaystyle{ G(V,E) }[/math];
  • two distinguished vertices [math]\displaystyle{ s }[/math] (the source) and [math]\displaystyle{ t }[/math] (the sink), where the in-degree of [math]\displaystyle{ s }[/math] and the out-degree of [math]\displaystyle{ t }[/math] are both 0;
  • the capacity function [math]\displaystyle{ c:E\rightarrow\mathbb{R}^+ }[/math] which associates each directed edge [math]\displaystyle{ (u,v)\in E }[/math] a nonnegative real number [math]\displaystyle{ c_{uv} }[/math] called the capacity of the edge.

The quadruple [math]\displaystyle{ (G,c,s,t) }[/math] is called a flow network.

A function [math]\displaystyle{ f:E\rightarrow\mathbb{R}^+ }[/math] is called a flow (to be specific an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow) in the network [math]\displaystyle{ G(V,E) }[/math] if it satisfies:

  • Capacity constraint: [math]\displaystyle{ f_{uv}\le c_{uv} }[/math] for all [math]\displaystyle{ (u,v)\in E }[/math].
  • Conservation constraint: [math]\displaystyle{ \sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw} }[/math] for all [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

The value of the flow [math]\displaystyle{ f }[/math] is [math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv} }[/math].

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\ge 0 &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

Cuts

Definition
Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ S\subset V }[/math]. We call [math]\displaystyle{ (S,\bar{S}) }[/math] an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut if [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math].
The value of the cut (also called the capacity of the cut) is defined as [math]\displaystyle{ \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math].

A fundamental fact in flow theory is that cuts always upper bound flows.

Lemma
Let [math]\displaystyle{ (G(V,E),c,s,t) }[/math] be a flow network. Let [math]\displaystyle{ f }[/math] be an arbitrary flow in [math]\displaystyle{ G }[/math], and let [math]\displaystyle{ (S,\bar{S}) }[/math] be an arbitrary [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut. Then
[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],
that is, the value of any flow is no greater than the value of any cut.
Proof.
By the definition of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, [math]\displaystyle{ s\in S }[/math] and [math]\displaystyle{ t\not\in S }[/math].

Due to the conservation of flow,

[math]\displaystyle{ \sum_{u\in S}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}+\sum_{u\in S\setminus\{s\}}\left(\sum_{v:(u,v)\in E}f_{uv}-\sum_{v:(v,u)\in E}f_{vu}\right)=\sum_{v:(s,v)\in E}f_{sv}\,. }[/math]

On the other hand, summing flow over edges,

[math]\displaystyle{ \sum_{v\in S}\left(\sum_{u:(u,v)\in E}f_{uv}-\sum_{u:(v,u)\in E}f_{vu}\right)=\sum_{u\in S,v\in S\atop (u,v)\in E}\left(f_{uv}-f_{uv}\right)+\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\,. }[/math]

Therefore,

[math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}=\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu}\le\sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}\le \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv}\,, }[/math]
[math]\displaystyle{ \square }[/math]

Augmenting paths

Definition (Augmenting path)
Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. An augmenting path to [math]\displaystyle{ u_k }[/math] is a sequence of distinct vertices [math]\displaystyle{ P=(u_0,u_1,\cdots, u_k) }[/math], such that
  • [math]\displaystyle{ u_0=s\, }[/math];
and each pair of consecutive vertices [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] in [math]\displaystyle{ P }[/math] corresponds to either a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] or a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math], and
  • [math]\displaystyle{ f(u_i,u_{i+1})\lt c(u_i,u_{i+1})\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a forward edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math], and
  • [math]\displaystyle{ f(u_{i+1},u_i)\gt 0\, }[/math] when [math]\displaystyle{ u_{i}u_{i+1}\, }[/math] corresponds to a reverse edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math].
If [math]\displaystyle{ u_k=t\, }[/math], we simply call [math]\displaystyle{ P }[/math] an augmenting path.

Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. Suppose there is an augmenting path [math]\displaystyle{ P=u_0u_1\cdots u_k }[/math], where [math]\displaystyle{ u_0=s }[/math] and [math]\displaystyle{ u_k=t }[/math]. Let [math]\displaystyle{ \epsilon\gt 0 }[/math] be a positive constant satisfying

  • [math]\displaystyle{ \epsilon \le c(u_{i},u_{i+1})-f(u_i,u_{i+1}) }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math];
  • [math]\displaystyle{ \epsilon \le f(u_{i+1},u_i) }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math].

Due to the definition of augmenting path, we can always find such a positive [math]\displaystyle{ \epsilon }[/math].

Increase [math]\displaystyle{ f(u_i,u_{i+1}) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all forward edges [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] in [math]\displaystyle{ P }[/math] and decrease [math]\displaystyle{ f(u_{i+1},u_i) }[/math] by [math]\displaystyle{ \epsilon }[/math] for all reverse edges [math]\displaystyle{ (u_{i+1},u_i)\in E }[/math] in [math]\displaystyle{ P }[/math]. Denote the modified flow by [math]\displaystyle{ f' }[/math]. It can be verified that [math]\displaystyle{ f' }[/math] satisfies the capacity constraint and conservation constraint thus is still a valid flow. On the other hand, the value of the new flow [math]\displaystyle{ f' }[/math]

[math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv}'=\epsilon+\sum_{v:(s,v)\in E}f_{sv}\gt \sum_{v:(s,v)\in E}f_{sv} }[/math].

Therefore, the value of the flow can be "augmented" by adjusting the flow on the augmenting path. This immediately implies that if a flow is maximum, then there is no augmenting path. Surprisingly, the converse is also true, thus maximum flows are "characterized" by augmenting paths.

Lemma
A flow [math]\displaystyle{ f }[/math] is maximum if and only if there are no augmenting paths.
Proof.
We have already proved the "only if" direction above. Now we prove the "if" direction.

Let [math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math]. Clearly [math]\displaystyle{ s\in S }[/math], and since there is no augmenting path [math]\displaystyle{ t\not\in S }[/math]. Therefore, [math]\displaystyle{ (S,\bar{S}) }[/math] defines an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.

We claim that

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],

that is, the value of flow [math]\displaystyle{ f }[/math] approach the value of the cut [math]\displaystyle{ (S,\bar{S}) }[/math] defined above. By the above lemma, this will imply that the current flow [math]\displaystyle{ f }[/math] is maximum.

To prove this claim, we first observe that

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} }[/math].

This identity is implied by the flow conservation constraint, and holds for any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut [math]\displaystyle{ (S,\bar{S}) }[/math].

We then claim that

  • [math]\displaystyle{ f_{uv}=c_{uv} }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (u,v)\in E }[/math]; and
  • [math]\displaystyle{ f_{vu}=0 }[/math] for all [math]\displaystyle{ u\in S,v\not\in S, (v,u)\in E }[/math].

If otherwise, then the augmenting path to [math]\displaystyle{ u }[/math] apending [math]\displaystyle{ uv }[/math] becomes a new augmenting path to [math]\displaystyle{ v }[/math], which contradicts that [math]\displaystyle{ S }[/math] includes all vertices to which there exist augmenting paths.

Therefore,

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}f_{uv}-\sum_{u\in S,v\not\in S\atop (v,u)\in E}f_{vu} = \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math].

As discussed above, this proves the theorem.

[math]\displaystyle{ \square }[/math]

Max-Flow Min-Cut

The max-flow min-cut theorem

Max-Flow Min-Cut Theorem
In a flow network, the maximum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.
Proof.

Let [math]\displaystyle{ f }[/math] be a flow with maximum value, so there is no augmenting path.

Again, let

[math]\displaystyle{ S=\{u\in V\mid \exists\text{an augmenting path to }u\} }[/math].

As proved above, [math]\displaystyle{ (S,\bar{S}) }[/math] forms an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, and

[math]\displaystyle{ \sum_{v:(s,v)}f_{sv}= \sum_{u\in S,v\not\in S\atop (u,v)\in E}c_{uv} }[/math],

that is, the value of flow [math]\displaystyle{ f }[/math] equals the value of cut [math]\displaystyle{ (S,\bar{S}) }[/math].

Since we know that all [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flows are not greater than any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, the value of flow [math]\displaystyle{ f }[/math] equals the minimum value of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut.

[math]\displaystyle{ \square }[/math]

Flow Integrality Theorem

Flow Integrality Theorem
Let [math]\displaystyle{ (G,c,s,t) }[/math] be a flow network with integral capacity [math]\displaystyle{ c }[/math]. There exists an integral flow which is maximum.
Proof.

Let [math]\displaystyle{ f }[/math] be an integral flow of maximum value. If there is an augmenting path, since both [math]\displaystyle{ c }[/math] and [math]\displaystyle{ f }[/math] are integral, a new flow can be constructed of value 1+the value of [math]\displaystyle{ f }[/math], contradicting that [math]\displaystyle{ f }[/math] is maximum over all integral flows. Therefore, there is no augmenting path, which means that [math]\displaystyle{ f }[/math] is maximum over all flows, integral or not.

[math]\displaystyle{ \square }[/math]

Applications: Menger's theorem

Given an undirected graph [math]\displaystyle{ G(V,E) }[/math] and two distinct vertices [math]\displaystyle{ s,t\in V }[/math], a set of edges [math]\displaystyle{ C\subseteq E }[/math] is called an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut, if deleting edges in [math]\displaystyle{ C }[/math] disconnects [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].

A simple path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is called an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] path. Two paths are said to be edge-disjoint if they do not share any edge.

Theorem (Menger 1927)
Let [math]\displaystyle{ G(V,E) }[/math] be an arbitrary undirected graph and [math]\displaystyle{ s,t\in V }[/math] be two distinct vertices. The minimum size of any [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut equals the maximum number of edge-disjoint [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths.
Proof.

Construct a directed graph [math]\displaystyle{ G'(V,E') }[/math] from [math]\displaystyle{ G(V,E) }[/math] as follows: replace every undirected edge [math]\displaystyle{ uv\in E }[/math] that [math]\displaystyle{ s,t\not\in\{u,v\} }[/math] by two directed edges [math]\displaystyle{ (u,v) }[/math] and [math]\displaystyle{ (v,u) }[/math]; replace every undirected edge [math]\displaystyle{ sv\in E }[/math] by [math]\displaystyle{ (s,v) }[/math], and very undirected edge [math]\displaystyle{ vt\in E }[/math] by [math]\displaystyle{ (v,t) }[/math]. Then assign every directed edge with capacity 1.

It is easy to verify that in the flow network constructed as above, the followings hold:

  • An integral [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow corresponds to a set of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths in the undirected graph [math]\displaystyle{ G }[/math], where the value of the flow is the number of [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] paths.
  • An [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in the flow network corresponds to an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in the undirected graph [math]\displaystyle{ G }[/math] with the same value.

The Menger's theorem follows as a direct consequence of the max-flow min-cut theorem.

[math]\displaystyle{ \square }[/math]

Applications: König-Egerváry theorem

Let [math]\displaystyle{ G(V,E) }[/math] be a graph. An edge set [math]\displaystyle{ M\subseteq E }[/math] is called a matching if no edge in [math]\displaystyle{ M }[/math] shares any vertex. A vertex set [math]\displaystyle{ C\subseteq V }[/math] is called a vertex cover if for any edge [math]\displaystyle{ uv\in E }[/math], either [math]\displaystyle{ u\in C }[/math] or [math]\displaystyle{ v\in C }[/math].

Theorem (König 1936)
In any bipartite graph [math]\displaystyle{ G(V_1,V_2,E) }[/math], the size of a maximum matching equals the size of a minimum vertex cover.

We now show how a reduction of bipartite matchings to flows.

Construct a flow network [math]\displaystyle{ (G'(V,E'),c,s,t) }[/math] as follows:

  • [math]\displaystyle{ V=V_1\cup V_2\cup\{s,t\} }[/math] where [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are two new vertices.
  • For ever [math]\displaystyle{ uv\in E }[/math], add [math]\displaystyle{ (u,v) }[/math] to [math]\displaystyle{ E' }[/math]; for every [math]\displaystyle{ u\in V_1 }[/math], add [math]\displaystyle{ (s,u) }[/math] to [math]\displaystyle{ E' }[/math]; and for every [math]\displaystyle{ v\in V_2 }[/math], add [math]\displaystyle{ (v,t) }[/math] to [math]\displaystyle{ E' }[/math].
  • Let [math]\displaystyle{ c_{su}=1 }[/math] for every [math]\displaystyle{ u\in V_1 }[/math] and [math]\displaystyle{ c_{vt}=1 }[/math] for every [math]\displaystyle{ v\in V_2 }[/math]. Let [math]\displaystyle{ c_{uv}=\infty }[/math] for every bipartite edges [math]\displaystyle{ (u,v) }[/math].
Lemma
The size of a maximum matching in [math]\displaystyle{ G }[/math] is equal to the value of a maximum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow in [math]\displaystyle{ G' }[/math].
Proof.

Given an integral [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G' }[/math], let [math]\displaystyle{ M=\{uv\in E\mid f_{uv}=1\} }[/math]. Then [math]\displaystyle{ M }[/math] must be a matching since for every [math]\displaystyle{ u\in V_1 }[/math]. To see this, observe that there is at most one [math]\displaystyle{ v\in V_2 }[/math] that [math]\displaystyle{ f_{uv}=1 }[/math], because of that [math]\displaystyle{ f_{su}\le c_{su}=1 }[/math] and conservation of flows. The same holds for vertices in [math]\displaystyle{ V_2 }[/math] by the same argument. Therefore, each flow corresponds to a matching.

Given a matching [math]\displaystyle{ M }[/math] in bipartite graph [math]\displaystyle{ G }[/math], define an integral flow [math]\displaystyle{ f }[/math] as such: for [math]\displaystyle{ uv\in E }[/math], [math]\displaystyle{ f_{uv}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] and [math]\displaystyle{ f_{uv}=0 }[/math] if otherwise; for [math]\displaystyle{ u\in V_1 }[/math], [math]\displaystyle{ f_{su}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] for some [math]\displaystyle{ v }[/math] and [math]\displaystyle{ f_{su}=0 }[/math] if otherwise; for [math]\displaystyle{ v\in V_2 }[/math], [math]\displaystyle{ f_{vt}=1 }[/math] if [math]\displaystyle{ uv\in M }[/math] for some [math]\displaystyle{ u }[/math] and [math]\displaystyle{ f_{vt}=0 }[/math] if otherwise.

It is easy to check that [math]\displaystyle{ f }[/math] is valid [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow in [math]\displaystyle{ G' }[/math]. Therefore, there is an one-one correspondence between flows in [math]\displaystyle{ G' }[/math] and matchings in [math]\displaystyle{ G }[/math]. The lemma follows naturally.

[math]\displaystyle{ \square }[/math]

We then establish a correspondence between [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cuts in [math]\displaystyle{ G' }[/math] and vertex covers in [math]\displaystyle{ G }[/math].

Suppose [math]\displaystyle{ (S,\bar{S}) }[/math] is an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in [math]\displaystyle{ G' }[/math].

Lemma
The size of a minimum vertex cover in [math]\displaystyle{ G }[/math] is equal to the value of a minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut in [math]\displaystyle{ G' }[/math].
Proof.

Let [math]\displaystyle{ (S,\bar{S}) }[/math] be an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut of minimum capacity in [math]\displaystyle{ G' }[/math]. Then [math]\displaystyle{ \sum_{u\in S, v\not\in S\atop (u,v)\in E'}c_{uv} }[/math] must be finite since [math]\displaystyle{ S=\{s\} }[/math] gives us an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut whose capacity is [math]\displaystyle{ |V_1| }[/math] which is finite. Therefore, no edge [math]\displaystyle{ uv\in E }[/math] has [math]\displaystyle{ u\in V_1\cap S }[/math] and [math]\displaystyle{ v\in V_2\setminus S }[/math], i.e., for all [math]\displaystyle{ uv\in E }[/math], either [math]\displaystyle{ u\in V_1\setminus S }[/math] or [math]\displaystyle{ v\in V_2\cap S }[/math]. Therefore, [math]\displaystyle{ (V_1\setminus S)\cup(V_2\cap S) }[/math] is a vertex cover in [math]\displaystyle{ G }[/math], whose size is

[math]\displaystyle{ |(V_1\setminus S)\cup(V_2\cap S)|=|V_1\setminus S|+|V_2\cap S|=\sum_{u\in V_1\setminus S}c_{su}+\sum_{v\in V_2\cap S}c_{ut}=\sum_{u\in S,v\not\in S\atop (u,v)\in E'}c_{uv} }[/math].

The last term is the capacity of the minimum [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] cut [math]\displaystyle{ (S,\bar{S}) }[/math].

[math]\displaystyle{ \square }[/math]

The König-Egerváry theorem then holds as a consequence of the max-flow min-cut theorem.

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=组合数学_(Fall_2011)/Ramsey_theory&oldid=4930"