\input macros.tex
\fi
-\chapter{Notation}
+\chapter{Notation}\id{notapp}%
+
+\section{Symbols}
{\obeylines\parskip=0pt
-\def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
+\def\n#1#2{\>\hangindent=6em\hangafter=1 \hbox to 6em{#1 \dotfill~}#2}
\def\[#1]{~{\it(\ref{#1})}}
-\n{$\bb R$}{the set of all real numbers}
-\n{$\bb N$}{the set of all natural numbers, including 0}
-\n{${\bb N}^+$}{the set of all positive integers}
+
+\n{$A(x,y)$}{Ackermann's function \[ackerdef]}
+\n{$A(x)$}{diagonal Ackermann's function \[ackerdef]}
+\n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
+\n{$C_k$}{cycle on~$k$ vertices}
+\n{${\cal D}(G)$}{optimal MSF decision tree for a~graph~$G$ \[decdef]}
+\n{$D(G)$}{depth of ${\cal D}(G)$ \[decdef]}
+\n{$D(m,n)$}{decision tree complexity of MSF \[decdef]}
+\n{$D_n$}{$n\times n$ matrix with 0's on the main diagonal and 1's elsewhere \[hatrank]}
+\n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
+\n{$E(G)$}{set of edges of a graph~$G$}
+\n{$E$}{$E(G)$ when the graph~$G$ is clear from context}
+\n{${\E}X$}{expected value of a~random variable~$X$}
+\n{$K_k$}{complete graph on~$k$ vertices}
+\n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
+\n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
+\n{$\log n$}{a binary logarithm of the number~$n$}
+\n{$\log^* n$}{iterated logarithm: $\log^*n := \min\{i \mid \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
+\n{$\<LSB>(x)$}{position of the lowest bit set in~$x$ \[lsbmsb]}
+\n{$\<MSB>(x)$}{position of the highest bit set in~$x$ \[lsbmsb]}
+\n{MSF}{minimum spanning forest \[mstdef]}
+\n{$\msf(G)$}{the unique minimum spanning forest of a graph~$G$ \[mstnota]}
+\n{MST}{minimum spanning tree \[mstdef]}
+\n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
+\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
+\n{$m$}{$m(G)$ when the graph~$G$ is clear from context}
+\n{$\bb N$}{set of all natural numbers, including 0}
+\n{${\bb N}^+$}{set of all positive integers}
+\n{$N_0(M)$}{number of permutations satisfying the restrictions~$M$ \[restnota]}
+\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
+\n{$n$}{$n(G)$ when the graph~$G$ is clear from context}
+\n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
\n{$\O(g)$}{asymptotic~$O$: $f=\O(g)$ iff $\exists c>0: f(n)\le g(n)$ for all~$n\ge n_0$}
-\n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
-\n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
\n{$\widetilde\O(g)$}{$f=\widetilde\O(g)$ iff $f=\O(g\cdot\log^{\O(1)} g)$}
+\n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
+\n{${\cal P}_A$}{set of all permutations on a~set~$A$ \[restnota]}
+\n{${\cal P}_{A,M}$}{set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
+\n{$\per M$}{permanent of a~square matrix~$M$}
\n{$\poly(n)$}{$f=\poly(n)$ iff $f=\O(n^c)$ for some $c$}
+\n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
+\n{$\bb R$}{set of all real numbers}
+\n{$R_{C,\prec}(x)$}{rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$R^{-1}_{C,\prec}(i)$}{unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
+\n{$V(G)$}{set of vertices of a graph~$G$}
+\n{$V$}{$V(G)$ when the graph~$G$ is clear from context}
+\n{$W$}{word size of the RAM \[wordsize]}
+\n{$w(e)$}{weight of an edge $e$}
+\n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
+
+\n{$\alpha(n)$}{diagonal inverse of the Ackermann's function \[ackerinv]}
+\n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]}
+\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i \mid \log^{(i)}n \le m/n \}$ \[itjarthm]}
+\n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
+\n{$\delta_G(v)$}{edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
+\n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
+\n{$\lambda_i(n)$}{inverse of the $i$-th row of the Ackermann's function \[ackerinv]}
+\n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
+\n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
+
\n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
\n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
\n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
\n{$G-e$}{graph $G$ with edge $e$ removed}
\n{$G+e$}{graph $G$ with edge $e$ added}
-\n{$w(e)$}{weight of an edge $e$}
-\n{$V(G)$}{set of vertices of a graph~$G$}
-\n{$E(G)$}{set of edges of a graph~$G$}
-\n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
-\n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
-\n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
\n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
-\n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
-\n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
-\n{MST}{minimum spanning tree \[mstdef]}
-\n{MSF}{minimum spanning forest \[mstdef]}
-\n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
-\n{$\msf(G)$}{the unique minimum spanning forest of a graph~$G$ \[mstnota]}
\n{$X \choose k$}{the set of all $k$-element subsets of a set~$X$}
\n{$G/e$}{multigraph contraction \[contract]}
-\n{$G.e$}{simple graph contraction \[simpcont]}
+\n{$G\sgc e$}{simple graph contraction \[simpcont]}
\n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
-\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
+\n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) \mid x\in X \}$}
\n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
-\n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
-\n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
-\n{${\E}X$}{expected value of a~random variable~$X$}
-\n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
-\n{$\log n$}{a binary logarithm of the number~$n$}
\n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
\n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
-\n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
-\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n \le m/n \}$ \[itjarthm]}
-\n{$W$}{word size of the RAM \[wordsize]}
\n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
\n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
\n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
\n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
\n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
\n{$\equiv$}{congruence modulo a~given number}
-\n{$\<LSB>(x)$}{the position of the lowest bit set in~$x$ \[lsbmsb]}
-\n{$\<MSB>(x)$}{the position of the highest bit set in~$x$ \[lsbmsb]}
\n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
-\n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
-\n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
-\n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
-\n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
\n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
\n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
-\n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
-\n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
\n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
-\n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
-\n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
\n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
\n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
-\n{$K_k$}{the complete graph on~$k$ vertices}
-\n{$C_k$}{the cycle on~$k$ vertices}
-\n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]}
-\n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
-\n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]}
-\n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
-\n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]}
-\n{$\per M$}{the permanent of a~square matrix~$M$}
\n{$G\crpt R$}{graph~$G$ with edges in~$R$ corrupted \[corrnota]}
\n{$R^C$}{$R^C = R\cap \delta(C)$ \[corrnota]}
-\n{${\cal D}(G)$}{The optimal MSF decision tree for a~graph~$G$ \[decdef]}
-\n{$D(G)$}{The depth of ${\cal D}(G)$ \[decdef]}
-\n{$D(m,n)$}{Decision tree complexity of MSF \[decdef]}
-\n{$A(x,y)$}{The Ackermann's function \[ackerdef]}
-\n{$A(x)$}{The diagonal Ackermann's function \[ackerdef]}
-\n{$a(x,n)$}{The inverse of the $x$-th row of the Ackermann's function \[ackerinv]}
-\n{$a(n)$}{The diagonal inverse of the Ackermann's function \[ackerinv]}
-\n{$\alpha(m,n)$}{$\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}$ \[ackerinv]}
+\n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
+
}
%--------------------------------------------------------------------------------
the same objects, although they formally differ.
\defn\id{contract}%
-Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
+Let $G=(V,E,M)$ be a multigraph and $e=xy$ its arbitrary edge.
+The \df{(multigraph) contraction of~$e$ in~$G$}
produces a multigraph $G/e=(V',E',M')$ such that:
$$\eqalign{
V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
E' &= E(G) - \{e\},\cr
-M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
+M'(f) &= \{ m(v) \mid v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
}$$
-Sometimes we need contraction for simple graphs as well. It corresponds to performing
-the multigraph contraction, unifying parallel edges and deleting loops.
+Sometimes we need contraction for simple graphs as well. It is equivalent to performing
+the multigraph contraction and then unifying parallel edges and deleting loops.
\defn\id{simpcont}%
-Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
-produces a graph $G.e=(V',E')$ such that:
+Let $G=(V,E)$ a simple graph and $e=xy$ its arbitrary edge.
+The \df{(simple graph) contraction of~$e$ in~$G$}
+produces a graph $G\sgc e=(V',E')$ such that:
$$\eqalign{
V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
-E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
-m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
+E' &= \{ \{m(x),m(y)\} \mid xy\in E \land m(x)\ne m(y) \},\cr
+m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr \noalign{\vskip5pt} v & \hbox{otherwise.}} \cr
}$$
\defn\id{setcont}%
-We can also extend the above definitions to contractions by a~set of vertices or edges.
+We can also extend the above definitions to contractions of a~set of vertices or edges.
For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
$f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
-where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$.
+where $U^*$ is the complete graph on~$U$. Similarly for $G\sgc F$ and $G\sgc U$.
%--------------------------------------------------------------------------------
-\section{Ackermann's function and its inverse}\id{ackersec}%
+\section{Ackermann's function and its inverses}\id{ackersec}%
The Ackermann's function is an~extremely quickly growing function which has been
introduced by Ackermann \cite{ackermann:function} in the context of
Various sources differ in the exact definition of both the Ackermann's
function and its inverse, but most of the differences are in factors that
-are negligible in the light of the giant asymptotic growth of the function.
+are negligible in the light of the giant asymptotic growth of the function.\foot{%
+To quote Pettie \cite{pettie:onlineverify}: ``In the field of algorithms \& complexity,
+Ackermann's function is rarely defined the same way twice. We would not presume to buck
+such a~well-established precedent. Here is a~slight variant.''}
We will use the definition by double recursion given by Tarjan \cite{tarjan:setunion},
which is predominant in the literature on graph algorithms:
Three functions related to the inverse of the function~$A$ are usually considered:
\defn\id{ackerinv}%
-The \df{row inverse} $a(x,y)$ of the Ackermann's function is defined by:
+The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by:
$$
-a(x,n) := \min\{ y \mid A(x,y) > \log n \}.
+\lambda_i(n) := \min\{ y \mid A(i,y) > \log n \}.
$$
-The \df{diagonal inverse} $a(n)$ is defined by:
+The \df{diagonal inverse} $\alpha(n)$ is defined by:
$$
-a(n) := \min\{ x \mid A(x) > \log n \}.
+\alpha(n) := \min\{ x \mid A(x) > \log n \}.
$$
-The \df{alpha function} $\alpha(m,n)$ is defined for $m\ge n$ by:
+The two-parameter \df{alpha function} $\alpha(m,n)$ is defined for $m\ge n$ by:
$$
\alpha(m,n) := \min\{ x\ge 1 \mid A(x,4\lceil m/n\rceil) > \log n \}.
$$
\example
-$a(1,n) = \O(\log\log n)$, $a(2,n) = \O(\log^* n)$, $a(3,n)$ grows even slower
-and $a(n)$ is asymptotically smaller than $a(x,n)$ for any fixed~$x$.
+$\lambda_1(n) = \O(\log\log n)$, $\lambda_2(n) = \O(\log^* n)$, $\lambda_3(n)$ grows even slower
+and $\alpha(n)$ is asymptotically smaller than $\lambda_i(n)$ for any fixed~$i$.
\obs
It is easy to verify that all the rows are strictly increasing and so are all
which covers all values of~$m$ that are likely to occur in practice.
\lemma
-$\alpha(m,n) \le a(n)+1$.
+$\alpha(m,n) \le \alpha(n)+1$.
\proof
+We know that
$A(x,4\lceil m/n\rceil) \ge A(x,4) = A(x-1,A(x,3)) \ge A(x-1,x-1)$, so $A(x,4\lceil m/n\rceil)$
rises above $\log n$ no later than $A(x-1,x-1)$ does.
\qed
\lemma\id{alphaconst}%
-When $k$~is a~fixed constant and $m\ge n\cdot a(k,n)$, then $\alpha(m,n) \le k$.
+When $i$~is a~fixed constant and $m\ge n\cdot \lambda_i(n)$, then $\alpha(m,n) \le i$.
\proof
-The choice of~$m$ guarantees that $A(x,4\lceil m/n\rceil) \ge A(x,a(k,n))$, which
-is greater than $\log n$ for all $x \ge k$.
+The choice of~$m$ guarantees that $A(x,4\lceil m/n\rceil) \ge A(x,\lambda_i(n))$, which
+is greater than $\log n$ for all $x \ge i$.
\qed
\endpart
projects / saga.git / blobdiff