home | index | units | counting | geometry | algebra | trigonometry & functions | calculus
analysis | sets & logic | number theory | recreational | misc | nomenclature & history | physics

Final Answers
© 2000-2016   Gérard P. Michon, Ph.D.

Ramsey Theory
Unavoidable order in large blobs


 Coat of arms of
 Waclaw Sierpinski
In all chaos there is a cosmos;
in all disorder, a secret order
.
Carl Jung   (1875-1961) 
 border
 border  border
 border
 border
 border
 border

Related articles on this site:

Related Links (Outside this Site)

A brief introduction to Ramsey Theory  by   Eric Yu.
Ramsey Theory in the work of Paul Erdös  by   R. L. Graham and J. Nesetri.
 
Wikipedia :   Ramsey Theory   |   Frank P. Ramsey (1903-1930)
 
border
border

Ramsey Theory

In 1928, Frank Plumpton Ramsey (1903-1930) remarked that patterns are unavoidable in large enough structures.  Although Ramsey only published an inconspicuous lemma in combinatorics about this (Ramsey's Theorem, 1930) this viewpoint has grown into an entire branch of mathematics, now called Ramsey Theory.


(2007-07-16)   The Pigeonhole Principle   (Dirichlet, 1834)
With fewer holes than pigeons, there must be a hole with several pigeons.

That's the simplest and most fundamental result in  Ramsey Theory.

Formally:  A function from a  finite  set into a smaller one can't be  injective.

This trivial statement turns out to be quite useful.  It was first stated formally in 1834 by Dirichlet who found several nontrivial uses for it...  Dirichlet dubbed it  Schubfachprinzip  (principle of the drawer)  which serves as the basis for the name given to the concept in several languages, including French  (principe des tiroirs)...  If you have more socks than drawers to put them in, then at least one drawer must have more than one sock in it!

Ramsey Theory deals with whatever becomes unavoidable  (holes with several pigeons)  when some quantity  (like the number of pigeons)  becomes large enough.


Anonymous query, via Google  (2010-10-14)   Given 70 distinct positive integers not exceeding 200, show that two of them differ by 4, 5 or 9.

Let  A  be a set of  70  distinct positive integers not exceeding  200.  The three sets  A, A+4 and A+9  cannot be pairwise disjoint  (or else, there would be  210  distinct positive integers not exceeding  209).  Therefore, there must be at least one integer  x  that belongs to at least two of those three sets.

  • If  x  is in  A  and  A+4, then  x  and  x+4  are in  A.
  • If  x  is in  A+4  and  A+9, then  x-9  and  x-4  are in  A.
  • If  x  is in  A  and  A+9, then  x  and  x+9  are in  A.

So, there's at least one pair of integers in  A  which differ by  4, 5 or 9.


(2009-01-18)   n+1  numbers among the first  2n  integers...
... will always contain two coprime integers.  Prove it!

In the summer of 1959, Paul Erdös (1913-1996)  met  Lajos Pósa (1947-)  before he was even 12.  Posa had been spotted as a child prodigy by the logician  Rósza Péter (1905-1977).  Erdös was delighted when the boy solved the above puzzle while eating his soup in  half a minute or so.

Give it a shot...   [ Answer ]

Louis Posa   |   Pósa Lajos (in Hungarian)   |   Eureka


(2009-01-19)   Choosing integers between 1 and n...
How many can you pick without having k+1 of them pairwise coprime?

The previous question is actually a special case  (k = 1)  of a  difficult  problem:  What's the largest number  b  of positive integers not exceeding  n  with no more than  k  pairwise coprime numbers among them?  Here's a table of  b(n) :

 k  1  2   3  4  5  6   7  8  9   10  11  12   13  14  15   16  17  18 
1 111223344 556677 889
2 122334456 77889 10111112
3 123445567 88991011121213
4 123456678 9910101112131314
5 123456789 10101111 121314 
6 123456789 101112121314  
7 123456789 10111213141516 16 

The largest  n  such that the set  {1, 2, 3, ... n}  contains at most  k  pairwise coprime numbers is tabulated below.  (It's the largest  n  for which  b(n) = n.)

  k   1234567
  n   1246101216

These are just one unit below the  kth  prime  (see A006093).  (HINT:  The number  1  and the primes up to  n  form a set of pairwise coprime integers.)

In 1962,  Erdös had conjectured that  b(n)  was equal to the number of integers not exceeding  n  which are divisible by at least one of the first  k  primes.

Erdös established the cases  k = 1  and  k = 2.  The case  k = 3  was proved by  S.L.G. Choi, in 1973.

That conjecture was  disproved  in 1994 by Ahlswede and Khachatrian.

Maximal sets of numbers not containing  k + 1  pairwise coprime integers  (1995)
and   On extremal sets without coprimes  by Rudolf Ahlswede and Levon H. Khachatrian (1994).
On sequences containing at most 3 pairwise coprime integers  by  S.L.G. Choi


(2009-01-14)   Ramsey's Theorem   (Frank Ramsey, 1930)
A monochromatic  K always occurs in a large enough colored  K.

K  is the undirected  complete graph  of order  n.  It consists of  n  vertices and   n(n-1)/2   edges  (connecting  all possible pairs of distinct vertices).

For two colors  (red and blue, say)  Ramsey's theorem  states that a complete graph of order at least equal to  R(r,b)  with red or blue edges must contain either a complete graph of order  r  with red edges only or a complete graph of order  b  with blue edges only.  Clearly,  R(r,b) = R(b,r).  The function  R  is notoriously difficult to compute, except when one argument is less than  3 :

R(1,n) = R(n,1) = 1         R(2,n) = R(n,2) = n

Otherwise,  R(r,b)  is unknown beyond the values tabulated below:

Ramsey Numbers
  1  2   3  4  5  6   7  8  9 
 1  111111111
2 123456789
3 13691418232836
4 1491825     
5 151425      
6 1618       
7 1723       
8 1828       
9 1936       

Similarly, in a complete graph of order  R(n, n ... n)  whose edges are colored using  c  colors  (1, 2 ... c)  there will always be  some  color  i  for which at least one complete subgraph of order  n exists whose edges are all of color  i.  At this writing, only one nontrivial multicolor value is known:

R(3,3,3)   =   17

This is to say that monochomatic triangles exist in any tri-colored complete graph of order 17.  (Two colorings of  K16   avoid monochromatic triangles.)

Ramsey's Theorem  (Wikipedia)


Points on a parabola (Marc Ordower of Bryan, TX. 2000-09-22)
Lattice points are points of the plane with integer coordinates.  Among infinitely many lattice points, must there always be some infinite subset of collinear points?

No.  Just consider the sequence whose general term is (P,P2): (1,1) (2,4) (3,9) (4,16) ... which does not even contain 3 collinear points. (These are points on a parabola, but points on any infinite convex curve would do!)


(Marc Ordower of Bryan, TX. 2000-09-24)
In an infinite sequence of lattice points where the distance [or gap] between two consecutive points is bounded...
  • Is there always an infinite subset of collinear points?
  • More interestingly:  Must some 1000000 points be collinear?

 Consecutive points are
 a bounded distance apart No, there need not be an infinite subset of collinear points in this case either...  Consider the sequence of points whose general term is (floor(Ön),n):

(0,0) (1,1) (1,2) (1,3) (2,4) (2,5) (2,6) (2,7) (2,8) (3,9) ...

The distance between consecutive points is indeed bounded; it is at most equal to Ö2.  No more than 3 points of this sequence may belong to a line that's not vertical, while only finitely many may belong to a vertical line (namely, 2p+1 points at abscissa p).

This does not settle the more interesting question of knowing whether there exist for any given M (say M=1000000) at least M collinear points in such a sequence... (See next article.)

On 2000-09-29, Marc Ordower wrote:
I'm glad that you find this question so interesting. I had posted it in hopes that someone would find it as appealing as I do.  However, I cannot take credit for posing this problem, as it is a classic question in Ramsey theory.  I should also point out that the solution to this problem is known.  I'll refrain from sharing it to avoid spoiling your fun.  However, there are a great many problems along these lines which are still open.
Regards, Marc

References:   [Affirmative answer to the second part of the question.]
This obscure result is indeed sometimes known as the Gerver-Ramsey theoremJoseph L. Gerver and L. Thomas Ramsey, On certain sequences of lattice points, Pacific J. Math. 83 (1979) 357-363, MR 81c:10039. 
    It is, in fact, enough to assume only that the gaps [the distances between pairs of consecutive points] are bounded on average (which is to say that the sum of the first n gaps is less than nB, for some positive constant B):  Carl Pomerance, Collinear subsets of lattice point sequences--an analog of Szemerédi's theorem, JCT-A (1980) 140-149, MR 81m:10104.

Problem 000:12  by Kevin O'Bryant,  in  "Western Number Theory Problems"  (Dec. 2000)


(2000-09-29)
In the plane, an infinite sequence of lattice points with bounded gaps contains at least M collinear points.

This is true for any integer M.  Here's my proof, which may or may not be the "classic" one which Marc Ordower would not share...   Just a joke!

We may assume that: 

  • The range of the sequence is infinite.  (Or else the result is trivial, since at least one point must appear infinitely many times, so that infinitely many elements of the sequence are collinear because they are equal). 
  • Consecutive points are distinct.  (The theorem so restricted is clearly equivalent to the more general one).

Without loss of generality, we may also assume that consecutive points are adjacent (that is, they are one unit of distance apart).  If the result holds in this special case, it holds for the general case because of the following argument:

For any sequence S of points (X(n),Y(n)) where two consecutive points are at most D units apart, we may consider the sequence C obtained by removing from the sequence (floor(X(n)/D),floor(Y(n)/D)) any consecutive elements which happen to be equal.  Since C is a sequence of adjacent points, the restricted theorem implies that, for any M, there is at least one straight line (with some rational slope q) going through MD2 elements of C.  Well, C clearly corresponds to D by D square cells which contain each at least one element from the original sequence S.  To the above line of slope q corresponds a set of at most D2 lines of slope q which contain each at least one integral point from each of those MD2 aligned cell.  The pigeonhole principle then tells us that at least one such line contains at least M points from the original sequence S.  In other words, the theorem for adjacent consecutive points does imply the general case where consecutive points are only known to be less than some distance D apart.

We now complete the proof by ...

 Come back later, we're
 still working on this one...

(2009-06-27)   Van der Waerden's theorem   (1927)
With finitely many colors of integers, there must be arbitrarily long arithmetic progressions of the same color.

For instance, the  van der Waerden theorem  states that arbitrarily long arithmetic progressions must exist which consist entirely either of prime numbers or of other integers.  (Actually,  both  alternatives are true; the latter is trivial and the former is the celebrated Green-Tao theorem.)

Van der Waerden's numbers   |   Bartel Leendert van der Waerden (1903-1996)


(2014-07-28)   Happy-End Problem   (1933)
Number of points guaranteed to contain the vertices of a convex n-gon.

In the early 1930s, Esther Klein-Szekeres (1910-2005) was the only female member of a group of brilliant young Hungarian mathematicians who convened regularly, including Paul Erdös (1913-1996) George Szekeres (1911-2005) and Paul Turàn (1910-1976)

In 1933, Esther asked the group about the least number of points in the plane  (without alignments)  which insures that  n  of them are the vertices of a  convex  polygon  (i.e., none of those is in the convex hull of the others).

That problem and its poser got the interest of George Szekeres who ended up marrying Esther in 1937.  That's what prompted Erdös to call that question the  "Happy-End Problem".  The name stuck.
 
Esther and George, passed away together on 28 August 2005, in the same Australian nursing home, within an hour of each other.  RIP. A posthumous paper of George (2006, with L. Peters) settled  n = 6.

This is a typical Ramsey-theory problem which asks about unavoidable substructures of size n in a set of m points.  In fact, it was one of the few prototypical problems that led to the development of Ramsey theory as a proper branch of mathematics supported by a common body of knowledge.  Here's what's known so far about it:

The Happy-End Problem
Points
in the plane
Unavoidable
convex n-gon
WhenWho
221932Esther Klein
33
54
951935Paul Erdös,  George Szekeres
1762006George Szekeres,  Lindsay Peters
2 n-2  + 1n1932Klein-Szekeres Conjecture

The conjecture presented on the last line was published by Paul Erdös & George Szekeres in 1935.  At the time, they showed that a convex pentagon always exists among sets of 9 points in general position in the plane  (it's easy to find sets of 8 points which don't have any).  They also showed that, for any n, there was indeed a definite m beyond which the presence of a convex n-gon could not be avoided.

They later gave examples of sets of  2 n-2  points without a convex n-gon within them, thereby establishing their conjectured result as a lower bound.

A general upper-bound for  n ≥ 5  is due to G.Tóth and P. Valtr  (2005):

( 2n-5  )   +  1
  n-2

This is widely believed to be much larger than needed...

Wikipedia :  Happy Ending Problem
Video :  Happy Ending Problem by  Ron Graham, filmed by Brady Haran.

border
border
visits since July 16, 2007
 (c) Copyright 2000-2016, Gerard P. Michon, Ph.D.