Families of Very Different Paths

Let D ⊆ N be an arbitrary subset of the natural numbers. For every n, let M ( n , 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 D . We determine or bound the asymptotics of M ( n , 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 more ambitious generalizations where paths are replaced by other graphs. 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.