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.



Representing a binary relation
Every binary relation $R$ has a representation with $d=2$. Enumerate $X=\{x\_i:i\in[n]\}$, and define $g\colon X\to\mathbb R^2$ by $g(x\_i)=(i,-i)$. Since $\{(i,-i,j,-j):i,j\in[n]\}$ is a set of pairwise incomparable elements of $\mathbb R^4$, the Proposition below implies that there exists a continuous increasing function $f\colon\mathbb R^4\to\mathbb R$ such that
$$f(i,-i,j,-j)=\begin{cases}\phantom-1&x\_i\mathrel Rx\_j,\\-1&\text{otherwise,}\end{cases}$$
whence
$$x\_i\mathrel Rx\_j\iff f(g(x\_i),g(x\_j))>0$$
as required.



> 
> **Proposition.** Let $d\in\mathbb N$ and $X\subseteq\mathbb R^d$ be finite. Then any nondecreasing (w.r.t. the coordinatewise partial order on $\mathbb R^d$) function $f\colon X\to\mathbb R$ extends to a continuous nondecreasing function $\tilde f\colon\mathbb R^d\to\mathbb R$. If $f$ is strictly increasing, $\tilde f$ can be taken strictly increasing as well.
> 
> 
> 


(More generally, the argument below can be adapted to $X\subseteq\mathbb R^d$ whose projection to each coordinate is a subset of $\mathbb R$ with no accummulation point.)


I will outline a proof in the strictly increasing case; the nondecreasing case is completely analogous.


First, we can extend $f$ to any countable set by iterating the following observation:



> 
> **Lemma.** If $X\subseteq\mathbb R^d$ is finite and $y\in\mathbb R^d$, then any increasing $f\colon X\to\mathbb R$ extends to an increasing function $g\colon X\cup\{y\}\to\mathbb R$.
> 
> 
> 


**Proof:** Assume $y\notin X$. Putting $r=\max\{f(x):x\in X,x<y\}$ and $s=\min\{f(x):x\in X,y<x\}$, it suffices to define $g(y)$ so that $r<g(y)<s$, which is possible as $r<s$. If $r$ or $s$ does not exist due to the relevant set being empty, we ignore the corresponding constraint. QED



> 
> **Corollary.** If $X\subseteq Y\subseteq\mathbb R^d$, $X$ is finite, and $Y$ is countable, then any increasing $f\colon X\to\mathbb R$ extends to an increasing function $g\colon Y\to\mathbb R$.
> 
> 
> 


**Proof:** Write $Y=\{y\_n:n\in\omega\}$. Using the Lemma, construct a sequence of $f=f\_0\subseteq f\_1\subseteq f\_2\subseteq\cdots$ of increasing functions $f\_n\colon X\cup\{y\_i:i<n\}\to\mathbb R$, and put $ g=\bigcup\_nf\_n$. QED


At this point, we could extend a given $f\colon X\to\mathbb R$ to an increasing $\bar f\colon Y\to\mathbb R$ for a countable dense set $Y$, and define $\tilde f\colon\mathbb R^d\to\mathbb R$ by $\tilde f(x)=\sup\{\bar f(y):y\le x,y\in Y\}$; this will be an increasing function, but may well be discontinuous. Thus, we need to work a bit harder.


Let $Z=\{z\_n:n\in\mathbb Z\}\subseteq\mathbb R$ be a set such that $n<m\implies z\_n<z\_m$, $\inf Z=-\infty$, $\sup Z=+\infty$, and $Z$ contains all coordinates of all elements of $X$. Using the Corollary, we can extend any increasing $f\colon X\to\mathbb R$ to an increasing $f\_0\colon Z^d\to\mathbb R$. By applying a suitable continuous increasing bijection $\mathbb R\to\mathbb R$, we may assume $Z=\mathbb Z$ without loss of generality.


We now extend the increasing function $f\_0\colon\mathbb Z^d\to\mathbb R$ to a function $f\_1\colon(\frac12\mathbb Z)^d\to\mathbb R$ as follows. Any $x\in(\frac12\mathbb Z)^d$ can be written uniquely as $x=(x\_0+x\_1)/2$, where $x\_0,x\_1\in\mathbb Z^d$, $x\_0\le x\_1$, and $\|x\_1-x\_0\|\_\infty\le1$; we define $f\_1(x)=\frac12(f\_0(x\_0)+f\_0(x\_1))$.


Let $x,y\in(\frac12\mathbb Z)^d$ be neighbouring lattice points, i.e., $x<y$ and $\|y-x\|\_1=1/2$. We have either $x\_0=y\_0$, $x\_1<y\_1$, and $\|y\_1-x\_1\|\_1=1$, or $x\_0<y\_0$, $\|y\_0-x\_0\|\_1=1$, and $x\_1=y\_1$. In the former case, $f\_1(y)-f\_1(x)=\frac12(f\_0(y\_1)-f\_0(x\_1))$, while in the latter case, $f\_1(y)-f\_1(x)=\frac12(f\_0(y\_0)-f\_0(x\_0))$. In particular, $f\_1(y)>f\_1(x)$. Since we can get from any $x$ to any $y>x$ by an increasing sequence of lattice neighbour hops, this implies that $f\_1$ is increasing.


But the argument gives more. Assume $n\in\mathbb N$ and $t>0$ are such that $f\_0$ is $t$-Lipschitz on $[-n,n]^d$ w.r.t. the $\|\cdot\|\_1$ norm:
$$x,y\in(\mathbb Z\cap[-n,n])^d\implies|f\_0(y)-f\_0(x)|\le t\|y-x\|\_1.$$
Then we obtain $|f\_1(y)-f\_1(x)|\le t/2$ when $y,x\in[-n,n]^d$ are neighbours in the $(\frac12\mathbb Z)^d$ lattice, which implies that $f\_1$ is $t$-Lipschitz on $[-n,n]^d$ w.r.t. $\|\cdot\|\_1$ as well.


Thus, if we iterate this process to construct a sequence $f\_0\subseteq f\_1\subseteq f\_2\subseteq\cdots$ of increasing functions $f\_i\colon(2^{-i}\mathbb Z)^d\to\mathbb R$, they will have the property that for any $n\in\mathbb N$ and $t>0$, if $f\_0$ is $t$-Lipschitz on $[-n,n]^d$, then all $f\_i$ are $t$-Lipschitz on $[-n,n]^d$.


Let $\bar f=\bigcup\_if\_i$. Then $\bar f$ is an increasing function $\mathbb D^d\to\mathbb R$, where $\mathbb D=\bigcup\_i2^{-i}\mathbb Z$ is the set of dyadic rationals, and for every $n\in\mathbb N$, there exists $t>0$ such that $\bar f$ is $t$-Lipschitz, hence uniformly continuous, on $[-n,n]^d$. It follows that $\bar f$ has a unique continuous extension $\tilde f\colon\mathbb R^d\to\mathbb R$, and this has to be increasing as well.


EDIT: A more explicit description of the extension of $f\_0\colon\mathbb Z^d\to\mathbb R$ to $\tilde f\colon\mathbb R^d\to\mathbb R$ above can be given as follows. We consider a triangulation of $\mathbb R^d$ whose faces are the simplices $\operatorname{Conv}\{x\_0,\dots,x\_k\}$ where $x\_0,\dots,x\_k\in\mathbb Z^d$ are such that $x\_0<x\_1<\dots<x\_k$ and $\|x\_k-x\_0\|\_\infty\le1$. (One needs to check that this is indeed a triangulation.) We then define $\tilde f$ such that its restriction to each simplex in the triangulation is the unique affine function that agrees with $f\_0$ at the vertices of the simplex. This is a continuous extension of $f\_0$, and one can check easily that it is increasing.


