Irreducible pairings and indecomposable tournaments

Abstract

We only consider finite structures. With every totally ordered set $V$ and a subset $P$ of $\left(\genfrac{}{}{0ex}{}{V}{2}\right)$, we associate the underlying tournament $\mathrm{Inv}(\underline{V},P)$ obtained from the transitive tournament $\underline{V}:=(V,\{(x,y)\in V\times V:x<y\})$ by reversing $P$, i.e., by reversing the arcs $(x,y)$ such that $\{x,y\}\in P$. The subset $P$ is a pairing (of $\cup P$) if $|\cup P|=2|P|$, a quasi-pairing (of $\cup P$) if $|\cup P|=2|P|-1$; it is irreducible if no nontrivial interval of $\cup P$ is a union of connected components of the graph $(\cup 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 $\mathrm{Inv}(\underline{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.

17 pages