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 Twitter account. ( Log Out / Change )

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

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

Cancel

Connecting to %s

Categories

Mathoverflow

Answer by Andrés E. Caicedo for product of power sets July 13, 2017

The answer is no in general. For instance, by what is essentially an argument of Sierpiński, if $(X,\Sigma,\nu)$ is a $\sigma$-finite continuous measure space, then no non-null subset of $X$ admits a $\nu\times\nu$-measurable well-ordering. The proof is almost verbatim the one here. It is consistent (assuming large cardinals) that there is an extension of Le […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Choosing *two* representatives July 19, 2017

I assume by $\aleph$ you mean $\mathfrak c$, the cardinality of the continuum. You can build $D$ by transfinite recursion: Well-order the continuum in type $\mathfrak c$. At stage $\alpha$ you add a point of $A_\alpha$ to your set, and one to its complement. You can always do this because at each stage fewer than $\mathfrak c$ many points have been selected. […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Axiom of Choice: Ultrafilter vs. Vitali set July 6, 2011

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 negative. More precisely: Assume determinacy in $L({\mathbb R})$. Then $2^\omega/E_0$ is a successor cardinal to ${\mathfrak c}$ (This doesn't matter, all we need is that it is strictly larger. T […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for "Weakly" Woodin cardinals May 28, 2017

(As I pointed out in a comment) yes, partial Woodinness is common in arguments in inner model theory. Accordingly, you obtain determinacy results addressing specific pointclasses (typically, well beyond projective). To illustrate this, let me "randomly" highlight two examples: See here for $\Sigma^1_2$-Woodin cardinals and, more generally, the noti […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Completion of ZFC November 22, 2010

I am not sure which statement you heard as the "Ultimate $L$ axiom," but I will assume it is the following version: There is a proper class of Woodin cardinals, and for all sentences $\varphi$ that hold in $V$, there is a universally Baire set $A\subseteq{\mathbb R}$ such that, letting $\theta=\Theta^{L(A,{\mathbb R})}$, we have that $HOD^{L(A,{\ma […]

Andrés E. Caicedo

Math.StackExchange

Answer by Andrés E. Caicedo for Is there a permutation on $\mathbb{N}$ that, if repeated often enough, eventually shuffles the whole set? July 23, 2017

A simple example is the permutation $\pi$ given by $\pi(n)=n+2$ if $n$ is even, $\pi(1)=0$, and otherwise $\pi(n)=n−2$. It should be clear that $\pi$ is computable and has the desired property. By the way, regarding the footnote: if a bijection is computable, so is its inverse, so $\pi^{-1}$ is computable as well. In general, given a computable bijection $\s […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Clarifying a question on polynomials July 12, 2017

The question is asking to find all polynomials $f$ for which you can find $a,b\in\mathbb R$ with $a\ne b$ such that the displayed identity holds. The concrete numbers $a,b$ may very well depend on $f$. A priori, it may be that for some $f$ there is only one pair for which the identity holds, it may be that for some $f$ there are many such pairs, and it may a […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Minimum number of axioms for ZFC set theory July 1, 2017

The reflection principle is a theorem schema in ZFC, meaning that for each formula $\phi(\vec x)$ we can prove in ZFC a version of the principle for $\phi$. In particular, it gives us that if $\phi$ holds (in the universe of sets) then there is some ordinal $\alpha$ such that $V_\alpha\models \phi$. It follows from this that (assuming its consistency) $\math […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Direct bijection between $C[0,1]$ and $[0,1]$ June 23, 2017

All proofs of the Bernstein-Cantor-Schroeder theorem that I know either directly or with very little work produce an explicit bijection from any given pair of injections. There is an obvious injection from $[0,1]$ to $C[0,1]$ mapping each $t$ to the function constantly equal to $t$, so the question reduces to finding an explicit injection from $C[0,1]$ to $[ […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Is it possible to formalize the idea that large cardinal axioms don't limit us, while their negations do? November 25, 2013

One way we formalize this "limitation" idea is via interpretative power. John Steel describes this approach carefully in several places, so you may want to read what he says, in particular at Solomon Feferman, Harvey M. Friedman, Penelope Maddy, and John R. Steel. Does mathematics need new axioms?, The Bulletin of Symbolic Logic, 6 (4), (2000), 401 […]

Andrés E. Caicedo

	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
	andrescaicedo on MSC2020
	Asaf Karagila on Help!
	andrescaicedo on Help!
	Yizheng Zhu (@yizhen… on Help!
	andrescaicedo on Help!
	Joel David Hamkins on Help!
	andrescaicedo on Help!

A kind of library