[Subtournaments isomorphic to in an indecomposable tournament]
We consider a tournament . For each subset X of V is associated the subtournament of T induced by X. We say that a tournament embeds into a tournament T when is isomorphic to a subtournament of T. A subset X of V is an interval of T provided that for and , if and only if . For example, ∅, and V are intervals of T, called trivial intervals. A tournament is indecomposable if all its intervals are trivial. In 2003, B.J. Latka characterized the class of the indecomposable tournaments into which a certain tournament on 5 vertices does not embed. In the case of an indecomposable tournament T, we study the set of vertices for which there exists a subset X of V such that and is isomorphic to . We prove the following: for any indecomposable tournament T, if , then and if is even. By giving examples, we also verify that this statement is optimal.
Considérons un tournoi . À chaque partie X de S est associé le sous-tournoi de T induit par X. On dit que le tournoi T abrite un tournoi lorsque est isomorphe à un sous-tournoi de T. Une partie X de S est un intervalle de T lorsque pour tous et , si et seulement si . Par exemple, ∅, et S sont des intervalles de T, appelés intervalles triviaux. Un tournoi, dont tous les intervalles sont triviaux, est indécomposable. En 2003, B.J. Latka a caractérisé la classe des tournois indécomposables nʼabritant pas un certain tournoi à 5 sommets. Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable T, à lʼensemble des sommets pour lesquels il existe une partie X de S telle que et est isomorphe à . Nous montrons que pour un tournoi indécomposable T nʼappartenant pas à la classe , , et que lorsque est pair. À lʼaide dʼexemples, nous vérifions aussi que cet énoncé est optimal.
Accepted:
Published online:
Houmem Belkhechine 1; Imed Boudabbous 2; Kaouthar Hzami 3
@article{CRMATH_2012__350_7-8_333_0, author = {Houmem Belkhechine and Imed Boudabbous and Kaouthar Hzami}, title = {Sous-tournois isomorphes \`a $ {W}_{5}$ dans un tournoi ind\'ecomposable}, journal = {Comptes Rendus. Math\'ematique}, pages = {333--337}, publisher = {Elsevier}, volume = {350}, number = {7-8}, year = {2012}, doi = {10.1016/j.crma.2012.03.012}, language = {fr}, }
TY - JOUR AU - Houmem Belkhechine AU - Imed Boudabbous AU - Kaouthar Hzami TI - Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable JO - Comptes Rendus. Mathématique PY - 2012 SP - 333 EP - 337 VL - 350 IS - 7-8 PB - Elsevier DO - 10.1016/j.crma.2012.03.012 LA - fr ID - CRMATH_2012__350_7-8_333_0 ER -
Houmem Belkhechine; Imed Boudabbous; Kaouthar Hzami. Sous-tournois isomorphes à $ {W}_{5}$ dans un tournoi indécomposable. Comptes Rendus. Mathématique, Volume 350 (2012) no. 7-8, pp. 333-337. doi : 10.1016/j.crma.2012.03.012. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2012.03.012/
[1] Tournois indécomposables et leurs sous-tournois indécomposables à 5 sommets, C. R. Acad. Sci. Paris, Ser. I, Volume 343 (2006), pp. 685-688
[2] On an adjacency property of almost all tournaments, Discrete Math., Volume 306 (2006), pp. 2327-2335
[3] Minimal indecomposable graphs, Discrete Math., Volume 183 (1998), pp. 61-80
[4] Finite Model Theory, Springer Monographs in Mathematics, 1999
[5] Primitivity is hereditary for 2-structures, Theoret. Comput. Sci., Volume 3 (1990) no. 70, pp. 343-358
[6] Some remarks on simple tournaments, Algebra Universalis, Volume 2 (1972), pp. 238-245
[7] Probabilities on finite models, J. Symbolic Logic, Volume 41 (1976), pp. 50-58
[8] Finite-model theory – a personal perspective, Theoret. Comput. Sci., Volume 116 (1993), pp. 3-31
[9] Lʼintervalle en théorie des relations, ses généralisations, filtre intervallaire et clôture dʼune relation (M. Pouzet; D. Richard, eds.), Orders, Description and Roles, North-Holland, Amsterdam, 1984, pp. 313-342
[10] La reconstruction des tournois sans diamants, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 283-291
[11] Indecomposable graphs, Discrete Math., Volume 173 (1997), pp. 71-78
[12] Structure theorem for tournaments omitting , J. Graph Theory, Volume 42 (2003), pp. 165-192
[13] Reconstruction of binary relations from their restrictions of cardinality 2, 3, 4 and , I, Z. Math. Logik Grundlag. Math., Volume 38 (1992), pp. 27-37
[14] Either tournaments or algebras ?, Discrete Math., Volume 11 (1975), pp. 37-66
[15] Partially critical tournaments and partially critical supports, Contrib. Discrete Math., Volume 6 (2011), pp. 52-76
[16] Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math., Volume 113 (1993), pp. 191-205
Cited by Sources:
Comments - Policy