Relation asymétrique

Modèle:Homon En mathématiques, une relation (binaire, interne) Modèle:Math est dite asymétriqueModèle:,Modèle:,Modèle:,Modèle:,Modèle:, si elle vérifie :

$xRy\Rightarrow (y\cancel{R}x),$

ou encore, si son graphe est disjoint de celui de sa relation réciproque.

L'asymétrie est parfois appelée « antisymétrie forte », par opposition à l'antisymétrie (usuelle, ou « faible »). En effet, une relation est asymétrique si et seulement si elle est à la fois antisymétrique et antiréflexive.

Exemples

• les relations d'ordre strict, qui sont les relations transitives et asymétriques ;
• dans les entiers, la relation "est le successeur de" ;
• dans un ensemble de personnes, la relation « est enfant de »  : personne n'est enfant d'un de ses enfants.

Une relation ne peut pas être à la fois symétrique et asymétrique, sauf si son graphe est vide.

Dénombrements

• Dans un ensemble à n éléments, il existe $3^{\frac{n(n-1)}{2}}$ relations asymétriques.

Modèle:Démonstration/débutAucun des n couples $(x,x)$ n'appartient au graphe.

Pour les $\frac{n(n-1)}{2}$ paires $\{x,y\}$, il y a trois possibilités : soit seul $(x,y)$ appartient au graphe, soit seul $(y,x)$, soit aucun des deux (ils ne peuvent y appartenir tous les deux). Modèle:Démonstration/fin

• Les relations d'ordre strict, qui sont en bijection avec les relations d'ordre, ne possèdent pas de formule de dénombrement "fermée" ; voir la Modèle:OEIS.
• Les relations d'ordre strict total sont en nombre $n!$.