Dimension of vertex labeling of \(k\)-uniform dcsl path (Q2792876)

Let \(G\) be a graph with vertex set \(V(G)\) and let \(X\) be a nonempty set. Let \(f:V(G)\rightarrow 2^X\) be injective. The function \(f^\oplus:V(G)^2\rightarrow 2^X\setminus \{\emptyset\}\) is defined as \(f^\oplus(u,v)=f(u)\oplus f(v)\), where \(A \oplus B=(A\setminus B)\cup (B\setminus A)\) denotes the symmetric difference of \(A\) and \(B\). \(G\) is called \(k\)-uniform dcsl graph if there is a \(k\)-uniform dcsl \(f\), i.e., a function \(f\) such that \(|f^\oplus(u,v)|=k\times d_G(u,v)\), where \(d_G(u,v)\) is the length of a shortest \(u-v\) path in \(G\). The \(k\)-uniform dcsl index \(\delta_k(G)\) is the minimum value of \(|X|\) such that \(X\) induces a \(k\)-uniform dcsl. For any partial order \(P\), a realizer of \(P\) is set of linear orders \(L_1,L_2,\dots, L_q\) such that \(P\subseteq L_i\) for \(=1,\dots,q\) and for each \(\{x,y\}\) such that neither \(xPy\) nor \(yPx\), there exist \(i\neq j\), \(1\leq i,j\leq q\), such that \(xL_i y\) and \(yL_j x\). The minimum size of a realizer of \(P\) is called the dimension of \(P\) and denoted with \(\mathrm{dim}(P)\). The authors prove that \(\mathrm{dim}(F)\leq \delta_k(P_n)\), where \(P_n\) is the path on \(n>2\) vertices and \(F\) is the range of a \(k\)-uniform dcsl of \(P_n\).