Monochromatic Hamiltonian t-tight Berge-cycles in hypergraphs

✍ Scribed by Paul Dorbec; Sylvain Gravier; Gábor N. Sárközy

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 141 KB
• Volume: 59
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20329

✦ Synopsis

Abstract

In any r‐uniform hypergraph ${\cal{H}}$ for 2 ≤ t ≤ r we define an r‐uniform t‐tight Berge‐cycle of length ℓ, denoted by C~ℓ~^(r, t)^, as a sequence of distinct vertices v~1~, v~2~, … , v~ℓ~, such that for each set (v~i~, v~i + 1~, … , v~i + t − 1~) of t consecutive vertices on the cycle, there is an edge E~i~ of ${\cal{H}}$ that contains these t vertices and the edges E~i~ are all distinct for i, 1 ≤ i ≤ ℓ, where ℓ + j ≡ j. For t = 2 we get the classical Berge‐cycle and for t = r we get the so‐called tight cycle. In this note we formulate the following conjecture. For any fixed 2 ≤ c, t ≤ r satisfying c + t ≤ r + 1 and sufficiently large n, if we color the edges of K~n~^(r)^, the complete r‐uniform hypergraph on n vertices, with c colors, then there is a monochromatic Hamiltonian t‐tight Berge‐cycle. We prove some partial results about this conjecture and we show that if true the conjecture is best possible. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 34–44, 2008