1. Irreducible Pairings and Indecomposable Tournaments.
- Author
-
Belkhechine, Houmem, Ben Salha, Cherifa, and Romdhane, Rim
- Abstract
We only consider finite structures. With every totally ordered set V and a subset P of V 2 , we associate the underlying tournament Inv (V ̲ , P) obtained from the transitive tournament V ̲ : = (V , { (x , y) ∈ V × V : x < y }) by reversing P, i.e., by reversing the arcs (x, y) such that { x , y } ∈ P . The subset P is a pairing (of ∪ P ) if | ∪ P | = 2 | P | , a quasi-pairing (of ∪ P ) if | ∪ P | = 2 | P | - 1 ; it is irreducible if no nontrivial interval of ∪ P is a union of connected components of the graph (∪ P , P) . In this paper, we consider pairings and quasi-pairings in relation to tournaments. We establish close relationships between irreducibility of pairings (or quasi-pairings) and indecomposability of their underlying tournaments under modular decomposition. For example, given a pairing P of a totally ordered set V of size at least 6, the pairing P is irreducible if and only if the tournament Inv (V ̲ , P) is indecomposable. This is a consequence of a more general result characterizing indecomposable tournaments obtained from transitive tournaments by reversing pairings. We obtain analogous results in the case of quasi-pairings. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF