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


<p>
Résumé :<br/>
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.<br/> 
(En collaboration avec: Janos Korner)