Relation asymétrique

En mathématiques, une relation (binaire, interne) R est dite asymétrique 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.

Démonstration

Aucun 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).

• 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 suite A001035 de l'OEIS.
• Les relations d'ordre strict total sont en nombre $n!$.