Graph-Different Permutations
Authors:
- János KörnerJKJános Körner
- Claudia MalvenutoCMClaudia Malvenuto
- Gábor SimonyiGSGábor Simonyi
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 22 (2) , 489-499
Abstract
For a finite graph G whose vertices are different natural numbers we call two infinite permutations of the natural numbers G-different if they have two adjacent vertices of G somewhere in the same position. The maximum number of pairwise G-different permutations of the naturals is always finite. We study this maximum as a graph invariant and relate it to a problem of the first two authors on colliding permutations. An improvement on the lower bound for the maximum number of pairwise colliding permutations is obtained.Keywords
All Related Versions
This publication has 3 references indexed in Scilit:
- Pairwise colliding permutations and the capacity of infinite graphsSIAM Journal on Discrete Mathematics, 2006
- Zero-error information theoryIEEE Transactions on Information Theory, 1998
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956