[FORTHCOMING] Les tournois indécomposables à indice de Slater minimal

The Slater index (resp. decomposability index) of a tournament is the minimum number of arcs that must be reversed in that tournament in order to make it a total order (resp. indecomposable (under modular decomposition)). The first author [H. Belkhechine, Decomposability index of tournaments, Discrete Math. 340 (2017) 2986–2994] showed that for every integer $$$n \geq 5$$$, the decomposability index of the $$$n$$$-vertex total order equals $$$\left\lceil \frac{n+1}{4} \right\rceil$$$. It follows that the Slater index of an indecomposable $$$n$$$-vertex tournament is at least $$$\left\lceil \frac{n+1}{4} \right\rceil$$$. This led A. Boussaïri to ask the following question during the thesis defense of the second author on July 2, 2021 : what are the indecomposable tournaments $$$T$$$ whose Slater index is minimum over all indecomposable tournaments with the same vertex set as $$$T$$$ ? These tournaments are then the indecomposable tournaments $$$T$$$ obtained from a total order by reversing exactly $$$\left\lceil \frac{v(T)+1}{4} \right\rceil$$$ arcs, where $$$v(T)$$$ is the number of vertices of $$$T$$$. In this paper, we characterize such tournaments by means of so-called irreducible pairings.

The Slater index (resp. decomposability index) of a tournament is the minimum number of arcs that must be reversed in that tournament in order to make it a total order (resp. indecomposable (under modular decomposition)). The first author [H. Belkhechine, Decomposability index of tournaments, Discrete Math. 340 (2017) 2986–2994] showed that for every integer $$$n \geq 5$$$, the decomposability index of the $$$n$$$-vertex total order equals $$$\left\lceil \frac{n+1}{4} \right\rceil$$$. It follows that the Slater index of an indecomposable $$$n$$$-vertex tournament is at least $$$\left\lceil \frac{n+1}{4} \right\rceil$$$. This led A. Boussaïri to ask the following question during the thesis defense of the second author on July 2, 2021: what are the indecomposable tournaments $$$T$$$ whose Slater index is minimum over all indecomposable tournaments with the same vertex set as $$$T$$$? These tournaments are then the indecomposable tournaments $$$T$$$ obtained from a total order by reversing exactly $$$\left\lceil \frac{v(T)+1}{4} \right\rceil$$$ arcs, where $$$v(T)$$$ is the number of vertices of $$$T$$$. In this paper, we characterize such tournaments by means of so-called irreducible pairings.

Module pairing indecomposable irreducible decomposability index Slater index

Module pairing indecomposable irreducible decomposability index Slater index