Periods in missing lengths of rainbow cycles

✍ Scribed by Petr Vojtěchovský

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 184 KB
• Volume: 61
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20371

✦ Synopsis

Abstract

A cycle in an edge‐colored graph is said to be rainbow if no two of its edges have the same color. For a complete, infinite, edge‐colored graph G, define
Then 𝔊(G) is a monoid with respect to the operation n∘m=n+ m−2, and thus there is a least positive integer π(G), the period of 𝔊(G), such that 𝔊(G) contains the arithmetic progression {N+ k__π(G)|k⩾0} for some sufficiently large N. Given that n∈𝔊(G), what can be said about π(G)? Alexeev showed that π(G)=1 when n⩾3 is odd, and conjectured that π(G) always divides 4. We prove Alexeev's conjecture: Let p(n)=1 when n is odd, p(n)=2 when n is divisible by four, and p(n)=4 otherwise. If 2<n∈𝔊(G) then π(G) is a divisor of p(n). Moreover, 𝔊(G) contains the arithmetic progression {N+ kp(n)|k⩾0} for some N=O(n^2^). The key observations are: If 2<n=2__k∈𝔊(G) then 3__n__−8∈𝔊(G). If 16≠n=4__k__∈𝔊(G) then 3__n__−10∈𝔊(G). The main result cannot be improved since for every k>0 there are G, H such that 4__k__∈𝔊(G), π(G)=2, and 4__k__+ 2∈𝔊(H), π(H)=4. © 2009 Wiley Periodicals, Inc. J Graph Theory