Related Links (Outside this Site)

In 1928, Frank Plumpton Ramsey (1903-1930) remarked that patterns are unavoidable in large enough structures.  Altough 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.

This is arguably the simplest and most fundamental result in  Ramsey Theory.

Formally:  A function from one 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 you must have at least one drawer with 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 very large.

---

(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_k (n) :

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_k (n) = n.)

k	1	2	3	4	5	6	7
n	1	2	4	6	10	12	16

These are just one unit below the  k^th  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_k (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_n  always occurs in a large enough colored  K_m .

K_n   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	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9
3	1	3	6	9	14	18	23	28	36
4	1	4	9	18	25
5	1	5	14	25
6	1	6	18
7	1	7	23
8	1	8	28
9	1	9	36

Similarly, in a complete graph of order  R(n₁ , n₂  ... n_c )  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_i  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 special colorings of  K₁₆   avoid monochromatic triangles.)

Ramsey's Theorem  (Wikipedia)

---

(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,P²): (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?

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): (1,1) (1,2) (1,3) (2,4) (2,5) (2,6) (2,7) (2,8) (3,9) (3,10) ... 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 theorem:  Joseph 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 will not share... 

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 MD² 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 D² lines of slope q which contain each at least one integral point from each of those MD² 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 ...

---

(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 prograssions 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