Given a natural number , write for the complete graph on vertices, and for the edgeless graph on vertices.
As explained in problem 47.10 from the textbook, given natural numbers , the notation
means that is so large that whenever is a graph on vertices, either contains a copy of as a subgraph, or a copy of as an induced subgraph.
We denote the negation of this statement by . In detail, this means that there is a graph on vertices such that for any collection of vertices of , at least one of the edges between them is not in , and also for any collection of vertices of , at least of the edges between them is in .
Note that if then also:
,
for any , and
for any .
Clearly, and for any . It is also clear that for any . When , however, the determination of the smallest such that is a subtle and difficult problem. This is called the Ramsey number of . We will denote it , so
and, if , then .
Theorem 1If and , then .
Proof: Consider a graph with . We need to show that either there is a copy of or of as an induced subgraph of .
Let . Divide the remaining vertices of into two sets and by setting
and
where means that there is an edge between and . We have and therefore either or . Otherwise, and , from which it follows that .
Suppose first that . Since , then the subgraph of induced by either contains a copy of or an induced copy of . In the latter case, is also an induced subgraph of , and we are done. In the former case, let be a subset of of size such that the subgraph of induced by is (isomorphic to) . Then, by definition of , the subgraph of induced by is isomorphic to , and we are done as well.
If, on the other hand, , the symmetric argument holds: Either there is a subset of of size whose induced subgraph is , and we are done, or else contains a copy of . But then (by definition of ) we have that is a copy of .
We have shown that in all cases either contains a copy of or of , as we needed to prove.
For example:
Since and , it follows that . A pentagon is an example of a graph witnessing , and therefore .
Since and , then . On the other hand, an octagon with two of its main diagonals is an example of a graph witnessing This means that is either 9 or 10. That it is actually 9 is a consequence of the following general result:
Theorem 2Suppose that and are even, and that and . Then .
Proof: We argue as before: Let be a graph with vertices. Given , define and as before, and note that . There are three cases:
. The result then follows by arguing as in the previous proof.
. Again, the result follows as in the previous proof.
and . Since , we must have that in fact and . Note that (by definition) , where is the degree (or valence) of .
If there is at least one for which we have either case 1 or 2, we are done. But this must actually happen. Otherwise,
is an odd number, since both and are even by assumption. However, as shown in Theorem 46.5 from the textbook, for any graph , we have that
which is obviously an even number. This contradiction completes the proof.
Theorems 1 and 2 provide us with an obvious algorithm to obtain upper bounds for the values of the Ramsey numbers , but these bounds are usually not optimal. For example,
and
so . However, the exact value of is 25.
For up-to-date bounds on the Ramsey numbers and references, the online survey Small Ramsey numbers by Stanislaw Radziszowski (The Electronic Journal of Combinatorics) is highly recommended. Typeset using LaTeX2WP. Here is a printable version of this post.
This entry was posted on Tuesday, May 4th, 2010 at 12:10 am and is filed under 187: Discrete mathematics. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
Georgii: Let me start with some brief remarks. In a series of three papers: a. Wacław Sierpiński, "Contribution à la théorie des séries divergentes", Comp. Rend. Soc. Sci. Varsovie 3 (1910) 89–93 (in Polish). b. Wacław Sierpiński, "Remarque sur la théorème de Riemann relatif aux séries semi-convergentes", Prac. Mat. Fiz. XXI (1910) 17–20 […]
It is not possible to provide an explicit expression for a non-linear solution. The reason is that (it is a folklore result that) an additive $f:{\mathbb R}\to{\mathbb R}$ is linear iff it is measurable. (This result can be found in a variety of places, it is a standard exercise in measure theory books. As of this writing, there is a short proof here (Intern […]
Stefan, "low" cardinalities do not change by passing from $L({\mathbb R})$ to $L({\mathbb R})[{\mathcal U}]$, so the answer to the second question is that the existence of a nonprincipal ultrafilter does not imply the existence of a Vitali set. More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${ […]
Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.
Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ with all its edges of the same color. For example, $R(3)= 6$, which is usually stated by saying that in a party of 6 people, necessarily there are 3 that know e […]
Equality is part of the background (first-order) logic, so it is included, but there is no need to mention it. The situation is the same in many other theories. If you want to work in a language without equality, on the other hand, then this is mentioned explicitly. It is true that from extensionality (and logical axioms), one can prove that two sets are equ […]
$L$ has such a nice canonical structure that one can use it to define a global well-ordering. That is, there is a formula $\phi(u,v)$ that (provably in $\mathsf{ZF}$) well-orders all of $L$, so that its restriction to any specific set $A$ in $L$ is a set well-ordering of $A$. The well-ordering $\varphi$ you are asking about can be obtained as the restriction […]
Gödel sentences are by construction $\Pi^0_1$ statements, that is, they have the form "for all $n$ ...", where ... is a recursive statement (think "a statement that a computer can decide"). For instance, the typical Gödel sentence for a system $T$ coming from the second incompleteness theorem says that "for all $n$ that code a proof […]
When I first saw the question, I remembered there was a proof on MO using Ramsey theory, but couldn't remember how the argument went, so I came up with the following, that I first posted as a comment: A cute proof using Schur's theorem: Fix $a$ in your semigroup $S$, and color $n$ and $m$ with the same color whenever $a^n=a^m$. By Schur's theo […]
It depends on what you are doing. I assume by lower level you really mean high level, or general, or 2-digit class. In that case, 54 is general topology, 26 is real functions, 03 is mathematical logic and foundations. "Point-set topology" most likely refers to the stuff in 54, or to the theory of Baire functions, as in 26A21, or to descriptive set […]
,
for any
, and
for any
.
, then 
.
and
, it follows that
. A pentagon is an example of a graph witnessing
, and therefore
.
and
. On the other hand, an octagon with two of its main diagonals is an example of a graph witnessing
This means that
is either 9 or 10. That it is actually 9 is a consequence of the following general result:
.
and
. Note that (by definition)
, where
is the degree (or valence) of
