Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs
Ran Gu, Jiaao Li, Yongtang Shi
Abstract
The anti-Ramsey problem was introduced by Erdös, Simonovits, and Sós in 1970s. The anti-Ramsey number of a hypergraph H, ar(n,s, H), is the smallest integer c such that in any coloring of the edges of the s-uniform complete hypergraph on n vertices with exactly c colors, there is a copy of H whose edges have distinct colors. In this paper, we determine the anti-Ramsey numbers of linear paths and loose paths in hypergraphs for sufficiently large n and give bounds for the anti-Ramsey numbers of Berge paths. Similar exact anti-Ramsey numbers are obtained for linear/loose cycles, and bounds are obtained for Berge cycles. Our main tools are the path extension technique and stability results on hypergraph Turán problems of paths and cycles.