1
$\begingroup$

Is there a term for a binary relation $R\subset A^2$ on some set $A$ such that if $(x, y)\in R$ then there is no $z$ such that $(y, z)\in R$ ? Are there any examples of it? Are there any related concepts?

I am working on a computer program that deals with "keywords" that have "aliases", and just came up with such relation, and wanted to know some hint in thinking about it.

  • 1
    A trivial fact is that such a relation is vacuously transitive.2012-03-15

1 Answers 1

1

You could call this a digraph with longest path length of $1$.

The set $A$ gives the vertices of the graph. Having $(x,y)$ in the relation provides a directed edge $x\to y$. Your condition implies there is no directed segment $x\to y\to z$, hence all directed paths are of length 1.

  • 1
    dtldarek's comment above suggests an alternative. Decompose $A$ into $S$ ("sources") and the complement of $S$ where $S$ is the set of all $x\in A$ such that there exists some $(x,y)$ in the relation $R$. Then a bipartite graph between $S$ and $A\setminus S$ with no singletons in $S$ describes your relation.2012-03-15