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. © 2006 Society for Industrial and Applied Mathematics.
Pairwise colliding permutations and the capacity of infinite graphs / Korner, Janos; Malvenuto, Claudia. - In: SIAM JOURNAL ON DISCRETE MATHEMATICS. - ISSN 0895-4801. - STAMPA. - 20:1(2006), pp. 203-212. [10.1137/050632877]
Pairwise colliding permutations and the capacity of infinite graphs
KORNER, JANOS;MALVENUTO, Claudia
2006
Abstract
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. © 2006 Society for Industrial and Applied Mathematics.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
