Anti-Ramsey Number Of Matchings In Hypergraphs

Abstract

A k-matching in a hypergraph is a set of k edges such that no two of these edges intersect. The anti-Ramsey number of a k-matching in a complete s-uniform hypergraph H on n vertices, denoted by ar(n, s, k), is the smallest integer c such that in any coloring of the edges of H with exactly c colors, there is a k-matching whose edges have distinct colors. The Turan number, denoted by ex(n, s, k), is the the maximum number of edges in an s-uniform hypergraph on n vertices with no k-matching. For k >= 3, we conjecture that if n > sk, then ar(n, s, k) = ex(n, s, k 1) + 2. Also, if n = sk, then ar(n, s, k) = {ex(n, s, k - 1) + 2 if k < c(s) ex(n, s, k - 1) + S + 1 if k >= c(s,) where c(s) is a constant dependent on s. We prove this conjecture k = 2, k = 3, and sufficiently large n, as well as provide upper and lower bounds. (C) 2013 Elsevier B.V. All rights reserved.