Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
A bipartite graph? – dtldarek Mar 14 '12 at 23:48
A trivial fact is that such a relation is vacuously transitive. – user23211 Mar 15 '12 at 0:05
up vote 1 down vote accepted

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.

share|cite|improve this answer
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. – alex.jordan Mar 15 '12 at 0:21

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.