(2007-07-16) 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 byDirichlet 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 conceptin several languages, including French (principe des tiroirs)... If you have more socks than drawers toput 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 toat 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) ... will always contain twocoprime integers. Prove it!
In the summer of 1959,PaulErdö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 eatinghis soup in half a minute or so.
(2009-01-19) How many can you pick without having k+1 of them pairwisecoprime?
Theprevious question is actually a special case (k = 1) of a difficult problem: What's the largest number b of positive integersnot 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 numbersis 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 (seeA006093). (: 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 tothe number of integers not exceeding n which are divisible by at least one of the first k primes.
That conjecture was disproved in 1994 by Ahlswede and Khachatrian.
(2009-01-14) A monochromatic clique Kn can always be found in any2-coloring of the clique Km , if m ≥ R(n.n).
Kn is theundirectedcomplete 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 containeither a complete graph of order r with red edges onlyor 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 theoremon 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 trianglesexist in any tri-colored complete graphof 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 oflattice pointswhere the distance [orgap] 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 to2. 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 existfor any given M (say M=1000000)at least M collinear points in such a sequence...(Seenext 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 someonewould find it as appealing as I do. However, I cannot take credit for posing this problem, as it is a classic question inRamsey 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
[Affirmative answer to thesecond part of the question.] This obscure result is indeed sometimes known as theGerver-Ramsey theorem: Joseph L. Gerver andL. Thomas Ramsey,On certain sequences of lattice points, Pacific J. Math. 83 (1979) 357-363,MR81c:10039. It is, in fact, enough to assume only that thegaps[the distances between pairs of consecutive points]are boundedon average(which is to say that the sum of the first ngaps 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.
(2000-09-29) In the plane, an infinite sequence oflattice points with boundedgaps 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 whichMarc 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 infinitelymany elements of the sequence arecollinearbecause they areequal).
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 areadjacent(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 obtainedby removing from the sequence (floor(X(n)/D),floor(Y(n)/D)) any consecutive elements whichhappen to be equal. Since C is a sequence ofadjacent points, the restricted theorem implies that,for any M, there is at least one straight line (with some rationalslope q) going through MD2 elements of C. Well, C clearly corresponds to D by D square cellswhich contain each at least one element from the original sequence S. To the above line ofslope q corresponds a set of at most D2 lines of slope q which contain each atleast one integral point from each of those MD2 aligned cell. Thepigeonhole principlethen tells us that at least one such line contains at least M points from the originalsequence S. In other words,the theorem for adjacent consecutive points does imply the general case whereconsecutive points are only known to be less than some distance D apart.
We now complete the proof by ...
(2009-06-27) With finitely many colors of integers, there must bearbitrarily longarithmetic progressions of the same color.
For instance, the van der Waerden theorem states thatarbitrarily long arithmetic progressions must exist which consist entirely eitherof prime numbers or of other integers. (Actually, both alternatives are true; the latter is trivial and the former isthe celebratedGreen-Tao theorem.)
(2014-07-28) 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 whoconvened regularly, includingPaul Erdös (1913-1996)George Szekeres (1911-2005)andPaul 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 theconvex hull of the others).
This is a typical Ramsey-theory problem which asks about unavoidable substructures of size nin a set of m points. In fact, it was one of the few prototypical problems that led tothe development of Ramsey theory as a proper branch of mathematics supported by a commonbody 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 byPaul Erdös & George Szekeres in 1935. At the time, they showed that a convex pentagon always exists among setsof 9 points in general position in the plane (it's easy to findsets of 8 points which don't have any). They also showed that, for any n, there was indeed a definite m beyondwhich the presence of a convex n-gon could not be avoided.
They later gave examples of sets of 2 n-2 pointswithout a convex n-gon within them, thereby establishing their conjecturedresult 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) 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 = 2 + 2 = 2 + 2
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 avoidany 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
