Skip to main content
2 of 8
added 40 characters in body
Arthur B
  • 1.9k
  • 1
  • 14
  • 18

Representing a binary relation

Consider a binary relation $R$ over a finite set $X$ of size $n$. Assume $R$ is antisymmetric and connected but not necessarily transitive. In essence, we are modeling an "option x beats option y" relation, which is not necessarily transitive. It might be the result of a voting process for instance.

It is sometimes possible to find a function $g : X \rightarrow \mathbf{R}^d$ which assigns a $d$ dimensional real vector to each element of X, and a continuous function $f: \mathbb{R}^{n + n} \rightarrow \mathbb{R}$ monotonous in each of its coordinates, such that $xRy \Leftrightarrow f(g(x),g(y)) > 0$.

Taking $d = n$ and $g$ a one-hot encoding, it's easy to construct $f$.

This is not generally possible for all $d$. If $d = 1$, this is possible iff $R$ is transitive.

Let's call the smallest $d$ for which $f$ and $g$ exist the dimension of the relation, and write it $D(R)$.

Is $D$ bounded?

Arthur B
  • 1.9k
  • 1
  • 14
  • 18