 |
Ramsey Theory
(2007-07-16)
The Pigeonhole Principle
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.
 (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?
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.
(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 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 ...
|
|
|
