Families of Graph-different Hamilton Paths
Authors:
- János KörnerJKJános Körner
- Silvia MessutiSMSilvia Messuti
- Gábor SimonyiGSGábor Simonyi
- 1 January 2012
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 26 (1) , 321-329
Abstract
Let $\mathbb{D}\subseteq \mathbb{N}$ be an arbitrary subset of the natural numbers. For every n, let $M(n, \mathbb{D})$ be the maximum of the cardinality of a set of Hamiltonian paths in the complete graph $K_n$ such that the union of any two paths from the family contains a not necessarily induced cycle of some length from $\mathbb{D}$. We determine or bound the asymptotics of $M(n, \mathbb{D})$ in various special cases. This problem is closely related to that of the permutation capacity of graphs and constitutes a further extension of the problem area around Shannon capacity. We also discuss how to generalize our cycle-difference problems and present an example where cycles are replaced by 4-cliques. These problems are in a natural duality to those of graph intersection, initiated by Erdős, Simonovits, and Sós. The lack of kernel structure as a natural candidate for optimum makes our problems quite challenging.
Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- Permutation Capacities of Families of Oriented Infinite PathsSIAM Journal on Discrete Mathematics, 2010
- Pairwise colliding permutations and the capacity of infinite graphsSIAM Journal on Discrete Mathematics, 2006
- Intersection Theorems on Structures1980
- INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETSThe Quarterly Journal of Mathematics, 1961
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956