×

Some remarks on simple tournaments. (English) Zbl 0267.05104

A tournament consists of a set \(T\) of points on which is defined a complete, anti-symmetric, irreflexive binary relation \(\rho\). A non-empty proper subset \(X\) of \(T\) is convex if for each \(y \in T-X\) either \(x \rho y\) for all \(x \in X\) or \(y \rho x\) for all \(x \in X\). A tournament is simple if it has no convex subsets with more than one point. The authors prove that almost all finite tournaments are simple and that for any tournament \(T\) with \(|T| \neq 2\) there exists a simple tournament \(R\) such that \(T \subset R\) and \(|R-T| =2\). (Criteria for a tournament to have a simple one-point extension have been given by the reviewer [Discrete Math. 2, 389-395 (1972; Zbl 0236.05108)] when \(T\) is finite and by P. Erdős, A. Hajnal and E. C. Milner [Mathematika, London 19, 57-62 (1972; Zbl 0242.05113)] in the general case.)
Reviewer: J.W.Moon

MSC:

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

References:

[1] E. Fried,Tournaments and non-associative lattices, Ann. Univ. Sci. Budapest, Eötvös Sect. Math., (to appear). · Zbl 0224.06004
[2] E. Fried and H. Lakser,Simple Tournaments, manuscript.
[3] Miller, E. W., On a property of families of sets, Comptes Rendus Vasovie, 30, 31-38 (1937) · Zbl 0017.30003
[4] Erdös, P.; Hajnal, A., On a property of families of sets, Acta Math. Acad. Sci. Hung., 12, 87-123 (1961) · Zbl 0201.32801
[5] Erdös, P., On a combinatorial problem II, Acta. Math. Acta. Sci. Hung., 15, 445-447 (1964) · Zbl 0201.33704
[6] P. Erdös, A. Hajnal and E. C. Milner,Simple one-point extensions of tournaments, Mathematika (to appear). · Zbl 0242.05113
[7] Hausdorff, F., Grundzüge einer Theorie der geordneten Mengen, Math. Ann., 65, 435-505 (1908) · JFM 39.0099.01
[8] J. W. Moon,Embedding tournaments in simple tournaments, Discrete Mathematics (to appear). · Zbl 0289.05116
[9] J. Tos,Quelques remarques, théorèmes, et problèmes sur les classes définissables d’algèbres, Mathematical Interpretation of Formal Systems. North-Holland, Amsterdam, 98-113. · Zbl 0068.24401
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.