2011/06/19 by János Körner, Körner, János, Silvia Messuti +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Information Theory (cs.IT) #Limits and Structures in Graph Theory #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.1106.3754
arxiv created 2011/06/19 · openalex publication_date 2011/06/19 · arxiv updated 2011/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let D 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 Kn 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 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.