\section{Additional quantitative bounds}\label{app:refinements}

We refine the finite lower bounds and extend the known existence
ranges for long replacement paths. Central-edge histograms give
stronger counts, while independent selections, controlled through
distance-level forests, give further existence estimates and allow
the selection probability to vary.

\subsection{Finite central-edge bounds}
\label{subsec:central-lower}

Counting only the central edges gives another finite estimate and, at some odd
lengths, a larger leading constant. Its symmetric specialization also
quantifies the cost of equal profiles at opposite positions.

\begin{proposition}\label{prop:central-lower}
Let \(n\ge3\), let \(k,s\) be integers with \(k\ge1\) and
\(1\le s\le k\), and put \(L=2k+1\).
Suppose a landmark set distinguishes the central edges and has no
internal landmark of depth greater than \(s\). Its number \(B\) of
internal landmarks satisfies
\[
 B\ge
 \left\lceil\frac{F_{3^{s+1},\,2s}\bigl(\binom n2\bigr)}
                         {2(n-2)}\right\rceil.
\]
If its endpoint profiles are symmetric,
\(D_i(t)=D_i(L-t)\), then also
\[
 B\ge
 \left\lceil\frac{F_{3^{s+1},\,s}\bigl(\binom n2\bigr)}
                         {n-2}\right\rceil.
\]
In particular the respective asymptotic orders are
\(\Omega_s(n^{1+1/s})\) and \(\Omega_s(n^{1+2/s})\).
The first bound has leading constant
\[
 c_s=\frac{2s}{2s+1}
     \left(\frac{(2s)!}{3^{s+1}}\right)^{1/(2s)}
     2^{-2-1/(2s)}.
\]
\end{proposition}
\begin{proof}
For a support \(ij\), put
\[
 \begin{aligned}
 \gamma_{ij,t}&=\eta_{ij}(t)+\eta_{ij}(L-t) &&(1\le t\le s),\\
 X_{ij,t}&=D_i(t)+D_j(t)-\eta_{ij}(t)-\eta_{ij}(L-t) &&(1\le t<L).
 \end{aligned}
\]
Each \(X_{ij,t}\) counts selected vertices on paths sharing an endpoint, other
than \(ij\), and is therefore nonnegative.
Only the positions
\[
 J_s=\{1,\ldots,s,L-s,\ldots,L-1\}
\]
can have a nonzero \(X\)-coordinate.
Let \(A_0=\sum_i\alpha_i\), and let \(T_t\) be the total number of selected
internal vertices of depth \(t\).
Write \(H_{ij}=H_{e_{ij}}^W\) for the histogram of the unique central
edge \(e_{ij}\) on \(ij\). Its nonzero ranges are
\begin{equation}\label{eq:central}
 \begin{aligned}
 H_{ij}(k-t)&=\gamma_{ij,t} &&(1\le t\le s),\\
 H_{ij}(k)&=\alpha_i+\alpha_j,\\
 H_{ij}(k+t)&=X_{ij,t} &&(t\in J_s),\\
 H_{ij}(L+k)&=A_0-\alpha_i-\alpha_j,\\
 H_{ij}(L+k+t)&=T_t-\gamma_{ij,t}-X_{ij,t}-X_{ij,L-t}
                                                   &&(1\le t\le s).
 \end{aligned}
\end{equation}
All other entries are zero. These ranges are disjoint.
For the fixed landmark set, the central histogram is thus equivalent to
the tuple consisting of the \(s+1\) tags
\(\gamma_{ij,1},\ldots,\gamma_{ij,s},\alpha_i+\alpha_j\),
each in \(\{0,1,2\}\), and the \(2s\) coordinates
\((X_{ij,t})_{t\in J_s}\). The \(\binom n2\) such tagged vectors
must be distinct.

Every selected internal vertex on support \(u v\) contributes once
for each support containing \(u\) but not \(v\), and once for each
support containing \(v\) but not \(u\). Hence
\[
 \sum_{i<j}\sum_{t\in J_s}X_{ij,t}=2(n-2)B.
\]
Apply Lemma~\ref{lem:cost} with \(Q=3^{s+1}\),
\(d=2s\), and \(N=\binom n2\), then divide by \(2(n-2)\).
Integrality gives the first finite bound, and the asymptotic formula
gives the stated constant.

Under symmetry, \(X_{ij,t}=X_{ij,L-t}\).
The first \(s\) coordinates therefore determine the tuple, and their
total sum is \((n-2)B\). The same argument with \(d=s\)
gives the second bound.
\end{proof}

The unrestricted central bound is the specialization \(s=k\).
For example, at \(L=5\), its leading constant is
\(c_2=2/(5\sqrt6)\), whereas the star bound gives \(a_2=1/6\).
At \(L=7\),
\[
 a_3=\frac34(3/64)^{1/3}\approx0.270421794,\qquad
 c_3=\frac67(80/9)^{1/6}2^{-13/6}\approx0.274765879.
\]
Thus retaining both finite bounds preserves information beyond the
common growth exponent.


\subsection{A refined lower bound at length three}\label{app:refined-three}

The count in Proposition~\ref{prop:central-lower} treats the local
landmark choices as a fixed number of tags. We obtain a stronger bound
by retaining the number of supports of each local type. The counting
ingredient is again the lattice-point count for a simplex~\cite{beck}.

For an integer \(t\ge0\), write \(F(t)=F_{3,2}(t)\), the minimum total cost of
\(t\) distinct elements of
\(\{0,1,2\}\times\mathbb Z_{\ge0}^2\), where the cost of
\((a,u,v)\) is \(u+v\). Thus \(F(0)=0\). If \(t>0\) and \(\ell\)
is the least nonnegative integer with \(3\binom{\ell+2}{2}\ge t\), then
\begin{equation}\label{eq:refined-three-cost}
 F(t)=\ell t-\frac{\ell(\ell+1)(\ell+2)}2,
 \qquad
 F(t)=\frac23\sqrt{\frac23}\,t^{3/2}+O(t).
\end{equation}
Indeed, there are \(3(j+1)\) points of cost \(j\). Filling the levels
below \(\ell\) and then the required part of level \(\ell\) gives the
exact formula. The relations
\(t=3\ell^2/2+O(\ell)\) and
\(F(t)=\ell^3+O(\ell^2)\) give its asymptotic form.

Put \(M=\binom n2\). For integers \(0\le b\le2M\), define
\begin{equation}\label{eq:refined-three-j}
 J_M(b)=
 \min_{\substack{x\in\mathbb Z\\
 \max(0,b-M)\le x\le\lfloor b/2\rfloor}}
 \bigl(F(M-b+x)+F(b-2x)+F(x)\bigr).
\end{equation}
The interval in this definition is nonempty.

\begin{proposition}\label{prop:refined-three}
Let \(n\ge3\), and suppose that a set of landmarks distinguishes the
central edges of \(S_3(K_n)\). If \(B\) is the number of its internal
landmarks, then
\begin{equation}\label{eq:refined-three-finite}
 2(n-2)B\ge J_M(B).
\end{equation}
In particular, with
\[
 h(n)=\min\{b\in\{0,\ldots,M\}:2(n-2)b\ge J_M(b)\},
\]
one has
\begin{equation}\label{eq:refined-three-bilateral}
 h(n)\le B\le n(n-1)-h(n).
\end{equation}
Moreover,
\begin{equation}\label{eq:refined-three-asymptotic}
 B\ge c_*n^2-O(n),
 \qquad c_*=0.080208390067\ldots,
\end{equation}
where \(c_*\) is the unique solution in \((0,1/10)\) of
\begin{equation}\label{eq:refined-three-root}
 2c_* = \frac23\sqrt{\frac23}
 \bigl((1/2-c_*)^{3/2}+c_*^{3/2}\bigr).
\end{equation}
\end{proposition}
\begin{proof}
Write each replacement path as
\(v_i-x_{ij}-x_{ji}-v_j\), and let \(\alpha_i\) and \(\eta_{ij}\)
indicate the selection of \(v_i\) and \(x_{ij}\), respectively.
Here \(x_{ij}=x_{ij}(1)\) and \(\eta_{ij}=\eta_{ij}(1)\).
Put
\[
 d_i^+=\sum_{j\ne i}\eta_{ij},\qquad
 d_i^-=\sum_{j\ne i}\eta_{ji},\qquad
 A_0=\sum_i\alpha_i,\qquad B=\sum_i d_i^+.
\]
For a support \(\{i,j\}\), define
\[
 s_{ij}=\eta_{ij}+\eta_{ji},\quad
 u_{ij}=d_i^++d_j^+-s_{ij},\quad
 v_{ij}=d_i^-+d_j^--s_{ij}.
\]
Both \(u_{ij}\) and \(v_{ij}\) are nonnegative. Its central-edge
histogram, ordered by distances zero to five, is
\[
 \bigl(s_{ij},\ \alpha_i+\alpha_j,\ u_{ij},\ v_{ij},\
 A_0-\alpha_i-\alpha_j,\ B-u_{ij}-v_{ij}-s_{ij}\bigr).
\]
Consequently, within a fixed class \(s_{ij}=s\), the triples
\((\alpha_i+\alpha_j,u_{ij},v_{ij})\) are distinct.

Let \(M_s\) be the number of supports in this class. Then
\[
 M_0+M_1+M_2=M,\qquad M_1+2M_2=B,
\]
and
\[
 \sum_{i<j}(u_{ij}+v_{ij})=2(n-2)B.
\]
For the last identity, the sums of the outdegrees and indegrees over all
pairs each contribute \((n-1)B\), while the two copies of
\(\sum_{i<j}s_{ij}\) subtract \(2B\).
Applying the definition of \(F\) in each of the three classes gives
\begin{equation}\label{eq:refined-three-classes}
 2(n-2)B\ge F(M_0)+F(M_1)+F(M_2).
\end{equation}
Taking \(x=M_2\) proves~\eqref{eq:refined-three-finite}.

The minimum defining \(h(n)\) exists. At \(b=M\), the choice \(x=0\)
gives \(J_M(M)\le F(M)\le(n-2)M\): the levels up to \(n-2\) contain
\(3\binom n2=3M\) points, each of cost at most \(n-2\).
Equation~\eqref{eq:refined-three-finite} therefore gives \(B\ge h(n)\)
when \(B\le M\), and the same conclusion is immediate when \(B>M\).
For the full vertex set, every central edge has histogram
\[
 \bigl(2,2,2n-4,2n-4,n-2,(n-2)(n-3)\bigr).
\]
Subtracting the chosen histogram from this common vector shows that the
complement also distinguishes all central edges. It has \(2M-B\)
internal landmarks. Applying the lower bound to that complement proves
\eqref{eq:refined-three-bilateral}. This complementation argument concerns
the central edges.

It remains to derive the constant. Write
\(C=(2/3)\sqrt{2/3}\). If \(B\ge n^2/10\), the desired asymptotic
bound follows from \(c_*<1/10\). Otherwise put
\(c=B/n^2\) and \(d=M_2/n^2\). The error term in
\eqref{eq:refined-three-cost} is uniform for arguments between zero and
\(M\). Divide~\eqref{eq:refined-three-classes} by \(n^3\) and use
\(M/n^2=1/2+O(1/n)\) to obtain
\[
 2c\ge C\min_{0\le d\le c/2}
 \bigl((1/2-c+d)^{3/2}+(c-2d)^{3/2}+d^{3/2}\bigr)-O(1/n).
\]
The function being minimized is convex. Its right derivative at zero is
\[
 \frac32\bigl(\sqrt{1/2-c}-2\sqrt c\bigr)\ge0
 \qquad(0\le c\le1/10).
\]
The minimum is therefore attained at \(d=0\).
Define
\[
 g(c)=2c-C\bigl((1/2-c)^{3/2}+c^{3/2}\bigr).
\]
On \([0,1/10]\), one has
\[
 g(0)<0,\qquad
 g(1/10)=\frac{5-\sqrt{15}}{25}>0,\qquad
 g'(c)=2+\frac{3C}{2}\bigl(\sqrt{1/2-c}-\sqrt c\bigr)>2.
\]
These facts prove the existence and uniqueness of \(c_*\).
The inequality \(g(c)\ge-O(1/n)\), together with the derivative bound,
gives \(c\ge c_*-O(1/n)\), proving
\eqref{eq:refined-three-asymptotic}.
\end{proof}

Every edge multiset resolving set distinguishes the central edges.
Proposition~\ref{prop:refined-three} thus improves the asymptotic lower
constant at length three. The simpler bound \(n^2/16-n/2\) remains an
explicit finite consequence of the terminal-edge count.

\subsection{A probabilistic bound for long replacement paths}
\label{app:long-path-probability}

The forest estimate of Allikvere~\cite[Lemma~11]{allikvere} converts
independent landmark choices into a bound on histogram collisions. We
recall the estimate and specialize its distance-level graph to complete
subdivisions. This gives an existence range at smaller orders than the
four-position construction. For every nonnegative integer \(j\), write
\[
 \beta(j)=2^{-j}\binom{j}{\lfloor j/2\rfloor}.
\]
\begin{lemma}[Forest estimate]\label{lem:distance-forest}
Select every vertex of a finite connected graph independently with
probability \(1/2\), and let \(W\) be the selected set. Fix two distinct
edges \(e,f\). Suppose that a forest \(F\) has vertices among the
nonnegative distance levels and that, for each edge
\(\{\lambda,\mu\}\in E(F)\), a group of \(m_{\lambda\mu}\) graph vertices
has \(\{d(e,x),d(f,x)\}=\{\lambda,\mu\}\).
Here \(m_{\lambda\mu}\) is a nonnegative integer and \(\lambda\ne\mu\).
Then
\[
 \Pr(H_e=H_f)\le\prod_{\{\lambda,\mu\}\in E(F)}\beta(m_{\lambda\mu}).
\]
\end{lemma}
\begin{proof}
The groups are disjoint because their unordered distance pairs differ.
Condition on all landmark choices outside them. Choose an orientation
of each forest edge. The contribution of its group to \(H_e-H_f\)
is its oriented incidence column multiplied by a signed sum of
independent Bernoulli variables. Replacing each negatively signed
variable \(X\) by \(1-X\) expresses this sum as a translate of
\(\operatorname{Bin}(m_{\lambda\mu},1/2)\). The greatest probability of any single value is
\(\beta(m_{\lambda\mu})\).

The incidence columns of a forest are independent. Equivalently,
successive elimination of leaves shows that fixing the net flow at
each vertex determines every edge flow. Thus \(H_e-H_f=0\) allows
at most one value for each group sum. Conditional independence gives
the product bound, which also holds after removing the conditioning.
This is the forest argument of~\cite[Lemma~11]{allikvere}.
\end{proof}

\begin{proposition}\label{prop:long-path-probability}
For all integers \(n\ge9\) and \(L\ge12\),
\[
 \operatorname{edim}_{\mathrm m}(S_L(K_n))
 \le\left\lfloor\frac{n+(L-1)\binom n2}{2}\right\rfloor.
\]
\end{proposition}
\begin{proof}
Put \(r=\lfloor L/2\rfloor\) and
\(N=n+(L-1)\binom n2\). Select each of the \(N\) vertices
independently with probability \(1/2\), and call the selected set \(W\).

\emph{Distance forests.}
For an edge \(e\), let \(q_e\) be its distance from its nearer original
endpoint. Its distances from its two supporting originals are
\(q_e,L-1-q_e\); every other original is at distance \(L+q_e\).
Fix \(e\ne f\), let \(I\) be the union of the originals supporting
them, and interchange \(e,f\) if necessary so that \(q_e\le q_f\).

First suppose some nearer original \(u\) of \(e\) satisfies
\(d(f,u)>q_e\). For every \(k\notin I\), the internal vertices on
the path \(uk\), measured from \(u\), satisfy
\begin{align*}
 d(e,x_{uk}(t))&=q_e+t,\\
 d(f,x_{uk}(t))&=\min\{d(f,u)+t,2L+q_f-t\}>q_e+t,
 \qquad 1\le t<L.
\end{align*}
The last inequality follows from \(d(f,u)>q_e\), \(q_f\ge q_e\),
and \(t<L\). The corresponding \(L-1\) unordered pairs of distance
levels form a forest. Their smaller endpoints are distinct, so the
smallest vertex of a hypothetical cycle would have to be the smaller
endpoint of two different edges. For each forest edge, the group has
\(n-|I|\) vertices. Lemma~\ref{lem:distance-forest} bounds this
pair's collision probability by \(\beta(n-|I|)^{L-1}\).

If this case fails, every nearer original of \(e\) is also a nearer
original of \(f\), and \(q_e=q_f\). Two distinct edges with the same
support cannot have this property. Nor can a central edge of an odd
path: its two nearer originals would force the supports, and then the
central edges, to coincide. The remaining pairs have supports with a common endpoint
\(01,02\), and both edges are at the same depth
\(q\in\{0,\ldots,r-1\}\) from the common original zero.

For such a pair and \(k\notin\{0,1,2\}\), the distances on path
\(1k\) are
\[
 \min\{L-1-q+t,2L+q-t\},\qquad
 \min\{L+q+t,2L+q-t\}.
\]
They differ exactly when \(1\le t\le r+q\). Their smaller levels
\(L-1-q+t\) are distinct, so these \(r+q\) pairs also form a forest.
The paths \(2k\) give the same pairs with the opposite orientations.
Each group therefore contains \(2(n-3)\) vertices. Its collision
probability is at most \(\beta(2(n-3))^{r+q}\).
Fig.~\ref{fig:distance-forest} displays this forest for one length and depth.
\begin{figure}[htbp]
\centering\input{figures/distance_forest.tex}
\caption{A shared-endpoint comparison for \(L=12\) and \(q=1\). In (a), the edges \(e\) and \(f\) have the same distance \(q\) from the original vertex \(0\). The vertices at position \(t=4\) on the supports \(1k\) and \(2k\) have ordered distance pairs \((14,17)\) and \((17,14)\). In (b), each position \(t=1,\ldots,7\) gives an arrow from the smaller level \(\ell_t\) to the larger level \(h_t\); the highlighted arrow corresponds to (a). These seven pairs form a forest. For each pair, varying \(k\) outside \(\{0,1,2\}\) supplies \(2(n-3)\) vertices. The drawn supports in (a) are schematic paths of length \(12\).}\label{fig:distance-forest}
\end{figure}
\FloatBarrier

\emph{Summing the collision probabilities.}
We use the elementary bound
\begin{equation}\label{eq:forest-binomial}
 \beta(j)\le\bigl(3\lceil j/2\rceil+1\bigr)^{-1/2}.
\end{equation}
For even indices, induction starts with \(\beta(0)=1\), uses
\(\beta(2k+2)=\beta(2k)(2k+1)/(2k+2)\), and observes that
\[
 (2k+2)^2(3k+1)-(2k+1)^2(3k+4)=k\ge0.
\]
The odd indices follow from \(\beta(2k-1)=\beta(2k)\).

Write
\[
 \widehat\beta(j)=(3\lceil j/2\rceil+1)^{-1/2},\qquad
 \theta_n=(3(n-3)+1)^{-1/2}.
\]
The numbers of unordered pairs of supports that are equal, sharing an endpoint,
or disjoint are respectively
\(\binom n2\), \(n\binom{n-1}{2}\), and \(3\binom n4\).
There are \(\binom L2\) pairs of different positions on one support
and \(L^2\) position pairs on two supports. Hence the total probability
for the pairs in the first case is bounded above by
\begin{equation}\label{eq:forest-generic}
 G(n,L)=L^2\left[
 \frac12\binom n2\widehat\beta(n-2)^{L-1}
 +n\binom{n-1}{2}\widehat\beta(n-3)^{L-1}
 +3\binom n4\widehat\beta(n-4)^{L-1}\right].
\end{equation}
The middle term uses all pairs of positions on supports with a common endpoint to overestimate
the number in the first case. The exceptional pairs are bounded
separately. There is one exceptional position pair at each depth \(q\)
for each pair of supports with a common endpoint, giving the bound
\begin{equation}\label{eq:forest-exceptional}
 E(n,L)=n\binom{n-1}{2}\frac{\theta_n^r}{1-\theta_n}.
\end{equation}
The union bound is therefore \(\Pr(\text{some collision})\le G(n,L)+E(n,L)\).

\emph{Uniform numerical bounds.}
For \(n\ge9\), the ratio of the expression in
\eqref{eq:forest-generic} at successive lengths is at most
\[
 \left(\frac{13}{12}\right)^2\frac1{\sqrt{10}}<1
 \qquad(L\ge12).
\]
For each parity of \(n\), every summand also decreases with \(n\).
Up to a positive constant it has the form
\[
 \frac{n(n-1)\cdots(n-k+1)}{(n-k+d)^{(L-1)/2}},
 \qquad k\in\{2,3,4\},\quad d\in\{2/3,5/3\}.
\]
Its logarithmic derivative is at most
\[
 \frac{k}{n-k+1}-\frac{L-1}{2(n-k+d)}<0.
\]
Indeed, it suffices that
\(11(n-k+1)-2k(n-k+d)>0\). Its minimum for the displayed choices
and \(n\ge9\) is \(38/3\), at \(k=4,d=5/3,n=9\).
It follows that
\begin{align*}
 G(n,L)&\le\max\{G(9,12),G(10,12)\}=G(10,12)\\
 &=\frac{55080}{13^5\sqrt{13}}+
   \frac{90720}{10^5\sqrt{10}}\\
 &<\frac{18360}{371293}+\frac{189}{625}<\frac9{25}.
\end{align*}
For the comparison, \(G(9,12)\) has the same second term and numerator
\(2592\) in its first term.

Since \(r\ge6\), the expression in
\eqref{eq:forest-exceptional} is at most
\(n\binom{n-1}{2}\theta_n^6/(1-\theta_n)\), which decreases with \(n\ge9\).
For example,
\[
 n\binom{n-1}{2}\theta_n^6
 =\frac1{54}\prod_{j=0}^2\frac{n-j}{n-8/3},
\]
and all three factors decrease; so does \((1-\theta_n)^{-1}\).
Therefore
\[
 E(n,L)\le\frac{252}{19^3(1-1/\sqrt{19})}
 <\frac{336}{6859}<\frac1{20}.
\]
The probability of any collision is consequently less than
\(9/25+1/20=41/100<1/2\).

Finally, the symmetry of \(\operatorname{Bin}(N,1/2)\) gives
\(\Pr(|W|\le\lfloor N/2\rfloor)\ge1/2\). With positive probability
the landmark set both satisfies this size bound and has no histogram
collision. Such a set proves the proposition.
\end{proof}