Jeudi 15 février 2007.
Oratrice : Claudia Malvenuto (Univ. Rome 1).
Titre : Pairwise colliding permutations and the capacity of infinite graphs.

Résumé :
We call two permutations of the first n naturals colliding if they map at least one number to consecutive naturals. We give bounds for the exponential asymptotics of the largest cardinality of any set of pairwise colliding permutations of [n]. We relate this problem to the determination of the Shannon capacity of an infinite graph and initiate the study of analogous problems for infinite graphs with finite chromatic number.
(En collaboration avec: Janos Korner)