What is a relation $R$ called for which $\forall x,y,z: \neg (x R y \wedge y R z)$?

Question

For a project, I am working with relations $R$ with the property:

$\neg\exists x,y,z: x R y \wedge y R z$

Does this property have a name? If so, what is it?

These sorts of relations can be described as a bipartite graph in which all edges are directed from the same half of the graph to the other: https://en.wikipedia.org/wiki/Bipartite_graph — Connor Harris, Aug 27 '18 at 14:55
Alternatively (and still in graph theory land), your relation is a (directed) matching. — Arthur, Aug 27 '18 at 14:56
(Directed) matching is the kind of answer I'm looking for, thank you. — reinierpost, Aug 27 '18 at 15:07

Daron · Accepted Answer · 2018-08-27T15:14:53.403

2

For posets this property is called having height $2$.

The height of a poset is the maximum cardinality of a totally-ordered subset.

edited Aug 27 '18 at 15:14

answered Aug 27 '18 at 14:56

Daron

I like this answer. If you just think of $R$ as $<$ rather than $\leq$ (as there is no $x$ with $xRx$), then it does seem like a partial order. – Arthur Aug 27 '18 at 15:03
Shouldn't it be: having height at most 2? – reinierpost Aug 27 '18 at 15:09
Yep! Corrected. – Daron Aug 27 '18 at 15:14

1 Answers1