Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Sous-tournois isomorphes à W 5
View through CrossRef
Considérons un tournoi
T
=
(
S
,
A
)
. À chaque partie
X
de
S
est associé le sous-tournoi
T
(
X
)
=
(
X
,
A
∩
(
X
×
X
)
)
de
T
induit par
X
. On dit que le tournoi
T
abrite un tournoi
T
′
lorsque
T
′
est isomorphe à un sous-tournoi de
T
. Une partie
X
de
S
est un intervalle de
T
lorsque pour tous
a
,
b
∈
X
et
x
∈
S
∖
X
,
(
a
,
x
)
∈
A
si et seulement si
(
b
,
x
)
∈
A
. Par exemple, ∅,
{
x
}
(
x
∈
S
)
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
T
des tournois indécomposables nʼabritant pas un certain tournoi
W
5
à 5 sommets. Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable
T
, à lʼensemble
W
5
(
T
)
des sommets
x
∈
S
pour lesquels il existe une partie
X
de
S
telle que
x
∈
X
et
T
(
X
)
est isomorphe à
W
5
. Nous montrons que pour un tournoi indécomposable
T
nʼappartenant pas à la classe
T
,
|
W
5
(
T
)
|
⩾
|
S
|
−
2
, et que
|
W
5
(
T
)
|
⩾
|
S
|
−
1
lorsque
|
S
|
est pair. À lʼaide dʼexemples, nous vérifions aussi que cet énoncé est optimal.
MathDoc/Centre Mersenne
Title: Sous-tournois isomorphes à
W
5
Description:
Considérons un tournoi
T
=
(
S
,
A
)
.
À chaque partie
X
de
S
est associé le sous-tournoi
T
(
X
)
=
(
X
,
A
∩
(
X
×
X
)
)
de
T
induit par
X
.
On dit que le tournoi
T
abrite un tournoi
T
′
lorsque
T
′
est isomorphe à un sous-tournoi de
T
.
Une partie
X
de
S
est un intervalle de
T
lorsque pour tous
a
,
b
∈
X
et
x
∈
S
∖
X
,
(
a
,
x
)
∈
A
si et seulement si
(
b
,
x
)
∈
A
.
Par exemple, ∅,
{
x
}
(
x
∈
S
)
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
T
des tournois indécomposables nʼabritant pas un certain tournoi
W
5
à 5 sommets.
Dans cet article, nous nous intéressons, dans le cas dʼun tournoi indécomposable
T
, à lʼensemble
W
5
(
T
)
des sommets
x
∈
S
pour lesquels il existe une partie
X
de
S
telle que
x
∈
X
et
T
(
X
)
est isomorphe à
W
5
.
Nous montrons que pour un tournoi indécomposable
T
nʼappartenant pas à la classe
T
,
|
W
5
(
T
)
|
⩾
|
S
|
−
2
, et que
|
W
5
(
T
)
|
⩾
|
S
|
−
1
lorsque
|
S
|
est pair.
À lʼaide dʼexemples, nous vérifions aussi que cet énoncé est optimal.
Related Results
Indécomposabilité des graphes et des tournois
Indécomposabilité des graphes et des tournois
Cette thèse porte sur l’indécomposabilité dans les graphes et les tournois. Elle comporte cinq chapitres dont le premier est introductif. Le deuxième chapitre consiste en une étude...
Morphologie des tournois (−1)-critiques
Morphologie des tournois (−1)-critiques
Étant donné un tournoi
T
=
(
S
,
...
Inversion dans les tournois
Inversion dans les tournois
Nous considérons la transformation qui inverse tous les arcs d'une partie
X
de l'ensemble des sommets d'un tournoi
T
...
Algorithmic and structural results on directed cycles in dense digraphs
Algorithmic and structural results on directed cycles in dense digraphs
Résultats algorithmiques et structurels sur les cycles orientés dans les digraphes denses
Dans cette thèse, nous nous intéressons à quelques problèmes algorithmique...
Sοficity οf multidimensiοnal subshifts
Sοficity οf multidimensiοnal subshifts
Soficité des espaces de pavages multidimensionnels
En dynamique symbolique, un sous-shift multidimensionnel est un language formel de coloriages infinis de l'espace...
Groupoïdes sous inductifs
Groupoïdes sous inductifs
Cet article est consacré à l’étude des groupoïdes munis de structures d’ordre, d’une façon précise des groupoïdes sous-préinductifs et sous-inductifs. Un rôle important est joué pa...
Subshifts of Finite Type on Groups : Emptiness and Aperiodicity
Subshifts of Finite Type on Groups : Emptiness and Aperiodicity
Sous-décalages de type fini sur des groupes : problèmes du vide et d'apériodicité
Un sous-décalage de type fini est un ensemble de pavages d'un groupe sujet à un no...