\section{What the distance multiset records}\label{sec:geometry}

We first express edge distances through landmark positions on the
replacement paths. This will isolate the counts that distinguish edges
and turn equality of multisets into equations for those counts.

Throughout the article, \(n\ge3\) and \(L\ge2\) are integers. Index the
original vertices by \(0,\ldots,n-1\). Sums over original vertices and
the rows and columns of binary matrices encoding landmark selections
use these indices. For distinct
originals \(i,j\) and an integer \(0\le t\le L\), let \(x_{ij}(t)\) be
the vertex in position \(t\) on the path from \(i\) to \(j\). Thus
\(x_{ij}(0)=i\), \(x_{ij}(L)=j\), and
\(x_{ij}(t)=x_{ji}(L-t)\). We call \(ij\) the \emph{support} of each
edge on this path.

Orient an edge so that its nearer original endpoint is \(i\), and write
\[
e=x_{ij}(a)x_{ij}(a+1),\qquad
0\le a\le\lfloor(L-1)/2\rfloor,\qquad b=L-1-a.
\]
Here \(a\) and \(b\) are the distances from \(e\) to \(i\) and \(j\),
respectively, and \(a\le b\). We call \(a\) the \emph{edge depth} and
put \(\delta=b-a\); either orientation is permitted when \(a=b\).
An internal vertex \(x_{ij}(t)\) has \emph{vertex depth} \(\min(t,L-t)\).

The distances depend on how the landmark's support meets \(ij\).
On \(ij\) itself, the endpoints of \(e\) are in positions \(a\) and
\(a+1\), as shown in Fig.~\ref{fig:own-support}.
If \(t\le a\), the nearer endpoint is in position \(a\), at distance
\(a-t\); if \(t\ge a+1\), it is in position \(a+1\), at distance
\(t-(a+1)\). These two cases cover every vertex because \(t\) is an
integer. In particular, the distance is zero at either endpoint of \(e\).

\begin{figure}[!htbp]
\centering\input{figures/own_support_distance.tex}
\caption{Distance on the edge's own support. Positions are measured from
\(i\). In (a), the nearest endpoint of \(e\) is in position \(a\); in (b),
it is in position \(a+1\). Each brace measures the distance to that
endpoint. Moving the orange landmark to either endpoint gives distance
zero. The paths are schematic.}
\label{fig:own-support}
\end{figure}
\FloatBarrier

For the other supports, compare routes through their original endpoints,
using distance \(L\) between distinct originals.
Fig.~\ref{fig:distance-geometry} shows the two configurations where
both endpoint routes can matter.

\begin{figure}[!htbp]
\centering\input{figures/distance_geometry.tex}
\caption{Routes to a landmark on another support. In (a), entering
\(ju\) through \(j\) or \(u\) gives lengths \(b+t\) and
\(a+L+(L-t)\). In (b), entering the disjoint support through \(u\) or
\(v\) gives \(a+L+t\) or \(a+L+(L-t)\). Orange vertices are landmarks.
Each complete support has length \(L\); intermediate positions are schematic.}
\label{fig:distance-geometry}
\end{figure}
\FloatBarrier

Table~\ref{tab:distances} collects these distances. In its first row,
leaving the support of \(e\) cannot shorten the segment drawn in
Fig.~\ref{fig:own-support}; in the remaining rows, the
shorter endpoint route gives the stated value.

\begin{table}[H]
\centering\small
\caption{Distances from \(e\), with \(a\le b\), \(a+b=L-1\),
\(1\le t<L\), and distinct \(u,v\notin\{i,j\}\).}\label{tab:distances}
\begin{tabular}{@{}ll@{}}
\toprule
Landmark & Distance from \(e\)\\
\midrule
\(x_{ij}(t)\), on the support &
\(\begin{cases}a-t,&t\le a,\\ t-(a+1),&t\ge a+1\end{cases}\)\\[9pt]
\(x_{iu}(t)\), sharing \(i\) & \(a+t\)\\
\(x_{ju}(t)\), sharing \(j\) & \(\min\{b+t,2L+a-t\}\)\\
\(x_{uv}(t)\), on a disjoint support & \(L+a+\min(t,L-t)\)\\
Originals \(i,j,u\) & \(a,b,L+a\), respectively\\
\bottomrule
\end{tabular}
\end{table}

Fix a landmark set \(W\subseteq V(S_L(K_n))\). To record which internal
vertices are selected, define
\[
\eta_{ij}(t)=
\begin{cases}
1,&x_{ij}(t)\in W,\\
0,&x_{ij}(t)\notin W,
\end{cases}
\qquad i\ne j,\quad 1\le t<L.
\]
The two orientations describe the same vertex, so
\(\eta_{ij}(t)=\eta_{ji}(L-t)\). Summing these indicators over paths
leaving \(i\) gives the \emph{endpoint profile}
\[
D_i(t)=\sum_{j\ne i}\eta_{ij}(t),\qquad 1\le t<L.
\]
Thus \(D_i(t)\) is the number of landmarks in position \(t\) on paths
leaving \(i\); it summarizes their individual choices in one integer.

We will count landmarks at each distance from an edge.
For \(e\in E(S_L(K_n))\) and a nonnegative integer \(h\), put
\[
 H_e^W(h)=|\{s\in W:d(e,s)=h\}|,\qquad
 H_e(z)=\sum_{h\ge0}H_e^W(h)z^h.
\]
Here \(z\) is an indeterminate and \(H_e\in\mathbb Z[z]\); the fixed
set \(W\) is suppressed in \(H_e\). Equality of these histograms is
exactly equality of the distance multisets. The polynomial collects
the integer counts: its exponent is a distance and its coefficient
is a number of landmarks.

For a landmark on a support disjoint from \(ij\), only its vertex
depth matters. Use this distance as a common baseline. A landmark
on a support sharing \(i\) or \(j\) changes one count from that
baseline; the following polynomials record the change:
\begin{align}
A_t(z)&=z^{a+t}-z^{L+a+\min(t,L-t)},\notag\\
B_t(z)&=z^{\min(b+t,2L+a-t)}-z^{L+a+\min(t,L-t)},
\qquad 1\le t<L.
\label{eq:columns}
\end{align}
Although suppressed in the notation, these polynomials depend on
\(a,b,L\). We also regard each polynomial as a column vector indexed
by distance, so its coefficient at \(z^h\) is the change at distance \(h\).

Let \(T_s\) count all internal landmarks of depth \(s\), where
\(1\le s\le k=\lfloor L/2\rfloor\). For the original vertices, put
\(\alpha_i=\ind_{\{i\in W\}}\) and \(A_0=\sum_i\alpha_i\).
We use \(\ind_{\{\mathcal P\}}=1\) when the condition \(\mathcal P\)
holds and \(0\) otherwise. The next identity begins with all landmarks
at the disjoint-support baseline and corrects the two families of
paths through the endpoints of \(e\). Landmarks on \(ij\) belong to
both families, so one final correction restores their actual distances.

\Needspace{18\baselineskip}
\begin{lemma}\label{lem:histogram}
For a fixed landmark set \(W\), let \(\eta_{ij}(t)\) be its internal
selection indicators as defined above. For
\(e=x_{ij}(a)x_{ij}(a+1)\), its histogram is
\begin{align}
H_e(z)={}&\sum_{s=1}^k T_sz^{L+a+s}
+\sum_{t=1}^{L-1}\bigl(D_i(t)A_t(z)+D_j(t)B_t(z)\bigr)+E_e(z)\notag\\
&+\alpha_i z^a+\alpha_jz^b+(A_0-\alpha_i-\alpha_j)z^{L+a},
\label{eq:histogram}
\end{align}
where the correction from the support of \(e\) is
\begin{align}
E_e(z)=\sum_{t=1}^{L-1}\eta_{ij}(t)\bigl[
&z^{\min(|t-a|,|t-(a+1)|)}-z^{a+t}\notag\\
&-z^{\min(b+L-t,L+a+t)}+z^{L+a+\min(t,L-t)}\bigr].
\label{eq:local-error}
\end{align}
With \(\|\cdot\|_\infty\) denoting the largest absolute coefficient,
any two edges \(e,f\) of the same graph, using the same set \(W\), satisfy
\begin{equation}\label{eq:error-bound}
\|E_e\|_\infty\le2,\qquad \|E_e-E_f\|_\infty\le4.
\end{equation}
\end{lemma}
\begin{proof}
Initially count each internal landmark as though its support were disjoint from \(ij\). The columns \(A_t,B_t\) correct the two families of paths, using Table~\ref{tab:distances}. A landmark on \(ij\) appears in both corrections; the summand in~\eqref{eq:local-error} restores its actual distance. Original landmarks give the last line of~\eqref{eq:histogram}.

For the coefficient bound, each of the two positive exponents in~\eqref{eq:local-error} has at most two preimages as \(t\) varies. Their ranges are disjoint: the first is at most \(b\), whereas the second is at least \(L+a+1>b\). Their combined contribution to any coefficient is therefore at most two. The exponent \(a+t\) is injective and at most \(L+a-1\). The other negative exponent is
\[
L+a+\min(\delta-t,t).
\]
Its increasing branch starts at \(L+a+1\), above the first negative range, and its decreasing branch is injective. Thus the negative contribution also has magnitude at most two at every coefficient. Subtracting these contributions proves the first bound; the second follows by the triangle inequality.
\end{proof}

We will recover the edge depth before comparing its endpoint profiles. All distances in Table~\ref{tab:distances} are at most \(L+a+k\). If a depth-\(k\) landmark lies on a disjoint support, it attains this value, so
\begin{equation}\label{eq:last-layer}
\max\{t:H_e^W(t)>0\}=L+a+k.
\end{equation}
The constructions in Sections~\ref{sec:symmetric} and~\ref{sec:odd} ensure such a landmark for every support. Equation~\eqref{eq:last-layer} then determines \(a\), and hence \(b\) and \(\delta\).

\begin{proposition}\label{prop:ordered}
For \(n\ge3\) and \(L\ge2\),
\[
\left\lceil\frac{n-1}{2}\right\rceil\le \edim(S_L(K_n))\le n.
\]
\end{proposition}
\begin{proof}
The original vertices resolve every edge: the two smallest named distances identify its support endpoints, and either endpoint distance specifies its position. This proves the upper bound. For the lower bound, associate to each landmark its original vertex, or the two endpoints of its support if it is internal. Fewer than \((n-1)/2\) landmarks leave at least two originals unassociated. Interchanging these originals induces a nontrivial automorphism that fixes every landmark and moves an edge of their replacement path. Those two edges have equal named distance records, a contradiction.
\end{proof}