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.

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.

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 )

Cancel

Connecting to %s

Categories

Mathoverflow

Answer by Andrés E. Caicedo for Continuum Hypothesis December 30, 2012

A classical reference is Hypothèse du Continu by Waclaw Sierpiński (1934), available through the Virtual Library of Science as part of the series Mathematical Monographs of the Institute of Mathematics of the Polish Academy of Sciences. Sierpiński discusses equivalences and consequences. The statements covered include examples from set theory, combinatorics, […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Which journals publish expository work? October 25, 2013

There is a new journal of the European Mathematical Society that seems perfect for these articles: EMS Surveys in Mathematical Sciences. The description at the link reads: The EMS Surveys in Mathematical Sciences is dedicated to publishing authoritative surveys and high-level expositions in all areas of mathematical sciences. It is a peer-reviewed periodical […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Does "$X \not\to (\omega)^\omega_2$ for every infinite $X$" imply ${\sf AC}$? March 29, 2022

The answer is no, the statement that for every set $X$ we have $$X\not\to(\omega)^\omega_2$$ does not imply the axiom of choice. This was shown by Kleinberg and Seiferas in 1973, see MR0340025 (49 #4782) Kleinberg, E. M.; Seiferas, J. I. Infinite exponent partition relations and well-ordered choice. J. Symbolic Logic 38 (1973), 299–308. https://doi.org/10.23 […]

Andrés E. Caicedo

On the structure of maximal Ramsey colorings October 25, 2021

For positive integers $a_1,\dots,a_n$, recall that the multicolor Ramsey number $R(a_1,\dots,a_n)$ is the smallest integer $N$ such that if the edges of the complete graph $K_N$ are colored with the $n$ colors $1,\dots,n$, then there is some $i\le n$ and a set of $a_i$ vertices, all of whose edges received color $i$. A maximal Ramsey$(a_1,\dots,a_n)$-colorin […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for How to rearrange only negative part of a conditionally convergent series to get any sum greater then initial? November 29, 2010

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

Andrés E. Caicedo

Math.StackExchange

Answer by Andrés E. Caicedo for Are there examples of theorems proved via proper (i.e. non-conservative) extensions? May 7, 2013

Yes, this is a nice idea, and the approach is used in practice. I list four examples below, but there are many others. Any arithmetic statement, or any first order statement about $(\mathbb R,\mathbb N,+,\times,

Andrés E. Caicedo

Answer by Andrés E. Caicedo for If a function can only be defined implicitly does it have to be multivalued? June 4, 2011

Not necessarily. Consider the graph $G$ in ${\mathbb R}^2$ of the points $(x,y)$ such that $$ y^5+16y-32x^3+32x=0. $$ This example comes from the nice book "The implicit function theorem" by Krantz and Parks. Note that this is the graph of a function: Fix $x$, and let $F(y)=y^5+16y-32x^3+32x$. Then $F'(y)=5y^4+16>0$ so $F$ is strictly incre […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Whether the map $x\mapsto x^3$ in a finite field is bijective August 20, 2013

Following Tomas's suggestion, I am posting this as an answer: I encountered this problem while directing a Master's thesis two years ago, and again (in a different setting) with another thesis last year. I seem to recall that I somehow got to this while reading slides of a talk by Paul Pollack. Anyway, I like to deduce the results asked in the prob […]

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

Answer by Andrés E. Caicedo for Is $6.12345678910111213141516171819202122\ldots$ transcendental? March 5, 2011

This is a transcendental number, in fact one of the best known ones, it is $6+$ Champernowne's number. Kurt Mahler was first to show that the number is transcendental, a proof can be found on his "Lectures on Diophantine approximations", available through Project Euclid. The argument (as typical in this area) consists in analyzing the rate at […]

Andrés E. Caicedo

	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library