The Erdős number

Last week's problem was very ingeniously addressed by a reader who, unfortunately, later deleted her comment. Let's see how the Hungarian mathematicians Paul Erdős and Georges Szekeres, regular collaborators and co-authors of the Erdős-Szekeres theorem , addressed it in their time. They started from the pigeonhole principle and thought of dividing the set of the first 2n numbers {1, 2, …, 2n} into n subsets such that—taking n + 1 numbers from the initial set—at least two of them were in the same subset. Thus, if these subsets were such that for any two numbers in the same subset, one was a multiple of the other, the initial statement would be proven.

For this purpose, the n subsets are defined as the intersections of the set {1, 2, …, 2n} with the following sets: {1, 2, 2², 2³…}, {3, 3 x 2, 3 x 2², 3 x 2³…}, {5, 5 x 2, 5 x 2², 5 x 2³,…}, …, {n-1, (n-1) x 2, (n-1) x 2², n-1) x 2³…}, in which each element divides the next in its subset, and in addition each number in the initial set {1, 2, …, 2n} can be written uniquely as (2m-1) x 2ᴷ, so it belongs to one of these sets. A somewhat complex explanation that Bretos Bursó summarizes as follows:

“Every natural number is the product of an even part and an odd part (the product of its prime factors equal to 2 and that of its odd prime factors). If two distinct numbers have the same odd part, then one of them divides the other (the one divisible by 2 more times than the other is a multiple of the other). The n + 1 numbers we take have n possible odd parts (1, 3, 5..., 2n-1), so there are at least two with the same odd part.”

And speaking of Erdős and collaborations between mathematicians, one cannot fail to mention the Erdős number . The prolific Hungarian mathematician had no fewer than 509 direct collaborators, whose Erdös number (nE) is 1; those who collaborated with any of these 509, but not directly with Erdös, have an nE of 2 (that's more than six thousand), and so on.

What do you think, using a Fermian estimate, might be your Erdős number? I'll settle for a reasonable approximation. (Hint: if you read this section regularly, it'll be much easier.)

The Erdős-Szekeres conjecture

The aforementioned Erdős-Szekeres theorem should not be confused with the conjecture of the same name.

The theorem states that for any pair of natural numbers (integers and positive) r and s, any sequence of length equal to or greater than (r-1)(s-1) + 1 contains a monotonically increasing subsequence of length s or a monotonically decreasing subsequence of length r.

It sounds complicated, but a simple example will clarify the concept: for r = 3 and s = 2, so (r-1)(s-1) + 1 = 3, any permutation of three numbers has either an increasing subsequence of length three or a decreasing subsequence of length two. Taking the six possible permutations of the numbers 1, 2, and 3 (and writing the sequences in simplified form):

• 123 has an increasing subsequence of length three in itself: 123
• 132 has a decreasing subsequence of length two: 32
• 213 has a decreasing subsequence of length two: 21
• 231 has two decreasing subsequences of length two: 21 and 31
• 312 has two decreasing subsequences of length two: 31 and 32
• 321 has three decreasing subsequences of length two: 32, 31 and 21

How would you approach proving this theorem from the pigeonhole principle? (I'm not asking for a rigorous proof, just a plan of attack.)

As for the Erdős-Szekeres conjecture, it's a generalization of the "happy ending problem," so named by Erdős because it led to the marriage of his friend and collaborator Georges Szekeres to the Australian mathematician Esther Klein. But that's a different article.