Pairwise colliding permutations and the capacity of infinite graphs | Zendy

János Körner | Zendy; Claudia Malvenuto | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Pairwise colliding permutations and the capacity of infinite graphs

Author(s) -

János Körner,

Claudia Malvenuto

Publication year - 2006

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/050632877

Subject(s) - combinatorics , pairwise comparison , mathematics , cardinality (data modeling) , chromatic scale , exponential function , discrete mathematics , graph , enumeration , set (abstract data type) , finite set , computer science , statistics , mathematical analysis , data mining , programming language

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

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research