\section{The new optimal adversary}\label{sec:overview}\label{sec:algorithm}

Kaplan, Zamir, and Zwick~\cite[Section~6]{kzz} suggest using continuous
intervals and retaining more complex dependencies between items.
We follow this direction by allowing DAGs of items at each tree node.
The main tasks are to choose answers using bounded neighborhoods and
to show that restoring the degree and path bounds requires few moves
overall.

\input{sections/order-dags}

\subsection{A tree of order-restriction DAGs}

The core data structure of our adversary is a rooted tree. Each node $v$
stores an order-restriction DAG $D_v$, whose vertices are the items
recorded there. Figure~\ref{fig:overview-state} shows an example.

Each item has a record $(x,\ell_x,r_x)$ stored at exactly one node.
The label $x$ identifies the key. The variable $X_x$ describes its
position among the items and child anchors at that node. We call the
item \emph{free} there while this position remains variable.
The interval endpoints are \emph{dyadic rationals}, meaning that their
denominators are powers of two. The stored intervals are canonical.

An arc $x\to y$ in $D_v$ records a comparison answered $x<y$ between
items stored at $v$. A comparison between two free items contributes
at most one arc.

Initially the tree consists of just the root, containing all records
with bounds $\ell_x=0$ and $r_x=1$. The position variables $X_x$ are
unassigned, and the root's graph has no arcs.
Thus every assignment in $(0,1)^n$ is feasible, and every total order
can be obtained by assigning distinct positions.

Each child is attached to a fixed position $c\in(0,1)$ in its parent,
called its \emph{anchor}. A node has at most one child at each anchor.
For any feasible assignment at the parent, an item whose position is
below $c$ precedes the entire child subtree, and an item whose position
is above $c$ follows it. Subtrees of
different children are ordered by their anchors. All items of each child
subtree therefore occur consecutively in the resulting total order.
The child's order-restriction DAG describes the possible orders within this block,
using position variables in $(0,1)$.

\begin{center}
\begin{minipage}{\linewidth}
\captionsetup{hypcap=false}
\centering
\begin{tikzpicture}[>=Latex,font=\small,
  group/.style={draw=ink!65,rounded corners=2pt,fill=pale},
  item/.style={circle,draw=ink,fill=white,minimum size=6mm,inner sep=1pt}]
% Root: the graph, the interval bounds, and the child anchors.
\draw[group] (-6.8,0) rectangle (6.8,4.7);
\node[font=\bfseries] at (0,4.35) {Root};
\node at (-3.8,3.85) {In-node DAG};
\node at (3.2,3.85) {Allowed intervals};
\draw[ink!20] (-.5,1.85)--(-.5,4.05);
\node[item] (oa) at (-5,2.7) {$a$};
\node[item] (ob) at (-2.5,3.3) {$b$};
\node[item] (oc) at (-2.5,2.1) {$c$};
\draw[->,thick,accent] (oa)--(ob);
\draw[->,thick,accent] (oa)--(oc);
\foreach \x/\label in {1/0,2.15/{1/4},3.3/{1/2},4.45/{3/4},5.6/1}
  \node[font=\scriptsize] at (\x,3.45) {$\label$};
\foreach \y/\label/\lo/\hi in {3.05/a/1/4.45,2.55/b/2.15/5.6,2.05/c/2.15/5.6}{
  \node[left] at (.65,\y) {$X_{\label}$};
  \draw[ink!25] (1,\y)--(5.6,\y);
  \draw[accent,very thick] (\lo,\y)--(\hi,\y);
  \draw[accent,fill=white] (\lo,\y) circle (1.7pt);
  \draw[accent,fill=white] (\hi,\y) circle (1.7pt);
}
\node at (0,1.6) {Child anchors in the root's unit interval};
\draw[thick] (-5.8,.7)--(5.8,.7);
\node[below] at (-5.8,.65) {$0$};
\node[below] at (5.8,.65) {$1$};
\fill (-2.9,.7) circle (2.3pt);
\fill (2.9,.7) circle (2.3pt);
\node[above=3pt] at (-2.9,.7) {$1/4$};
\node[above=3pt] at (2.9,.7) {$3/4$};
\draw[thick,ink!55] (-2.9,.7)--(-2.9,-.2)--(-3.55,-.9);
\draw[thick,ink!55] (2.9,.7)--(2.9,-.2)--(3.55,-.9);
% Each child repeats both kinds of information on its own unit interval.
\begin{scope}[shift={(-3.55,-.9)}]
\draw[group] (-3.25,-3) rectangle (3.25,0);
\node[font=\bfseries] at (0,-.35) {Child at $1/4$};
\node[font=\footnotesize] at (-1.9,-.85) {In-node DAG};
\node[font=\footnotesize] at (1.5,-.85) {Allowed intervals};
\draw[ink!20] (-.55,-1.1)--(-.55,-2.5);
\node[item] (op) at (-2.55,-1.7) {$p$};
\node[item] (oq) at (-1.25,-1.7) {$q$};
\draw[->,thick,accent] (op)--(oq);
\foreach \x/\label in {.4/0,2.8/1}
  \node[font=\scriptsize] at (\x,-1.25) {$\label$};
\foreach \y/\label/\lo/\hi in {-1.7/p/.4/2.8,-2.2/q/.4/2.8}{
  \node[left] at (.15,\y) {$X_{\label}$};
  \draw[ink!25] (.4,\y)--(2.8,\y);
  \draw[accent,very thick] (\lo,\y)--(\hi,\y);
  \draw[accent,fill=white] (\lo,\y) circle (1.7pt);
  \draw[accent,fill=white] (\hi,\y) circle (1.7pt);
}
\node[font=\footnotesize] at (0,-2.7) {Positions within this child};
\end{scope}
\begin{scope}[shift={(3.55,-.9)}]
\draw[group] (-3.25,-3) rectangle (3.25,0);
\node[font=\bfseries] at (0,-.35) {Child at $3/4$};
\node[font=\footnotesize] at (-1.9,-.85) {In-node DAG};
\node[font=\footnotesize] at (1.5,-.85) {Allowed intervals};
\draw[ink!20] (-.55,-1.1)--(-.55,-2.5);
\node[item] (orr) at (-2.55,-1.7) {$r$};
\node[item] (os) at (-1.25,-1.7) {$s$};
\draw[->,thick,accent] (orr)--(os);
\foreach \x/\label in {.4/0,2.8/1}
  \node[font=\scriptsize] at (\x,-1.25) {$\label$};
\foreach \y/\label in {-1.7/r,-2.2/s}{
  \node[left] at (.15,\y) {$X_{\label}$};
  \draw[accent,very thick] (.4,\y)--(2.8,\y);
  \draw[accent,fill=white] (.4,\y) circle (1.7pt);
  \draw[accent,fill=white] (2.8,\y) circle (1.7pt);
}
\node[font=\footnotesize] at (0,-2.7) {Positions within this child};
\end{scope}
\end{tikzpicture}
\captionof{figure}{A state of the adversary. Each large box is a tree node,
containing an order-restriction DAG, drawn as its arcs and allowed intervals.}
\label{fig:overview-state}
\end{minipage}
\end{center}

In the root of Figure~\ref{fig:overview-state}, the in-node DAG records $a<b$ and
$a<c$.
To read an order from this state, choose feasible positions at each node,
avoiding ties with other items or child anchors. List the items and anchors
from left to right, and recursively replace each anchor by its child's
order. For example, root positions
$(X_a,X_b,X_c)=(1/3,1/2,7/8)$ give
\[
p<q<a<b<r<s<c.
\]
Other feasible choices give other orders. The \emph{transcript} $\mathcal T$ is the sequence of answers so far. Our invariant is
that every represented order satisfies the transcript. The tree need not
represent every order that satisfies it.