Return to Question

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 \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?

My guess is no. If you consider sets of non-transitive die, it seems intuitive that you cannot, in general, sum up the relationship between them with $d$ much lower than their number of faces.

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 \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$.

Intuitively, can we explain the relation in terms of the interplay of $d$ latent qualities for each element?

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?

My guess is no. If you consider sets of non-transitive die, it seems intuitive that you cannot, in general, sum up the relationship between them with $d$ much lower than their number of faces.

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?

My guess is no. If you consider sets of non-transitive die, it seems intuitive that you cannot, in general, sum up the relationship between them with $d$ much lower than their number of faces.

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 \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?

My guess is no. If you consider sets of non-transitive die, it seems intuitive that you cannot, in general, sum up the relationship between them with $d$ much lower than their number of faces.

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?

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?

My guess is no. If you consider sets of non-transitive die, it seems intuitive that you cannot, in general, sum up the relationship between them with $d$ much lower than their number of faces.