Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2511.11037 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914158368260096 |
|---|---|
| author | Nokhrin, Sergei Patrakeev, Mikhail |
| author_facet | Nokhrin, Sergei Patrakeev, Mikhail |
| contents | Tournament ranking is a function that assigns each vertex of a tournament (i.e., a directed graph without loops, in which each pair of different vertexes is connected by exactly one arc) a number called the rank of the vertex. One of approaches to constructing tournament rankings suggests choosing a ranking that satisfies a fixed set of axioms. In another approach, proposed by Erdős and Moon, only injective rankings are considered, and among them, one that minimises the number of backward arcs is selected (an arc $x\to y$ is called backward iff the rank of $x$ is less than the rank of $y$). We combine these two approaches as follows: among the rankings that satisfy a fixed set of axioms, we choose one that minimises the number of backward arcs.
The Erdős-Moon approach naturally leads to the question of how small the proportion of backward arcs can be guaranteed when using injective rankings. Erdős and Moon showed that the answer to this question is $1/2$. A similar question arises in our approach: how small the proportion of backward arcs can be guaranteed when using rankings that satisfy a set of axioms $\mathcal{A}$? We call this number the Erdős-Moon number of $\mathcal{A}$. We prove that the Erdős-Moon number of the Copeland axiom equals $3/4$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_11037 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Axiomatic and Erdős-Moon approaches to tournament rankings Nokhrin, Sergei Patrakeev, Mikhail Combinatorics 05C20 Tournament ranking is a function that assigns each vertex of a tournament (i.e., a directed graph without loops, in which each pair of different vertexes is connected by exactly one arc) a number called the rank of the vertex. One of approaches to constructing tournament rankings suggests choosing a ranking that satisfies a fixed set of axioms. In another approach, proposed by Erdős and Moon, only injective rankings are considered, and among them, one that minimises the number of backward arcs is selected (an arc $x\to y$ is called backward iff the rank of $x$ is less than the rank of $y$). We combine these two approaches as follows: among the rankings that satisfy a fixed set of axioms, we choose one that minimises the number of backward arcs. The Erdős-Moon approach naturally leads to the question of how small the proportion of backward arcs can be guaranteed when using injective rankings. Erdős and Moon showed that the answer to this question is $1/2$. A similar question arises in our approach: how small the proportion of backward arcs can be guaranteed when using rankings that satisfy a set of axioms $\mathcal{A}$? We call this number the Erdős-Moon number of $\mathcal{A}$. We prove that the Erdős-Moon number of the Copeland axiom equals $3/4$. |
| title | Axiomatic and Erdős-Moon approaches to tournament rankings |
| topic | Combinatorics 05C20 |
| url | https://arxiv.org/abs/2511.11037 |