2019/01/18 by Gu, Ran, Li, Jiaao, Shi, Yongtang · 5 citations
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1901.06092
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 path extension technique and stability results on hypergraph Turán problems of paths and cycles.