imported>WikiSysop |
imported>Zabshk |
| Line 1: |
Line 1: |
| == Ramsey's Theorem ==
| | {{Orphan|date=December 2010}} |
| === Ramsey's theorem for graph ===
| | '''Graham's number''' is a very, very big [[natural number]] that was defined by a man named Ronald Graham. Graham was solving a problem in an area of mathematics called [[Ramsey theory]]. He proved that the answer to his problem was smaller than Graham's number. |
| {{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)|
| | Graham's number is one of the biggest numbers ever used in a [[mathematical proof]]. Even if every digit in Graham's number were written in the tiniest writing possible, it would still be too big to fit in the [[observable universe]]. |
| :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:
| |
| :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>.
| |
| }}
| |
|
| |
|
| {{Theorem|Lemma (the "mixing color" trick)|
| | ==Context== |
| :<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.
| | Ramsey theory is an area of mathematics that asks questions like the following: |
| }}
| |
|
| |
|
| === Ramsey number ===
| | {{quote|<p>Suppose we draw some number of points, and connect every pair of points by a line. Some lines are blue and some are red. Can we always find 3 points for which the 3 lines connecting them are all the same color?}} |
| 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:
| | It turns out that for this simple problem, the answer is "yes" when we have 6 or more points, no matter how the lines are colored. But when we have 5 points or fewer, we can color the lines so that the answer is "no". |
| :"''<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
| | Graham's number comes from a variation on this question. |
| :<math>\begin{align}
| |
| R(k,1) &=R(1,\ell)=1\\
| |
| R(k,\ell) &\le R(k,\ell-1)+R(k-1,\ell).
| |
| \end{align}</math>
| |
|
| |
|
| From this recursion, we can deduce an upper bound for the Ramsey number.
| | {{quote|<p>Once again, say we have some points, but now they are the corners of an ''n''-dimensional [[hypercube]]. They are still all connected by blue and red lines. For any 4 points, there are 6 lines connecting them. Can we find 4 points that all lie on one [[Plane (mathematics)|plane]], and the 6 lines connecting them are all the same color?}} |
| {{Theorem|Theorem| | |
| :<math>R(k,\ell)\le{k+\ell-2\choose k-1}</math>.
| |
| }}
| |
| {{Proof|It is easy to verify the bound by induction.
| |
| }} | |
|
| |
|
| ------
| | By asking that the 4 points lie on a plane, we have made the problem much harder. We would like to know: for what values of ''n'' is the answer "no" (for some way of coloring the lines), and for what values of ''n'' is it "yes" (for all ways of coloring the lines)? But this problem has not been completely solved yet. |
|
| |
|
| The following theorem is due to Spencer in 1975, which is the best known lower bound for diagonal Ramsey number.
| | In 1971, Ronald Graham and B. L. Rothschild found a partial answer to this problem. They showed that for ''n''=6, the answer is "no". But when ''n'' is very large, as large as Graham's number or larger, the answer is "yes". |
|
| |
|
| {{Theorem|Theorem (Spencer 1975)|
| | One of the reasons this partial answer is important is that it means that the answer is eventually "yes" for at least some large ''n''. Before 1971, we didn't know even that much. |
| :<math>R(k,k)\ge Ck2^{k/2}</math> for some constant <math>C>0</math>.
| |
| }}
| |
|
| |
|
| Its proof uses the Lovász local lemma in the probabilistic method.
| | ==Definition== |
| {{Theorem
| |
| |Lovász Local Lemma (symmetric case)|
| |
| :Let <math>A_1,A_2,\ldots,A_n</math> be a set of events, and assume that the following hold:
| |
| :#for all <math>1\le i\le n</math>, <math>\Pr[A_i]\le p</math>;
| |
| :# each event <math>A_i</math> is independent of all but at most <math>d</math> other events, and
| |
| :::<math>ep(d+1)\le 1</math>.
| |
| :Then
| |
| ::<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.
| | Graham's number is not only too big to write down all of its digits, it is too big even to write in [[scientific notation]]. In order to be able to write it down, we have to use [[Knuth's up-arrow notation]]. |
| {{Proof|
| |
| 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.
| |
|
| |
|
| 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>.
| | We will write down a [[sequence]] of numbers that we will call '''g1''', '''g2''', '''g3''', and so on. Each one will be used in an equation to find the next. '''g64 is''' Graham's number. |
|
| |
|
| 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>.
| | First, here are some examples of up-arrows: |
|
| |
|
| Take <math>n=Ck2^{k/2}</math> for some appropriate constant <math>C>0</math>.
| | * <math>3\uparrow3</math> is 3x3x3 which equals 27. An arrow between two numbers just means the first number multiplied by itself the second number of times. |
| :<math>
| | * You can think of <math>3 \uparrow \uparrow 3</math> as <math>3 \uparrow (3 \uparrow 3)</math> because two arrows between numbers A and B just means A written down a B number of times with an arrow in between each A. Because we know what single arrows are, <math>3\uparrow(3\uparrow3)</math> is 3 multiplied by itself <math>3\uparrow3</math> times and we know <math>3\uparrow3 |
| \begin{align} | | </math> is twenty-seven. So <math>3\uparrow\uparrow3</math> is 3x3x3x3x....x3x3, in total 27 times. That equals 7625597484987. |
| \mathrm{e}p(d+1) | | * <math>3 \uparrow \uparrow \uparrow 3</math> is <math>3 \uparrow \uparrow (3 \uparrow \uparrow 3)</math> and we know <math>3\uparrow\uparrow3</math> is 7625597484987. So <math>3\uparrow\uparrow(3\uparrow\uparrow3)</math> is <math>3\uparrow \uparrow 7625597484987</math>. That can also be written as <math>3\uparrow(3\uparrow(3\uparrow(3\uparrow . . .(3\uparrow(3\uparrow(3\uparrow3)</math> with a total of 7625597484987 3s. This number is so huge, its digits, even written very small, could fill up the observable universe and beyond. |
| &\le \mathrm{e}2^{1-{k\choose 2}}\left({k\choose 2}{n\choose k-2}+1\right)\\
| | ** Although this number may already be beyond comprehension, this is barely the start of this giant number. |
| &\le 2^{3-{k\choose 2}}{k\choose 2}{n\choose k-2}\\
| | * The next step like this is <math>3 \uparrow \uparrow \uparrow \uparrow 3</math> or <math>3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3)</math>. This is the number we will call '''g1'''. |
| &\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>.
| |
| }}
| |
|
| |
|
| {{Theorem|Theorem|
| | After that, '''g2''' is equal to <math>3\uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow 3</math>; the number of arrows in this number is '''g1'''. |
| :<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"
| | '''g3''' is equal to <math>3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3</math>, where the number of arrows is '''g2'''. |
| ! ''<math>k</math>'',''<math>l</math>''
| |
| ! 1
| |
| ! 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 ===
| | We keep going in this way. We stop when we define '''g64''' to be <math>3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3</math>, where the number of arrows is '''g63'''. |
| {{Theorem|Ramsey's Theorem (hypergraph, multicolor)|
| |
| :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:
| |
| :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>
| | This is Graham's number. |
|
| |
|
| {{Theorem|Lemma (the "mixing color" trick)|
| | ==Related pages== |
| :<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>
| | * [[Knuth's up-arrow notation]] |
| }}
| |
|
| |
|
| 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.
| | [[Category:Mathematics]] |
| | | [[Category:Hyperoperations]] |
| {{Theorem|Lemma|
| | [[Category:Integers]] |
| :<math>R_t(k,\ell)\le R_{t-1}(R_t(k-1,\ell),R_t(k,\ell-1))+1</math>
| |
| }}
| |
| {{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:{[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>.
| |
| | |
| 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
| |
| :<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 ==
| |
| === The "Happy Ending" problem ===
| |
| {{Theorem|The happy ending problem|
| |
| :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.
| |
| }}
| |
| 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.
| |
| | |
| {{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>.
| |
| | |
| 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,
| |
| :<math>\triangle_{abc}=\triangle_{abd}\cup\triangle_{acd}\cup\triangle_{bcd}\cup\{d\}</math>,
| |
| 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.
| |
| }}
| |
| | |
| === Yao's lower bound on implicit data structures ===
| |
| {{Theorem|Lemma|
| |
| :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>.
| |
| :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.
| |
| }}
| |
| {{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.
| |
| | |
| 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>.
| |
| | |
| 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:
| |
| :<math>
| |
| \begin{align}
| |
| T[k]=
| |
| \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>.
| |
| | |
| 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.
| |
| }}
| |
| | |
| | |
| We have seen that on a sorted table, there is no search algorithm outperforming the binary search in the worst case.
| |
| 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
| |
| :<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-like Theorems ==
| |
| === Van der Waerden's Theorem ===
| |
| {{Theorem|Theorem (Van der Waerden 1927)|
| |
| :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>.
| |
| }}
| |
| | |
| === Hales–Jewett Theorem ===
| |
| {{Theorem|Theorem (Hales-Jewett 1963)|
| |
| :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.
| |
| }}
| |
| | |
| {{Theorem|Theorem (Hales-Jewett 1963)|
| |
| :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.
| |
| }}
| |
Template:Orphan
Graham's number is a very, very big natural number that was defined by a man named Ronald Graham. Graham was solving a problem in an area of mathematics called Ramsey theory. He proved that the answer to his problem was smaller than Graham's number.
Graham's number is one of the biggest numbers ever used in a mathematical proof. Even if every digit in Graham's number were written in the tiniest writing possible, it would still be too big to fit in the observable universe.
Context
Ramsey theory is an area of mathematics that asks questions like the following:
Template:Quote
It turns out that for this simple problem, the answer is "yes" when we have 6 or more points, no matter how the lines are colored. But when we have 5 points or fewer, we can color the lines so that the answer is "no".
Graham's number comes from a variation on this question.
Template:Quote
By asking that the 4 points lie on a plane, we have made the problem much harder. We would like to know: for what values of n is the answer "no" (for some way of coloring the lines), and for what values of n is it "yes" (for all ways of coloring the lines)? But this problem has not been completely solved yet.
In 1971, Ronald Graham and B. L. Rothschild found a partial answer to this problem. They showed that for n=6, the answer is "no". But when n is very large, as large as Graham's number or larger, the answer is "yes".
One of the reasons this partial answer is important is that it means that the answer is eventually "yes" for at least some large n. Before 1971, we didn't know even that much.
Definition
Graham's number is not only too big to write down all of its digits, it is too big even to write in scientific notation. In order to be able to write it down, we have to use Knuth's up-arrow notation.
We will write down a sequence of numbers that we will call g1, g2, g3, and so on. Each one will be used in an equation to find the next. g64 is Graham's number.
First, here are some examples of up-arrows:
- [math]\displaystyle{ 3\uparrow3 }[/math] is 3x3x3 which equals 27. An arrow between two numbers just means the first number multiplied by itself the second number of times.
- You can think of [math]\displaystyle{ 3 \uparrow \uparrow 3 }[/math] as [math]\displaystyle{ 3 \uparrow (3 \uparrow 3) }[/math] because two arrows between numbers A and B just means A written down a B number of times with an arrow in between each A. Because we know what single arrows are, [math]\displaystyle{ 3\uparrow(3\uparrow3) }[/math] is 3 multiplied by itself [math]\displaystyle{ 3\uparrow3 }[/math] times and we know [math]\displaystyle{ 3\uparrow3
}[/math] is twenty-seven. So [math]\displaystyle{ 3\uparrow\uparrow3 }[/math] is 3x3x3x3x....x3x3, in total 27 times. That equals 7625597484987.
- [math]\displaystyle{ 3 \uparrow \uparrow \uparrow 3 }[/math] is [math]\displaystyle{ 3 \uparrow \uparrow (3 \uparrow \uparrow 3) }[/math] and we know [math]\displaystyle{ 3\uparrow\uparrow3 }[/math] is 7625597484987. So [math]\displaystyle{ 3\uparrow\uparrow(3\uparrow\uparrow3) }[/math] is [math]\displaystyle{ 3\uparrow \uparrow 7625597484987 }[/math]. That can also be written as [math]\displaystyle{ 3\uparrow(3\uparrow(3\uparrow(3\uparrow . . .(3\uparrow(3\uparrow(3\uparrow3) }[/math] with a total of 7625597484987 3s. This number is so huge, its digits, even written very small, could fill up the observable universe and beyond.
- Although this number may already be beyond comprehension, this is barely the start of this giant number.
- The next step like this is [math]\displaystyle{ 3 \uparrow \uparrow \uparrow \uparrow 3 }[/math] or [math]\displaystyle{ 3 \uparrow \uparrow \uparrow (3 \uparrow \uparrow \uparrow 3) }[/math]. This is the number we will call g1.
After that, g2 is equal to [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow 3 }[/math]; the number of arrows in this number is g1.
g3 is equal to [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3 }[/math], where the number of arrows is g2.
We keep going in this way. We stop when we define g64 to be [math]\displaystyle{ 3\uparrow \uparrow \uparrow \uparrow \uparrow \ldots \uparrow \uparrow \uparrow \uparrow \uparrow 3 }[/math], where the number of arrows is g63.
This is Graham's number.
Related pages