Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2403.07629 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913262485897216 |
|---|---|
| author | Savchenko, Sergey |
| author_facet | Savchenko, Sergey |
| contents | For a regular tournament $T$ of order $n,$ denote by $c_{8}(T)$ the number of cycles of length $8$ in $T.$ Let $DR_{n}$ be a doubly-regular tournament of order $n\equiv 3\mod4$ (so, the out-sets and in-sets of its vertices are also regular and hence, contain the maximum possible number of cyclic triples) and $RLT_{n}$ be the unique regular locally transitive tournament of (odd) order $n$ (so, the out-sets and in-sets of its vertices are transitive and hence, contain no cyclic triples, at all). Some arguments based on the spectral properties of tournaments allow us to suggest that $c_{8}(T) \le c_{8}(RLT_{n}),$ where $n$ is sufficiently large. This restriction on $n$ is essential because our computer processing of B. McKay's file of tournaments implies that for $n=9,11,13,$ the maximum of $c_{8}(T)$ is attained at tournaments with regular structure of the out and in-sets of their vertices. In the present paper, we show that $c_{8}(DR_{n})$ does not depend on a particular choice of $DR_{n}$ and determine expressions for $c_{8}(DR_{n})$ and $c_{8}(RLT_{n}).$ They are both polynomials of degree $8$ in $n.$ Comparing $c_{8}(DR_{n})$ with $c_{8}(RLT_{n})$ yields the inequality $c_{8}(DR_{n})>c_{8}(RLT_{n})$ for $11\le n\le 35,$ while $c_{8}(RLT_{n}) > c_{8}(DR_{n})$ for $n\ge 39.$ This allows us to treat the value $n=39$ as the point of phase transition in the local properties of maximizers and minimizers of $c_{8}(T)$ in the class of regular tournaments of order $n.$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07629 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the number of 8-cycles for two particular regular tournaments of order N with diametrically opposite local properties Savchenko, Sergey Combinatorics For a regular tournament $T$ of order $n,$ denote by $c_{8}(T)$ the number of cycles of length $8$ in $T.$ Let $DR_{n}$ be a doubly-regular tournament of order $n\equiv 3\mod4$ (so, the out-sets and in-sets of its vertices are also regular and hence, contain the maximum possible number of cyclic triples) and $RLT_{n}$ be the unique regular locally transitive tournament of (odd) order $n$ (so, the out-sets and in-sets of its vertices are transitive and hence, contain no cyclic triples, at all). Some arguments based on the spectral properties of tournaments allow us to suggest that $c_{8}(T) \le c_{8}(RLT_{n}),$ where $n$ is sufficiently large. This restriction on $n$ is essential because our computer processing of B. McKay's file of tournaments implies that for $n=9,11,13,$ the maximum of $c_{8}(T)$ is attained at tournaments with regular structure of the out and in-sets of their vertices. In the present paper, we show that $c_{8}(DR_{n})$ does not depend on a particular choice of $DR_{n}$ and determine expressions for $c_{8}(DR_{n})$ and $c_{8}(RLT_{n}).$ They are both polynomials of degree $8$ in $n.$ Comparing $c_{8}(DR_{n})$ with $c_{8}(RLT_{n})$ yields the inequality $c_{8}(DR_{n})>c_{8}(RLT_{n})$ for $11\le n\le 35,$ while $c_{8}(RLT_{n}) > c_{8}(DR_{n})$ for $n\ge 39.$ This allows us to treat the value $n=39$ as the point of phase transition in the local properties of maximizers and minimizers of $c_{8}(T)$ in the class of regular tournaments of order $n.$ |
| title | On the number of 8-cycles for two particular regular tournaments of order N with diametrically opposite local properties |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.07629 |