imported>WikiSysop |
imported>WikiSysop |
| Line 1: |
Line 1: |
| = Probabilistic Method = | | =Graph Colorings= |
| The probabilistic method provides another way of proving the existence of objects: instead of explicitly constructing an object, we define a probability space of objects in which the probability is positive that a randomly selected object has the required property.
| | A '''proper coloring''' of a graph <math>G(V,E)</math> is a mapping <math>f:V\rightarrow[q]</math> for some integer <math>q</math>, satisfying that <math>f(u)\neq f(v)</math> for all <math>uv\in E</math>. |
|
| |
|
| The basic principle of the probabilistic method is very simple, and can be stated in intuitive ways:
| | We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics. |
| *If an object chosen randomly from a universe satisfies a property with positive probability, then there must be an object in the universe that satisfies that property.
| |
| :For example, for a ball(the object) randomly chosen from a box(the universe) of balls, if the probability that the chosen ball is blue(the property) is >0, then there must be a blue ball in the box.
| |
| *Any random variable assumes at least one value that is no smaller than its expectation, and at least one value that is no greater than the expectation.
| |
| :For example, if we know the average height of the students in the class is <math>\ell</math>, then we know there is a students whose height is at least <math>\ell</math>, and there is a student whose height is at most <math>\ell</math>.
| |
|
| |
|
| Although the idea of the probabilistic method is simple, it provides us a powerful tool for existential proof.
| | Let's first consider the decision version of the problem. That is, given as input a graph <math>G(V,E)</math>, decide whether there exists a proper <math>q</math>-coloring of <math>G</math>. Denote by <math>\Delta</math> the maximum degree of <math>G</math>. |
| | * If <math>q\ge \Delta+1</math>, there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm. |
| | * If <math>q=\Delta</math>, <math>G</math> has a proper coloring unless it contains a <math>(\Delta+1)</math>-clique or it is an odd cycle. ([http://en.wikipedia.org/wiki/Brooks'_theorem Brooks Theorem]) |
| | * If <math>q<\Delta</math>, the problem is NP-hard. |
|
| |
|
| ===Ramsey number=== | | Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when <math>q<\Delta</math>. The decision problem for the case <math>q=\Delta</math> is also nontrivial. Thus people are interested only in the case when <math>q\ge \Delta+1</math>. |
|
| |
|
| Recall the Ramsey theorem which states that in a meeting of at least six people, there are either three people knowing each other or three people not knowing each other. In graph theoretical terms, this means that no matter how we color the edges of <math>K_6</math> (the complete graph on six vertices), there must be a '''monochromatic''' <math>K_3</math> (a triangle whose edges have the same color).
| | The following is a natural Markov chain for sampling proper colorings. |
|
| |
|
| Generally, the '''Ramsey number''' <math>R(k,\ell)</math> is the smallest integer <math>n</math> such that in any two-coloring of the edges of a complete graph on <math>n</math> vertices <math>K_n</math> by red and blue, either there is a red <math>K_k</math> or there is a blue <math>K_\ell</math>.
| | {{Theorem|Markov Chain for Graph Coloring| |
| | | :Start with a proper coloring of <math>G(V,E)</math>. At each step: |
| Ramsey showed in 1929 that <math>R(k,\ell)</math> is finite for any <math>k</math> and <math>\ell</math>. It is extremely hard to compute the exact value of <math>R(k,\ell)</math>. Here we give a lower bound of <math>R(k,k)</math> by the probabilistic method.
| | # Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random. |
| | | # Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise. |
| {{Theorem | |
| |Theorem (Erdős 1947)| | |
| :If <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math> then it is possible to color the edges of <math>K_n</math> with two colors so that there is no monochromatic <math>K_k</math> subgraph. | |
| }}
| |
| {{Proof| Consider a random two-coloring of edges of <math>K_n</math> obtained as follows:
| |
| * For each edge of <math>K_n</math>, independently flip a fair coin to decide the color of the edge.
| |
| | |
| For any fixed set <math>S</math> of <math>k</math> vertices, let <math>\mathcal{E}_S</math> be the event that the <math>K_k</math> subgraph induced by <math>S</math> is monochromatic. There are <math>{k\choose 2}</math> many edges in <math>K_k</math>, therefore
| |
| :<math>\Pr[\mathcal{E}_S]=2\cdot 2^{-{k\choose 2}}=2^{1-{k\choose 2}}.</math>
| |
| | |
| Since there are <math>{n\choose k}</math> possible choices of <math>S</math>, by the union bound
| |
| :<math>
| |
| \Pr[\exists S, \mathcal{E}_S]\le {n\choose k}\cdot\Pr[\mathcal{E}_S]={n\choose k}\cdot 2^{1-{k\choose 2}}.
| |
| </math>
| |
| Due to the assumption, <math>{n\choose k}\cdot 2^{1-{k\choose 2}}<1</math>, thus there exists a two coloring that none of <math>\mathcal{E}_S</math> occurs, which means there is no monochromatic <math>K_k</math> subgraph.
| |
| }}
| |
| | |
| For <math>k\ge 3</math> and we take <math>n=\lfloor2^{k/2}\rfloor</math>, then
| |
| :<math>
| |
| \begin{align}
| |
| {n\choose k}\cdot 2^{1-{k\choose 2}}
| |
| &<
| |
| \frac{n^k}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
| |
| &\le
| |
| \frac{2^{k^2/2}}{k!}\cdot\frac{2^{1+\frac{k}{2}}}{2^{k^2/2}}\\
| |
| &=
| |
| \frac{2^{1+\frac{k}{2}}}{k!}\\
| |
| &<1.
| |
| \end{align}
| |
| </math>
| |
| By the above theorem, there exists a two-coloring of <math>K_n</math> that there is no monochromatic <math>K_k</math>. Therefore, the Ramsey number <math>R(k,k)>\lfloor2^{k/2}\rfloor</math> for all <math>k\ge 3</math>.
| |
| | |
| Note that for sufficiently large <math>k</math>, if <math>n= \lfloor 2^{k/2}\rfloor</math>, then the probability that there exists a monochromatic <math>K_k</math> is bounded by
| |
| :<math> | |
| {n\choose k}\cdot 2^{1-{k\choose 2}}
| |
| <
| |
| \frac{2^{1+\frac{k}{2}}}{k!}
| |
| \ll 1,
| |
| </math>
| |
| which means that a random two-coloring of <math>K_n</math> is very likely not to contain a monochromatic <math>K_{2\log n}</math>. This gives us a very simple randomized algorithm for finding a two-coloring of <math>K_n</math> without monochromatic <math>K_{2\log n}</math>.
| |
| | |
| = Averaging Principle =
| |
| | |
| ===Maximum cut===
| |
| | |
| Given an undirected graph <math>G(V,E)</math>, a set <math>C</math> of edges of <math>G</math> is called a '''cut''' if <math>G</math> is disconnected after removing the edges in <math>C</math>. We can represent a cut by <math>c(S,T)</math> where <math>(S,T)</math> is a bipartition of the vertex set <math>V</math>, and <math>c(S,T)=\{uv\in E\mid u\in S,v\in T\}</math> is the set of edges crossing between <math>S</math> and <math>T</math>.
| |
| | |
| We have seen how to compute min-cut: either by deterministic max-flow algorithm, or by Karger's randomized algorithm. On the other hand, max-cut is hard to compute, because it is '''NP-complete'''. Actually, the weighted version of max-cut is among the [http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems Karp's 21 NP-complete problems].
| |
| | |
| We now show by the probabilistic method that a max-cut always has at least half the edges.
| |
| | |
| {{Theorem
| |
| |Theorem|
| |
| :Given an undirected graph <math>G</math> with <math>n</math> vertices and <math>m</math> edges, there is a cut of size at least <math>\frac{m}{2}</math>.
| |
| }} | | }} |
| {{Proof| Enumerate the vertices in an arbitrary order. Partition the vertex set <math>V</math> into two disjoint sets <math>S</math> and <math>T</math> as follows.
| |
| :For each vertex <math>v\in V</math>,
| |
| :* independently choose one of <math>S</math> and <math>T</math> with equal probability, and let <math>v</math> join the chosen set.
| |
|
| |
|
| For each vertex <math>v\in V</math>, let <math>X_v\in\{S,T\}</math> be the random variable which represents the set that <math>v</math> joins. For each edge <math>uv\in E</math>, let <math>Y_{uv}</math> be the 0-1 random variable which indicates whether <math>uv</math> crosses between <math>S</math> and <math>T</math>. Clearly, | | For a fixed graph <math>G(V,E)</math>, the state space of the above Markov chain is the set of all proper colorings of <math>G</math> with <math>q</math> colors. |
| :<math>
| |
| \Pr[Y_{uv}=1]=\Pr[X_u\neq X_v]=\frac{1}{2}.
| |
| </math>
| |
|
| |
|
| The size of <math>c(S,T)</math> is given by <math>Y=\sum_{uv\in E}Y_{uv}</math>. By the linearity of expectation,
| | {{Theorem|Lemma| |
| :<math>
| | The followings hold for the above Markov chain. |
| \mathbf{E}[Y]=\sum_{uv\in E}\mathbf{E}[Y_{uv}]=\sum_{uv\in E}\Pr[Y_{uv}=1]=\frac{m}{2}.
| | # Aperiodic. |
| </math> | | # The transition matrix is symmetric. |
| Therefore, there exist a bipartition <math>(S,T)</math> of <math>V</math> such that <math>|c(S,T)|\ge\frac{m}{2}</math>, i.e. there exists a cut of <math>G</math> which contains at least <math>\frac{m}{2}</math> edges.
| | # Irreducible if <math>q\ge \Delta+2</math>. |
| }} | | }} |
|
| |
|
| =Alternations=
| | The followings are the two most important conjectures regarding the problem. |
| | | {{Theorem|Conjecture| |
| | | #The simple Markov chain defined above has mixing time <math>O(n\ln n)</math> whenever <math>q\ge\Delta+2</math>. |
| ===Independent sets===
| | # Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>. |
| An independent set of a graph is a set of vertices with no edges between them. The following theorem gives a lower bound on the size of the largest independent set.
| |
| {{Theorem | |
| |Theorem| | |
| :Let <math>G(V,E)</math> be a graph on <math>n</math> vertices with <math>m</math> edges. Then <math>G</math> has an independent set with at least <math>\frac{n^2}{4m}</math> vertices.
| |
| }} | | }} |
| {{Proof| Let <math>S</math> be a set of vertices constructed as follows:
| |
| :For each vertex <math>v\in V</math>:
| |
| :* <math>v</math> is included in <math>S</math> independently with probability <math>p</math>,
| |
| <math>p</math> to be determined.
| |
|
| |
|
| Let <math>X=|S|</math>. It is obvious that <math>\mathbf{E}[X]=np</math>.
| | These two conjectures are still open. People approach them by relax the requirement for the number of colors <math>q</math>. Intuitively, the larger the <math>q</math> is, the more freedom we have, the less dependency are there between non-adjacent vertices. |
|
| |
|
| For each edge <math>e\in E</math>, let <math>Y_{e}</math> be the random variable which indicates whether both endpoints of <math></math> are in <math>S</math>.
| | =Coupling: <math>q\ge 4\Delta+1</math>= |
| :<math>
| |
| \mathbf{E}[Y_{uv}]=\Pr[u\in S\wedge v\in S]=p^2.
| |
| </math>
| |
| Let <math>Y</math> be the number of edges in the subgraph of <math>G</math> induced by <math>S</math>. It holds that <math>Y=\sum_{e\in E}Y_e</math>. By linearity of expectation,
| |
| :<math>\mathbf{E}[Y]=\sum_{e\in E}\mathbf{E}[Y_e]=mp^2</math>. | |
| | |
| Note that although <math>S</math> is not necessary an independent set, it can be modified to one if for each edge <math>e</math> of the induced subgraph <math>G(S)</math>, we delete one of the endpoint of <math>e</math> from <math>S</math>. Let <math>S^*</math> be the resulting set. It is obvious that <math>S^*</math> is an independent set since there is no edge left in the induced subgraph <math>G(S^*)</math>.
| |
| | |
| Since there are <math>Y</math> edges in <math>G(S)</math>, there are at most <math>Y</math> vertices in <math>S</math> are deleted to make it become <math>S^*</math>. Therefore, <math>|S^*|\ge X-Y</math>. By linearity of expectation,
| |
| :<math>
| |
| \mathbf{E}[|S^*|]\ge\mathbf{E}[X-Y]=\mathbf{E}[X]-\mathbf{E}[Y]=np-mp^2.
| |
| </math>
| |
| The expectation is maximized when <math>p=\frac{n}{2m}</math>, thus
| |
| :<math>
| |
| \mathbf{E}[|S^*|]\ge n\cdot\frac{n}{2m}-m\left(\frac{n}{2m}\right)^2=\frac{n^2}{4m}.
| |
| </math>
| |
| There exists an independent set which contains at least <math>\frac{n^2}{4m}</math> vertices.
| |
| }}
| |
| | |
| The proof actually propose a randomized algorithm for constructing large independent set:
| |
| | |
| {{Theorem
| |
| |Algorithm|
| |
| Given a graph on <math>n</math> vertices with <math>m</math> edges, let <math>d=\frac{2m}{n}</math> be the average degree.
| |
| #For each vertex <math>v\in V</math>, <math>v</math> is included in <math>S</math> independently with probability <math>\frac{1}{d}</math>.
| |
| #For each remaining edge in the induced subgraph <math>G(S)</math>, remove one of the endpoints from <math>S</math>.
| |
| }}
| |
|
| |
|
| Let <math>S^*</math> be the resulting set. We have shown that <math>S^*</math> is an independent set and <math>\mathbf{E}[|S^*|]\ge\frac{n^2}{4m}</math>.
| | =Path Coupling: <math>q\ge 2\Delta+1</math> = |
Graph Colorings
A proper coloring of a graph [math]\displaystyle{ G(V,E) }[/math] is a mapping [math]\displaystyle{ f:V\rightarrow[q] }[/math] for some integer [math]\displaystyle{ q }[/math], satisfying that [math]\displaystyle{ f(u)\neq f(v) }[/math] for all [math]\displaystyle{ uv\in E }[/math].
We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.
Let's first consider the decision version of the problem. That is, given as input a graph [math]\displaystyle{ G(V,E) }[/math], decide whether there exists a proper [math]\displaystyle{ q }[/math]-coloring of [math]\displaystyle{ G }[/math]. Denote by [math]\displaystyle{ \Delta }[/math] the maximum degree of [math]\displaystyle{ G }[/math].
- If [math]\displaystyle{ q\ge \Delta+1 }[/math], there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
- If [math]\displaystyle{ q=\Delta }[/math], [math]\displaystyle{ G }[/math] has a proper coloring unless it contains a [math]\displaystyle{ (\Delta+1) }[/math]-clique or it is an odd cycle. (Brooks Theorem)
- If [math]\displaystyle{ q\lt \Delta }[/math], the problem is NP-hard.
Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when [math]\displaystyle{ q\lt \Delta }[/math]. The decision problem for the case [math]\displaystyle{ q=\Delta }[/math] is also nontrivial. Thus people are interested only in the case when [math]\displaystyle{ q\ge \Delta+1 }[/math].
The following is a natural Markov chain for sampling proper colorings.
| Markov Chain for Graph Coloring
|
- Start with a proper coloring of [math]\displaystyle{ G(V,E) }[/math]. At each step:
- Pick a vertex [math]\displaystyle{ v\in V }[/math] and a color [math]\displaystyle{ c\in[q] }[/math] uniformly at random.
- Change the color of [math]\displaystyle{ v }[/math] to [math]\displaystyle{ c }[/math] if the resulting coloring is proper; do nothing if otherwise.
|
For a fixed graph [math]\displaystyle{ G(V,E) }[/math], the state space of the above Markov chain is the set of all proper colorings of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ q }[/math] colors.
| Lemma
|
|
The followings hold for the above Markov chain.
- Aperiodic.
- The transition matrix is symmetric.
- Irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math].
|
The followings are the two most important conjectures regarding the problem.
| Conjecture
|
- The simple Markov chain defined above has mixing time [math]\displaystyle{ O(n\ln n) }[/math] whenever [math]\displaystyle{ q\ge\Delta+2 }[/math].
- Random sampling of proper graph colorings can be done in polynomial time whenever [math]\displaystyle{ q\ge\Delta+1 }[/math].
|
These two conjectures are still open. People approach them by relax the requirement for the number of colors [math]\displaystyle{ q }[/math]. Intuitively, the larger the [math]\displaystyle{ q }[/math] is, the more freedom we have, the less dependency are there between non-adjacent vertices.
Coupling: [math]\displaystyle{ q\ge 4\Delta+1 }[/math]
Path Coupling: [math]\displaystyle{ q\ge 2\Delta+1 }[/math]