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 Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper? December 23, 2014

This is Theorem 39 in the paper (see Theorem 4.(i) for a user-friendly preview). But the fact that $(2^\kappa)^+\to(\kappa^+)^2_\kappa$ is older (1946) and due to Erdős, see here: Paul Erdős. Some set-theoretical properties of graphs, Univ. Nac. Tucumán. Revista A. 3 (1942), 363-367 MR0009444 (5,151d). (Anyway, it is probably easier to read a more modern pre […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for The Erdős-Turán conjecture or the Erdős' conjecture? June 3, 2013

One of the best places to track these things down is The mathematical coloring book, by Alexander Soifer, Springer 2009. Chapter 35 is on "Monochromatic arithmetic progressions", and section 35.4, "Paul Erdős’s Favorite Conjecture", is on the problem you ask about. As far as I can tell, the question is sometimes called the Erdős-Turán con […]

Andrés E. Caicedo

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

On the division paradox December 22, 2022

This question is partly motivated by Timothy Chow's recent question on the division paradox. Say that a set $X$ admits a paradoxical partition if and only if there is an equivalence relation $\sim$ on $X$ such that $|X|

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Relative densities December 22, 2022

A solution can be obtained as suggested by Keith Conrad in the comments, via Chebotarëv's theorem. Details can be found in $\S3.4$ of Coloring the $n$-Smooth Numbers with $n$ Colors Andrés Eduardo Caicedo, Thomas A. C. Chartier, Péter Pál Pach The Electronic Journal of Combinatorics 28 (1) (2021), #P1.34, 79 pp. DOI: https://doi.org/10.37236/8492 Many t […]

Andrés E. Caicedo

Math.StackExchange

Answer by Andrés E. Caicedo for Is it possible for a function to be smooth everywhere, analytic nowhere, yet Taylor series at any point converges in a nonzero radius? January 7, 2014

No, this is not possible. Dave L. Renfro wrote an excellent historical Essay on nowhere analytic $C^\infty$ functions in two parts (with numerous references). See here: 1 (dated May 9, 2002 6:18 PM), and 2 (dated May 19, 2002 8:29 PM). As indicated in part 1, in Zygmunt Zahorski. Sur l'ensemble des points singuliers d'une fonction d'une variab […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for How to check the real analyticity of a function? December 3, 2013

This is a difficult question in general. Ideally, to show that $f$ is analytic at the origin, you show that in a suitable neighborhood of $0$, the error of the $n$-th Taylor polynomial approaches $0$ as $n\to\infty$. For example, for $f(x)=\sin(x)$, any derivative of $f(x)$ is one of $\sin(x)$, $\cos(x)$, $-\sin(x)$, or $-\cos(x)$, and the error given by the […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Borel hierarchy doesn't "collapse" before $\omega_1$ October 1, 2013

To complement Yann's answer: This is a nice problem, the possible length of Borel hierarchies in different spaces or without assuming the axiom of choice. It has been studied in detail by Arnie Miller. See Arnold W. Miller. On the length of Borel hierarchies, Ann. Math. Logic, 16 (3), (1979), 233–267. MR0548475 (80m:04003), Arnold W. Miller. Long Borel […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for consistency strength of PA September 3, 2013

This is a good question, because a priori $\mathsf{PA}$ lacks the flexibility of $\mathsf{ZFC}$ that allows us to deal with consistency problems semantically (by building models) and, anyway, the obvious model of most subtheories of $\mathsf{PA}$ is just the standard model. The way this is done in the context of $\mathsf{ZFC}$ is using the reflection theorem […]

Andrés E. Caicedo

Answer by Andrés E. Caicedo for Does ZFC prove a sentence in the language of arithmetic that PA+Con(ZFC) cannot prove? August 31, 2013

Yes, of course. An example is the statement that all Goodstein sequences terminate. The point is that this sentence is not only independent of $\mathsf{PA}$, but in fact of the theory resulting from adding to $\mathsf{PA}$ all $\Pi^0_1$ statements true in the standard model of arithmetic. Note that $\mathrm{Con}(\mathsf{ZFC})$ is an example of such a $\Pi^0_ […]

Andrés E. Caicedo

	Richard Kimberly Hec… on Woodin’s proof of the se…
	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 …

A kind of library