A problem and a bet

In the young but flourishing subject of permutation patterns, it is usual to regard a permutation of {1,…,n} as simply a sequence containing each of these numbers just once. So 31542 is a permutation of {1,…,5}. This is in agreement with the nineteenth-century usage, and indeed with the non-mathematical usage, of the term, reserving the word “substitution” for the corresponding bijective mapping (in this case, taking 1 to 3, 2 to 1, etc.)

A permutation p of {1,…,m} occurs in a permutation q of {1,…,n} if there are m symbols in q which occur in the same order as the symbols in p. Thus for example, the permutation 132 occurs in the permutation 31542 since the red symbols have the same order as 132: smallest first, largest second, intermediate third.

I have explained here my slightly different view: a permutation is a set carrying two total orders; “occurs in” means “is an induced substructure of”. But for now we will follow the usual view.

One of the concerns of the theory of permutation patterns is: given a permutation p of {1,…,m}, how many permutations of {1,…,n} avoid it (in the sense that it does not occur)? The problem is trivial for m=1 and m=2. For m=3, something remarkable happens: the number is always the same, no matter what p is; in fact, the number is the famous Catalan number.

What about m=4? The function giving the number of avoiding permutations is one of three possibilities for any choice of p; they are realised by the three permutations 1234, 1342 and 1324. For the first two the function is known; for the third, it is still a mystery, and even its rate of growth is not known very precisely.

At the BCC, Einar Steingrímsson talked about permutation patterns, and revealed that he has a bet with Doron Zeilberger about this. If someone comes up with the answer this year, Doron will pay Einar 170 euros. The amount paid out will decrease by ten euros with every year that passes before the solution is found, and if it is not found by the year 2030 then Doron wins the bet and Einar will pay him 170 euros. In his paper he summarises the situation thus:

… Doron Zeilberger is claimed to have said that “Not even God knows the number of 1324-avoiders of length 1000.” I’m not sure how good Zeilberger’s God is at math, but I believe that some humans will find this number in the not so distant future.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in events, open problems and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s