On types of growth for graph-different permutations

DOI10.1016/J.JCTA.2008.11.003zbMATH Open1211.05150arXiv0712.1442OpenAlexW1941378564MaRDI QIDQ1024371FDOQ1024371

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)

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".

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

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

zbMATH Keywords

permutationsextremal combinatoricsShannon capacity of graphs

Mathematics Subject Classification ID

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

Cites Work

• On the Shannon capacity of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distance graphs with finite chromatic number
• Pairwise colliding permutations and the capacity of infinite graphs
• On the capacity of the arbitrarily varying channel for maximum probability of error
• Graph-Different Permutations

Cited In (9)

• 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
• Permutation capacities of families of 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)