187 – On Ramsey theory | A kind of library

187 – On Ramsey theory

Given a natural number ${n}$ , write ${K_n}$ for the complete graph on ${n}$ vertices, and ${E_n}$ for the edgeless graph on ${n}$ vertices.

As explained in problem 47.10 from the textbook, given natural numbers ${a,b,n}$ , the notation

$\displaystyle n\rightarrow(a,b)$

means that ${n}$ is so large that whenever ${G}$ is a graph on ${n}$ vertices, either ${G}$ contains a copy of ${K_a}$ as a subgraph, or a copy of ${E_b}$ as an induced subgraph.

We denote the negation of this statement by ${n\not\rightarrow(a,b)}$ . In detail, this means that there is a graph ${G=(V,E)}$ on ${n}$ vertices such that for any collection of ${a}$ vertices of ${G}$ , at least one of the edges between them is not in ${E}$ , and also for any collection of ${b}$ vertices of ${G}$ , at least of the edges between them is in ${E}$ .

Note that if ${n\rightarrow(a,b)}$ then also:

${n\rightarrow(b,a)}$ ,
${m\rightarrow(a,b)}$ for any ${m\ge n}$ , and
${n\rightarrow(a,c)}$ for any ${c\le b}$ .

Clearly, ${0\rightarrow(m,0)}$ and ${1\rightarrow(m,1)}$ for any ${m}$ . It is also clear that ${m\rightarrow(m,2)}$ for any ${m}$ . When ${a,b\ge3}$ , however, the determination of the smallest ${n}$ such that ${n\rightarrow(a,b)}$ is a subtle and difficult problem. This ${n}$ is called the Ramsey number of ${a,b}$ . We will denote it ${R(a,b)}$ , so

$\displaystyle R(a,b)\rightarrow(a,b)$

and, if ${m<R(a,b)}$ , then ${m\not\rightarrow(a,b)}$ .

Theorem 1 If ${n\rightarrow(a-1,b)}$ and ${m\rightarrow(a,b-1)}$ , then ${n+m\rightarrow(a,b)}$ .

Proof: Consider a graph ${G=(V,E)}$ with ${|V|=n+m}$ . We need to show that either there is a copy of ${K_a}$ or of ${E_b}$ as an induced subgraph of ${G}$ .

Let ${v\in V}$ . Divide the remaining ${n+m-1}$ vertices of ${G}$ into two sets ${A}$ and ${B}$ by setting

$\displaystyle A=\{w\in V\mid v\sim w\}$

and

$\displaystyle B=\{w\in V\mid w\ne v\mbox{ and }v\not\sim w\},$

where ${v\sim w}$ means that there is an edge between ${v}$ and ${w}$ . We have ${|A|+|B|=n+m-1}$ and therefore either ${|A|\ge n}$ or ${|B|\ge m}$ . Otherwise, ${|A|\le n-1}$ and ${|B|\le m-1}$ , from which it follows that ${|A|+|B|\le n+m-2}$ .

Suppose first that ${|A|\ge n}$ . Since ${n\rightarrow(a-1,b)}$ , then the subgraph of ${G}$ induced by ${A}$ either contains a copy of ${K_{a-1}}$ or an induced copy of ${E_b}$ . In the latter case, ${E_b}$ is also an induced subgraph of ${G}$ , and we are done. In the former case, let ${C}$ be a subset of ${A}$ of size ${a-1}$ such that the subgraph of ${G}$ induced by ${C}$ is (isomorphic to) ${K_{a-1}}$ . Then, by definition of ${A}$ , the subgraph of ${G}$ induced by ${C\cup\{v\}}$ is isomorphic to ${K_a}$ , and we are done as well.

If, on the other hand, ${|B|\ge m}$ , the symmetric argument holds: Either there is a subset of ${B}$ of size ${a}$ whose induced subgraph is ${K_a}$ , and we are done, or else ${B}$ contains a copy ${C}$ of ${E_{b-1}}$ . But then (by definition of ${B}$ ) we have that ${C\cup\{v\}}$ is a copy of ${E_b}$ .

We have shown that in all cases ${G}$ either contains a copy of ${K_a}$ or of ${E_b}$ , as we needed to prove. $\Box$

For example:

Since ${3\rightarrow(2,3)}$ and ${3\rightarrow(3,2)}$ , it follows that ${6\rightarrow(3,3)}$ . A pentagon is an example of a graph witnessing ${5\not\rightarrow(3,3)}$ , and therefore ${R(3,3)=6}$ .
Since ${4\rightarrow(2,4)}$ and ${6\rightarrow(3,3)}$ , then ${10\rightarrow(3,4)}$ . On the other hand, an octagon with two of its main diagonals is an example of a graph witnessing ${8\not\rightarrow(3,4).}$ This means that ${R(3,4)}$ is either 9 or 10. That it is actually 9 is a consequence of the following general result:

Theorem 2 Suppose that ${n}$ and ${m}$ are even, and that ${n\rightarrow(a-1,b)}$ and ${m\rightarrow(a,b-1)}$ . Then ${n+m-1\rightarrow(a,b)}$ .

Proof: We argue as before: Let ${G=(V,E)}$ be a graph with ${n+m-1}$ vertices. Given ${v\in V}$ , define ${A}$ and ${B}$ as before, and note that ${|A|+|B|=n+m-2}$ . There are three cases:

${|A|\ge n}$ . The result then follows by arguing as in the previous proof.
${|B|\ge m}$ . Again, the result follows as in the previous proof.
${|A|\le n-1}$ and ${|B|\le m-1}$ . Since ${|A|+|B|=n+m-2}$ , we must have that in fact ${|A|=n-1}$ and ${|B|=m-1}$ . Note that (by definition) ${d(v)=|A|=n-1}$ , where ${d(v)}$ is the degree (or valence) of ${v}$ .

If there is at least one ${v\in V}$ for which we have either case 1 or 2, we are done. But this must actually happen. Otherwise,

$\displaystyle \sum_{v\in V}d(v)=(n-1)|V|=(n-1)(n+m-1)$

is an odd number, since both ${n}$ and ${m}$ are even by assumption. However, as shown in Theorem 46.5 from the textbook, for any graph ${G=(V,E)}$ , we have that

$\displaystyle \sum_{v\in V}d(v)=2|E|,$

which is obviously an even number. This contradiction completes the proof. $\Box$

Theorems 1 and 2 provide us with an obvious algorithm to obtain upper bounds for the values of the Ramsey numbers ${R(a,b)}$ , but these bounds are usually not optimal. For example,

$\displaystyle R(4,4)\le R(3,4)+R(4,3)=18$

and

$\displaystyle R(5,3)\le R(4,3)+R(5,2)=9+5=14,$

so ${R(5,4)\le R(4,4)+R(5,3)-1=31}$ . However, the exact value of ${R(5,4)}$ 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.

Leave a Reply Cancel reply

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Google+ account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

Categories

Mathoverflow

Relative Densities September 12, 2013

Throughout the question, we only consider primes of the form $3k+1$. A reference for cubic reciprocity is Ireland & Rosen's A Classical Introduction to Modern Number Theory. How can I count the relative density of those $p$ (of the form $3k+1$) such that the equation $2=3x^3$ has no solutions modulo $p$? Really, even pointers on how to say anything […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Solutions to the Continuum Hypothesis May 18, 2010

(1) Patrick Dehornoy gave a nice talk at the Séminaire Bourbaki explaining Hugh Woodin's approach. It omits many technical details, so you may want to look at it before looking again at the Notices papers. I think looking at those slides and then at the Notices articles gives a reasonable picture of what the approach is and what kind of problems remain […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Are there any non-linear solutions of Cauchy's equation ($f(x+y)=f(x)+f(y)$) without assuming the Axiom of Choice? March 6, 2011

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 […]

Andrés E. Caicedo

David Gale's subset take-away game October 12, 2010

I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print: Richard K. Guy. Unsolved problems in combinatorial games. In Games of No Chance, (R. J. Nowakowski ed.) MSRI Publications 29, Cambridge University Press, 1996, pp. […]

Andrés E. Caicedo

A translation of the Cantor set contained in the irrationals February 22, 2014

Let $C$ be the standard Cantor middle-third set. As a consequence of the Baire category theorem, there are numbers $r$ such that $C+r$ consists solely of irrational numbers, see here. What would be an explicit example of a number $r$ with this property? Short of an explicit example, are there any references addressing this question? A natural approach would […]

Andrés E. Caicedo

Math.StackExchange

Answer by Andrés E. Caicedo for Well-ordering of the reals in ZF with constructibility? April 19, 2018

$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{ZFC}$) well-orders all of $L$, so that its restriction to any specific set $A$ is a set well-ordering of $A$. The well-ordering $\varphi$ you are asking about can be obtained as the restriction to $\ […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Assuming ZF and the axiom of constructibility, $\alpha > \omega, V_\alpha = L_\alpha \iff \alpha = \aleph_\alpha$ February 28, 2018

Define the sequence of beth numbers by $\beth_0=\aleph_0$, $\beth_{\alpha+1}=2^{\beth_\alpha}$ and $\beth_\lambda=\sup_{\beta

Andrés E. Caicedo

Answer by Andrés E. Caicedo for On the definition of Inductive set. Equivalences February 18, 2018

The two concepts are different. For example, $\omega$, the first infinite ordinal, is the standard example of an inductive set according to the first definition, but is not inductive in the second sense. In fact, no set can be inductive in both senses (any such putative set would contain all ordinals). In the context of set theory, the usual use of the term […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Find a contradiction to: If $t^n < (\sup \{t \in \mathbb{R}_{>0}: t^n < x\})^n$ then $t^n < x$ when this supremum is greater than $x$. February 16, 2018

I will show that for any positive integers $n,\ell,k$ there is an $M$ so large that for all positive integers $i$, if $i/M\le \ell$, then the difference $$ \left(\frac iM\right)^n-\left(\frac{i-1}M\right)^n $$ is less than $1/k$. Let's prove this first, and then argue that the result follows from it. Note that $$ (i+1)^n-i^n=\sum_{k=0}^{n-1}\binom nk i^ […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Prove by induction that $n^2>7n+1$ for all $n \ge 8$ February 15, 2018

I think it is cleaner to argue without induction. If $n$ is a positive integer and $n\ge 8$, then $7n$ is both less than $n^2$ and a multiple of $n$, so at most $n^2-n$ and therefore $7n+1$ is at most $n^2-n+1

Andrés E. Caicedo

	116c- Homework 7 \| A… on 116c- Lecture 18
	116c- Lecture 17 \| A… on 116c: Mathematical Logic (Set…
	116c- Lecture 18 \| A… on 116c- Homework 7
	116c- Lecture 19 \| A… on 116c- Lecture 13
	580 -Partition calcu… on 580 -III. Partition calcu…
	580 -Partition calcu… on 580 -Partition calculus (…
	Nosferatu \| A kind o… on The cabinet of Doctor Cal…
	Monica Agana –… on 414/514 The theorems of Rieman…
	The Dalek invasion o… on The Dalek invasion of Boi…
	andrescaicedo on Help!
	Asaf Karagila on On anti-foundation and coding…
	andrescaicedo on On anti-foundation and coding…
	Asaf Karagila on On anti-foundation and coding…
	On anti-foundation a… on Interpretations
	andrescaicedo on MSC2020

A kind of library