\section{Canonical intervals and densities}\label{app:geometry}

We prove Lemma~\ref{lem:interior} for order-restriction DAGs. We then establish the
density bounds used to choose anchors and analyse probability certificates.

\subsection{Normalization and restriction}

\begin{lemma}[Normalization]\label{lem:normalization}
\textnormal{\texttt{Normalize}} preserves $K(D)$. The resulting region
has positive volume if and only if every interval has positive width;
in that case the intervals are canonical.
\end{lemma}
\begin{proof}[Proof of Lemmas~\ref{lem:normalization} and~\ref{lem:interior}]
Every propagated bound is already implied by an arc and an interval
bound. A forward topological pass propagates every lower bound to all
its successors; the reverse pass propagates every upper bound to all
its predecessors. Thus normalization preserves the region and gives
$\ell_x\le\ell_y$ and $r_x\le r_y$ along every arc $x\to y$.

Positive volume requires positive widths. Conversely, suppose all widths
are positive. Choose numbers $0<\theta_x<1$ increasing in a topological
order, and set
\[
X_x=(1-\theta_x)\ell_x+\theta_xr_x.
\]
Along an arc $x\to y$, increasing $\theta_x$ to $\theta_y$ strictly
increases this value, because $r_x>\ell_x$. Replacing the endpoints by
$\ell_y,r_y$ cannot decrease it. Thus $X_x<X_y$, all interval bounds
hold strictly, and a small open neighborhood is feasible.

Now fix $X_x=c$ in the normalized interval and delete its coordinate.
Every incident inequality becomes exactly the bound imposed by
\texttt{Restrict}, while all other inequalities persist. This proves
that the resulting region is the section at $c$. Lower bounds propagate forward
and upper bounds backward. Any earlier lower bound that reached a
successor through $x$ is superseded by $c>\ell_x$; any earlier upper
bound that reached a predecessor through $x$ is superseded by $c<r_x$.
The normalized intervals of the remaining coordinates are therefore
\begin{equation}\label{eq:section-intervals}
\begin{cases}
(\ell_y,\min(r_y,c)),&y\text{ precedes }x,\\
(\max(\ell_y,c),r_y),&y\text{ succeeds }x,\\
(\ell_y,r_y),&y\text{ is incomparable with }x.
\end{cases}
\end{equation}
A predecessor retains positive width because $r_y>\ell_y$ and
$c>\ell_x\ge\ell_y$. A successor does too because $r_y>\ell_y$ and
$c<r_x\le r_y$. Other widths are unchanged. The criterion just proved
shows that the section has positive volume. Since this holds for every
$c\in(\ell_x,r_x)$, that interval is exactly the coordinate projection. The volume identity
in Lemma~\ref{lem:interior} follows from the definition of $f_x(c)$ as
section volume divided by $V(D)$.
\end{proof}

\subsection{Bounds from convex sections}

Let $V$ be the set of coordinates,
let $N=|V|$, and let
$K\subseteq\R^V$ be their feasible region.
For a coordinate $x$ and a real number $t$, write
\[
K_x(t)=\{(z_i)_{i\ne x}:z\in K,\ z_x=t\},
\qquad S_x(t)=\vol_{N-1}K_x(t).
\]
Here $K_x(t)$ is the $(N-1)$-dimensional section obtained by fixing
coordinate $x$ at $t$. The uniform distribution on $K$
therefore gives $x$ the density
\[
f_x(t)=\frac{S_x(t)}{\vol_N K}.
\]
These formulas define $f_x$ pointwise, and we use this definition throughout.
If some coordinates have already been fixed, we use the same
definitions in the remaining free coordinates. In dimension zero, the
volume of the singleton consisting of the empty assignment is one.

\begin{lemma}[Density of a linear projection]\label{lem:projection-density}
Let $C\subseteq\R^d$ be a bounded open convex region of positive volume,
and let $\varphi$ be a nonzero linear functional with
$\varphi(C)=(\ell,r)$ of width $W$. For $X$ uniform on $C$, the density
$g$ of $\varphi(X)$ satisfies
\[
g(t)\le\frac dW,\qquad
g(t)\ge\frac{4^{-(d-1)}}W
\quad(\ell+W/4\le t\le r-W/4).
\]
\end{lemma}
\begin{proof}
An invertible linear change of coordinates makes $\varphi$ the first
coordinate. Its constant Jacobian preserves uniformity on the transformed
region, so it suffices to prove the bounds for a coordinate projection.
Write $S(t)$ for the section volume at that coordinate's value $t$;
then $g(t)=S(t)/\vol C$.

Choose points in $\overline C$ whose first coordinates are $\ell$ and $r$.
Such points exist because $C$ is bounded. For $\ell<t<s<r$, join every
point of the section at $t$ to the point at $r$. Since $C$ is open and
convex, the image with first coordinate $s$ lies in the section of $C$ there. Each of its
$d-1$ directions is scaled by $(r-s)/(r-t)$, so
\begin{equation}\label{eq:push-upper}
S(s)\ge\left(\frac{r-s}{r-t}\right)^{d-1}S(t)
\qquad(t<s).
\end{equation}
Joining instead to the point at $\ell$ gives
\begin{equation}\label{eq:push-lower}
S(s)\ge\left(\frac{s-\ell}{t-\ell}\right)^{d-1}S(t)
\qquad(s<t).
\end{equation}
Normalize these inequalities and integrate over $s$ on both sides of $t$:
\[
1\ge g(t)\left(
\int_\ell^t\left(\frac{s-\ell}{t-\ell}\right)^{d-1}ds+
\int_t^r\left(\frac{r-s}{r-t}\right)^{d-1}ds\right)
=\frac{Wg(t)}{d}.
\]
Thus $g(t)\le d/W$.

For the lower bound, choose $t_0$ with $g(t_0)\ge1/W$, which exists
because $g$ integrates to one over an interval of length $W$. For any
$s\in[\ell+W/4,r-W/4]$, the appropriate ratio in
\eqref{eq:push-upper} or \eqref{eq:push-lower} is at least $1/4$.
Consequently
\[
g(s)\ge4^{-(d-1)}g(t_0)\ge\frac{4^{-(d-1)}}{W}.
\]
The case $s=t_0$ satisfies the same bound directly.
\end{proof}

\begin{lemma}[Coordinate density bounds]\label{lem:fiber}
Let $D$ be a canonical order-restriction DAG with $V(D)>0$, and suppose
$x$ has at most
$B$ other comparable coordinates and canonical interval $(\ell,r)$ of
width $W$. Its density satisfies
\begin{align}
f_x(t)&\le\frac{B+1}{W},\label{eq:fiber-upper}\\
f_x(t)&\ge\frac{4^{-B}}{W}
\qquad(\ell+W/4\le t\le r-W/4).\label{eq:fiber-lower}
\end{align}
\end{lemma}
\begin{proof}
Fix all coordinates incomparable with $x$, at values leaving a nonempty
region. By the section formula in Lemma~\ref{lem:interior}, each such
fixing leaves $x$'s canonical interval unchanged. The remaining region
$C$ is open and convex, has dimension $d\le B+1$, and still projects
onto $(\ell,r)$ in coordinate $x$. Lemma~\ref{lem:projection-density}
therefore gives both required bounds for the density of $x$ in $C$.

Average over the fixed coordinates. If $\omega$ denotes their values,
$C_\omega$ the remaining region, and $g_\omega$ its coordinate density,
integration of each section gives the pointwise identity
\[
f_x(t)=
\frac{\int \vol(C_\omega)g_\omega(t)\,d\omega}
     {\int \vol(C_\omega)\,d\omega}.
\]
Empty slices contribute zero. The bounds on $g_\omega$ are uniform in
$\omega$, so they also hold for $f_x$.
\end{proof}

\begin{lemma}[A bound for small differences]\label{lem:gap}
Let $X$ be uniform on $K(D)$ for a canonical order-restriction DAG
$D$ with $V(D)>0$, and suppose $x$ has
at most $B$ other comparable coordinates and canonical interval of width
$W$. Let $Y$ be a fixed number or $X_y$ for any distinct free coordinate
$y$. For every interval $I$ of length $a$,
\begin{equation}\label{eq:gap}
\Prb(X_x-Y\in I)\le\frac{(B+1)a}{W}.
\end{equation}
\end{lemma}
\begin{proof}
For a fixed number $Y$, integrate the coordinate-density upper bound
over $I+Y$. Now let $Y=X_y$ for any free coordinate $y\ne x$.
As above, fix all coordinates incomparable with $x$. The remaining
convex region $C$ has dimension $d\le B+1$, and $x$ retains its
width $W$. We show that the projection $X_x-X_y$ has width
at least $W$ in each such region.

If $y$ is incomparable with $x$, it is now fixed, so the projection is
a translate of $X_x$ and has width $W$. Otherwise $y$ remains free.
Write $(\ell_z,r_z)$ for canonical intervals in $C$; $x$'s endpoints
are unchanged. If a directed path goes from $x$ to $y$, then $r_y\ge r_x$.
Fixing $X_y=t\in(\ell_y,r_y)$ leaves $x$ the interval
$(\ell_x,\min(r_x,t))$, by Lemma~\ref{lem:interior}. As $t$ approaches
$r_y$, its width tends to $W$. On that section the difference
$X_x-t$ varies over an interval of the same width. Thus the projection
of the whole region $C$ has width at least $W$.
If a directed path goes from $y$ to $x$, let $t$ approach $\ell_y$ instead.
Here $\ell_y\le\ell_x$, and the remaining interval
$(\max(\ell_x,t),r_x)$ again has width tending to $W$.

Lemma~\ref{lem:projection-density} bounds the conditional density of the
difference by $d/W\le(B+1)/W$. Integrating over $I$ and averaging over
the fixed coordinates proves \eqref{eq:gap}. If both coordinates have
at most $B$ comparable coordinates, exchanging $x$ and $y$ gives the
same bound with $\max(W_x,W_y)$ in the denominator.
\end{proof}

\subsection{Density in a central interval}

A density is \emph{log-concave} if its positive support is convex and its
logarithm is concave there. The coordinate densities above are log-concave pointwise: the uniform
density on $K$ is log-concave, and integrating out the other coordinates
preserves this property by Pr\'ekopa's marginal theorem
\cite[Theorem~8]{prekopa}. We finish with the density bound used for
positions having substantial probability on each side.

\begin{lemma}[Density at central positions]\label{lem:central-quantiles}
Let $X$ have a log-concave density $f$. If
$\Prb(X\le c)\ge p$ and $\Prb(X\ge c)\ge p$ for some $0<p\le1/2$, then
\[
f(c)\ge p\sup_t f(t).
\]
\end{lemma}
\begin{proof}
For $s\le c\le t$, log-concavity gives
\[
f(s)f(t)\le f(c)f(s+t-c).
\]
Indeed, $c$ and $s+t-c$ are complementary convex combinations of $s,t$;
multiply the two log-concavity inequalities. Fixing $t\ge c$ and
integrating over $s\le c$ gives
\[
p f(t)\le f(c)\int_{-\infty}^c f(s+t-c)\,ds\le f(c).
\]
Here the first inequality uses the mass at least $p$ to the left of $c$,
and the last uses that a density integrates to one. Fixing $s\le c$ and
integrating over $t\ge c$ instead uses the right-hand mass and gives
$p f(s)\le f(c)$. Taking the supremum over both sides of $c$ proves the
claim.
\end{proof}

\begin{lemma}[Density in a central interval]\label{lem:central-density}
Let $X$ be uniform on $K(D)$ for an order-restriction DAG $D$ with
$V(D)>0$. Suppose
$J=[u,v]\subset(\ell_x,r_x)$ satisfies
\[
\Prb(X_x\le u)\ge\tfrac14,\qquad
\Prb(X_x\in J)\ge\tfrac14,\qquad
\Prb(X_x\ge v)\ge\tfrac14.
\]
Then, for every $c\in J$,
\[
f_x(c)\ge\frac1{16|J|}.
\]
\end{lemma}
\begin{proof}[Proof of Lemma~\ref{lem:central-density}]
Put $M=\sup_t f_x(t)$. The inside-mass condition gives $M|J|\ge1/4$.
Every $c\in J$ has probability at least $1/4$ on each side, so
Lemma~\ref{lem:central-quantiles} gives $f_x(c)\ge M/4\ge1/(16|J|)$.
\end{proof}