Lundi 22 septembre 2008, à 16h en amphi Rubis.
Orateur : János Körner (Univ. Rome "La Sapienza").
Titre : Permutation capacity.

How many permutations of the first n natural numbers can we find such that any two of them place two consecutive natural numbers somewhere in the same position? This problem was introduced by the speaker and Malvenuto who conjectured that the maximum number of such permutations is exactly the middle binomial coefficient {n \choose |_n/2_|}.

This conjecture has been neither disproved nor confirmed so far. Our combinatorial puzzle is closely connected to Shannon's graph capacity concept and the rich and beautiful mathematics around it. We will survey some of the numerous generalizations of this problem and indicate its relations to the well-known topic of pattern avoidance in permutations, in particular the conjecture of Stanley-Wilf recently proved by Tardos and Marcus.