Skip to main content
5 of 8
added 74 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 not reflexive) 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 \mathbb{R}^d$ which assigns a $d$ dimensional real vector to each element of $X$, and a continuous function $f: \mathbb{R}^{d + d} \rightarrow \mathbb{R}$ monotonic in each of its coordinates, such that $xRy \Leftrightarrow f(g(x),g(y)) > 0$.

Taking $d = n$, it's easy to construct $f$, by having $g$ map the elements of $X$ to the canonical basis of $\mathbb{R}^d$ (a one-hot encoding).

This is not generally possible for all $d$. If $d = 1$, this is possible iff $R$ is also 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