Archive

Posts Tagged ‘Bijection’

ICM Paper

March 14, 2018 2 comments

Well, I finally finished my ICM paper. It’s only 30 pp, but it took many sleepless nights to write and maybe about 10 years to understand what exactly do I want to say. The published version will be a bit shorter – I had to cut section 4 to satisfy their page limitations.

Basically, I give a survey of various recent and not-so-recent results in Enumerative Combinatorics around three major questions:

(1) What is a formula?
(2) What is a good bijection?
(3) What is a combinatorial interpretation?

Not that I answer these questions, but rather explain how one could answer them from computational complexity point of view. I tried to cover as much ground as I could without overwhelming the reader. Clearly, I had to make a lot of choices, and a great deal of beautiful mathematics had to be omitted, sometimes in favor of the Computational Combinatorics approach. Also, much of the survey surely reflects my own POV on the subject. I sincerely apologize to everyone I slighted and who disagrees with my opinion! Hope you still enjoy the reading.

Let me mention that I will wait for a bit before posting the paper on the arXiv. I very much welcome all comments and suggestions! Post them here or email privately.

P.S. In thinking of how approach this paper, I read a large number of papers in previous ICM proceedings, e.g. papers by Noga Alon, Mireille Bousquet-Mélou, Paul Erdős, Philippe Flajolet, Marc Noy, János Pach, Richard Stanley, Benny Sudakov, and many others. They are all terrific and worth reading even if just to see how the field has been changing over the years. I also greatly benefited from a short introductory article by Doron Zeilberger, which I strongly recommend.

A lost bijection

July 11, 2012 1 comment

One can argue whether some proofs are from the book, while others maybe not. Some such proofs are short but non-elementary, others are elementary but slightly tedious, yet others are short but mysterious, etc. (see here for these examples). BTW, can one result have two or more “proofs from the book”?

However, very occasionally you come across a proof that is both short, elementary and completely straightforward. One would call such a proof trivial, if not for the fact that it’s brand new. I propose a new term for these – let’s call them lost proofs, loosely defined as proofs which should have been discovered decades or centuries ago, but evaded this fate for whatever accidental historical circumstances (as in lost world, get it?) And when you find such a proof you sort of can’t believe it. Really? This is true? This is new? Really? Really?!?

Let me describe one such lost proof. This story started in 1857 when Arthur Cayley wrote “On a problem in the partition of numbers”, with the following curious result:

The number of integer sequences $(a_1,\ldots,a_n)$ such that $1\le a_1 \le 2$, and $1\le a_{i+1} \le 2 a_i$ for $1\le i < n$, is equal to the total number of partitions of integers $N \in \{0,1,\ldots,2^{n}-1\}$ into parts $1,2,4,\ldots,2^{n-1}$.

For example, for $n=2$ the first set is sequences is $\{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (2, 4)\}$, while the second of partitions is $\{21, 2, 1^3, 1^2, 1, \varnothing\}$, both with six elements.

This result was discovered about 20-25 years too soon. In 1879-1882, while at Johns Hopkins University, Sylvester pioneered what he called a “constructive partition theory”, and had he seen his good friend’s older paper, he probably would have thought about finding a bijective proof. Apparently, he didn’t. In all fairness to everybody involved, Cayley had written over 900 papers.

Now, the problem was rediscovered by Minc (1959), and notably by Andrews, Paule, Riese and Strehl (2001) as a biproduct of computer experiments. Both Cayley’s and APRS’s proofs are analytic (using generating functions). More recent investigations by Corteel, Lee and Savage (2005 and 2007 papers), and Beck, Braun and Le (2011) proved various extensions, still using generating functions.

We are now ready for the “lost proof”, which is really a lost bijection. It’s given by just one formula, due to Matjaž Konvalinka and me:

$\Psi: (a_1,a_2,a_3,\ldots,a_n) \to [2^{n-1}]^{2-a_1} [2^{n-2}]^{2a_1-a_2}[2^{n-3}]^{2a_2-a_3} \ldots 1^{2a_{n-1}-a_n}$

For example, for $n=2$ we get the following bijection:

$\Psi: (1,1) \to 21, \ (1,2) \to 2, \ (2,1) \to 1^3, \ (2,2) \to 1^2, \ (2,3) \to 1, \ (2,4) \to \varnothing.$

Of course, once the bijection is found, the proof of Cayley’s theorem is completely straightforward. Also, once you have such an affine formula, many extensions become trivial.

One wonders, how does one can come up with such a bijection. The answer is: simply compute it assuming there is an affine map. It tends to be unique. Also, we have done this before (for convex partitions and LR-coefficients). There is a reason why this bijection is so similar to Sylvie Corteel’s “brilliant human-generated one-line proof” in the words of Doron Zeilberger. So it’s just amazing that this simple proof has been “lost” for over 150 years, until now…

See our paper (Konvalinka and Pak, “Cayley compositions, partitions, polytopes, and geometric bijections”, 2012) for applications of this “lost bijection” and my survey (Pak, “Partition Bijections, a Survey”, 2006) for more on partition bijections.

Categories: Mathematics, New papers