×

Inversions in tournaments. (Inversion dans les tournois.) (French. Abridged English version) Zbl 1209.05105

Summary: We consider the transformation reversing all arcs of a subset \(X\) of the vertex set of a tournament \(T\). The index of \(T\), denoted by \(i(T)\), is the smallest number of subsets that must be reversed to make \(T\) acyclic. It turns out that critical tournaments and \((-1)\)-critical tournaments can be defined in terms of inversions (at most two for the former, at most four for the latter). We interpret \(i(T)\) as the minimum distance of \(T\) to the transitive tournaments on the same vertex set, and we interpret the distance between two tournaments \(T\) and \(T^{\prime}\) as the Boolean dimension of a graph, namely the Boolean sum of T and \(T^{\prime}\). On n vertices, the maximum distance is at most \(n - 1\), whereas \(i(n)\), the maximum of \(i(T)\) over the tournaments on \(n\) vertices, satisfies \( \frac {n-1}{2} - \log_2 n \leqslant i(n) \leqslant n-3\), for \(n \geqslant 4\). Let \(\mathcal I^{<\omega}_m\) (resp. \(\mathcal I^{\leqslant \omega}_m\)) be the class of finite (resp. at most countable) tournaments \(T\) such that \(i(T) \leqslant m\). The class \(\mathcal I^{<\omega}_m\) is determined by finitely many obstructions. We give a morphological description of the members of \(\mathcal I^{<\omega}_1\) and a description of the critical obstructions. We give an explicit description of a universal tournament of the class \(\mathcal I^{\leqslant \omega}_m\).

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[2] Belkhechine, H.; Boudabbous, I.; Dammak, J., Morphologie des tournois \((- 1)\)-critiques, C. R. Acad. Sci. Paris Ser. I, 345, 663-666 (2007) · Zbl 1188.05071
[3] Bondy, J. A.; Murty, U. S.R., Graph Theory, Graduate Texts in Mathematics, vol. 244 (2008), Springer, 651 pp · Zbl 1134.05001
[4] Boudabbous, Y.; Pouzet, M., The morphology of infinite tournaments; applications to the growth of their profile, Europ. J. Combin., 31, 461-481 (2010) · Zbl 1230.05138
[5] Culus, J.-F.; Jouve, B., Convex circuit-free coloration of an oriented graph, Europ. J. Combin., 30, 43-52 (2009) · Zbl 1213.05073
[6] Fraïssé, R., Theory of Relations, Studies in Logic and the Foundations of Mathematics, vol. 145 (2000), Elsevier · Zbl 0593.04001
[7] Gallai, T., Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar., 18, 25-66 (1967) · Zbl 0153.26002
[8] Latka, B. J., Structure theorem for tournaments omitting \(N_5\), J. Graph Theory, 42, 165-192 (2003) · Zbl 1016.05036
[9] Pouzet, M., Un bel ordre d’abritement et ses rapports avec les bornes d’une multirelation, C. R. Acad. Sci. Paris Sér. A-B, 274, A1677-A1680 (1972) · Zbl 0254.08001
[10] Schmerl, J. H.; Trotter, W. T., Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., 113, 191-205 (1993) · Zbl 0776.06002
[11] Slater, P., Inconsistencies in a schedule of paired comparaison, Biometrika, 48, 303-312 (1961)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.