错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Irreducible Pairings and Indecomposable Tournaments

  • Houmem Belkhechine,
  • Cherifa Ben Salha,
  • Rim Romdhane

摘要

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