On types of growth for graph-different permutations

DOI10.1016/J.JCTA.2008.11.003MaRDI QIDQ1024371zbMATH OpenOpenAlexFDO

Authors János Körner, Gábor Simonyi, Blerina Sinaimeri

Publication date 17 June 2009

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0712.1442

zbMATH Keywords

permutationsextremal combinatoricsShannon capacity of graphs

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: We consider an infinite graph G whose vertex set is the set of natural numbers and adjacency depends solely on the difference between vertices. We study the largest cardinality of a set of permutations of [n] any pair of which differ somewhere in a pair of adjacent vertices of G and determine it completely in an interesting special case. We give estimates for other cases and compare the results in case of complementary graphs. We also explore the close relationship between our problem and the concept of Shannon capacity "within a given type".

Recommendations

• Graph-Different Permutations
• Pairwise colliding permutations and the capacity of infinite graphs
• Permutation capacities of families of oriented infinite paths
• Maximum size of a family of pairwise graph-different permutations
• Divergent permutations

Cites work

• scientific article; zbMATH DE number 3908323 (Why is no real title available?)
• scientific article; zbMATH DE number 1131873 (Why is no real title available?)
• Distance graphs with finite chromatic number
• Graph-Different Permutations
• On the Shannon capacity of a graph
• On the capacity of the arbitrarily varying channel for maximum probability of error
• Pairwise colliding permutations and the capacity of infinite graphs

Cited in

(9)

• Permutation capacities of families of oriented infinite paths
• Triangle-different Hamiltonian paths
• New bounds on even cycle creating Hamiltonian paths using expander graphs
• Divergent permutations
• On \(k\)-neighbor separated permutations
• Graph-Different Permutations
• Pairwise colliding permutations and the capacity of infinite graphs
• Maximum size of a family of pairwise graph-different permutations
• Permutation capacities and oriented infinite paths

This page was built for publication: On types of growth for graph-different permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024371)