|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Periods in missing lengths of rainbow cycles | | Petr Vojtěchovský
; | | Date: |
18 Sep 2015 | | 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
$mathfrak{S}(G)={nge 2;|; ext{no $n$-cycle of $G$ is rainbow}}$. Then
$mathfrak{S}(G)$ is a monoid with respect to the operation $ncirc m = n+m-2$,
and thus there is a least positive integer $pi(G)$, the period of
$mathfrak{S}(G)$, such that $mathfrak{S}(G)$ contains the arithmetic
progression ${N+kpi(G);|;kge 0}$ for some sufficiently large $N$.
Given that $ninmathfrak{S}(G)$, what can be said about $pi(G)$? Alexeev
showed that $pi(G)=1$ when $nge 3$ is odd, and conjectured that $pi(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<ninmathfrak{S}(G)$ then $pi(G)$ is a divisor of
$p(n)$. Moreover, $mathfrak{S}(G)$ contains the arithmetic progression
${N+kp(n);|;kge 0}$ for some $N=O(n^2)$. The key observations are: If
$2<n=2kinmathfrak{S}(G)$ then $3n-8inmathfrak{S}(G)$. If $16
e
n=4kinmathfrak{S}(G)$ then $3n-10inmathfrak{S}(G)$.
The main result cannot be improved since for every $k>0$ there are $G$, $H$
such that $4kinmathfrak{S}(G)$, $pi(G)=2$, and $4k+2inmathfrak{S}(H)$,
$pi(H)=4$. | | Source: | arXiv, 1509.5632 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER