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. The bigest breakthrough in basic Ramsey theory occurred in 2023:
(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-4 and x-9
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.
(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 bk (n) :
k
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1
1
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
2
1
2
2
3
3
4
4
5
6
7
7
8
8
9
10
11
11
12
3
1
2
3
4
4
5
5
6
7
8
8
9
9
10
11
12
12
13
4
1
2
3
4
5
6
6
7
8
9
9
10
10
11
12
13
13
14
5
1
2
3
4
5
6
7
8
9
10
10
11
11
12
13
14
6
1
2
3
4
5
6
7
8
9
10
11
12
12
13
14
7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
bk (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 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
bk (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.
(2009-01-14) Ramsey's Theorem (Frank Ramsey, 1930)
A monochromatic clique Kn can always be found in any
2-coloring of the clique Km , if m ≥ R(n.n).
Kn is the undirectedcomplete graph (or clique) 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 fact that R(3,3) = 6 is known as the
theorem
on friends and strangers: In a group of 6 people,
there's always a group of 3 who know each other or a group of 3 who don't.
This need not be so in a group of 5 people or less.
R(r,b) is not difficult to compute 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(n1 , n2 ... nc )
whose edges are colored using c colors
(1, 2 ... c) there will always besome color i
for which at least one complete subgraph of order ni
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.)
(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...
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):
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 would 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 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 ...
(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.)
(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
convexpolygon
(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
When
Who
2
2
1932
Esther Klein
3
3
5
4
9
5
1935
Paul Erdös, George Szekeres
17
6
2006
George Szekeres, Lindsay Peters
2 n-2 + 1
n
1932
Klein-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...
(2018-05-18) Monochromatic Pythagorean triples among 1,2, ... N.
With just two colors, they can't be avoided if N is 7825 or more.
A computer proof was released (by Marijn Heule, Oliver Kullmann & Victor Marek) in May 2016,
which required 200 TB of computer memory. It's been heralded as the largest
proof ever produced (so far).
It turns out that
78252 =
78002 + 6252
=
58652 + 51802
The problem is that all two-color colorings of the numbers from 1 to 7824 which avoid
pythagorean triples (coprime or not)
will have 7800 and 625 share the same color
(blue, say) while 5865 and 5180 are of the other color (red).
So, whichever way we color 7825 we obtain a monochromatic Pythagorean triple
(albeit not consisting of coprime integers).
Now, using three colors, can we color all positive integers to avoid
any monochromatic Pythagorean triples?
(Marc Ordower of Bryan, TX. 
No, there need not be an infinite subset of collinear points in this case either...
Consider the sequence of points whose general term is
