+%--------------------------------------------------------------------------------
+
+\section{Multigraphs and contractions}
+
+Since the formalism of multigraphs is not fixed in the literature, we will
+better define it carefully, following \cite{diestel:gt}:
+
+\defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
+set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
+with the vertices, and $M$ is a mapping $E\rightarrow {V \choose 2} \cup {V \choose 1}$
+which assigns to each edge either a pair of vertices or a single vertex
+(if the edge is a loop).
+
+\proclaim{Notation}%
+When the meaning is clear from the context, we use the standard graph notation
+even for multigraphs. For example, $xy\in E(G)$ becomes a
+shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
+consider multigraphs with no multiple edges nor loops and simple graphs to be
+the same objects, although they formally differ.
+
+\defn\id{contract}%
+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) \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 \noalign{\vskip5pt} v & \hbox{otherwise.}} \cr
+}$$
+
+We sometimes also need to contract edges in simple graphs. 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 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)\} \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 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$ (the result obviously 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\sgc F$ and $G\sgc U$.
+
+%--------------------------------------------------------------------------------
+
+\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
+computability theory. Its original purpose was to demonstrate that not every recursive
+function is also primitive recursive. At the first sight, it does not
+seem related to efficient algorithms at all. Its various inverses however occur in
+analyses of algorithms and mathematical structures surprisingly often:
+We meet them in Section \ref{classalg} in the time complexity of the Disjoint Set Union
+data structure and also in the best known upper bound on the decision tree
+complexity of minimum spanning trees in Section \ref{optalgsect}. Another
+important application is in the complexity of Davenport-Schinzel sequences (see
+Klazar's survey \cite{klazar:gdss}), but as far as we know, these are not otherwise
+related to the topic of our study.
+
+Various sources differ in the exact definition of both the Ackermann's
+function and its inverse, but most of these differences are in factors that
+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.
+
+\defn\id{ackerdef}%
+The \df{Ackermann's function} $A(x,y)$ is a~function on non-negative integers defined as follows:
+$$\eqalign{
+A(0,y) &:= 2y, \cr
+A(x,0) &:= 0, \cr
+A(x,1) &:= 2 \quad \hbox{for $x\ge 1$}, \cr
+A(x,y) &:= A(x-1, A(x,y-1)) \quad \hbox{for $x\ge 1$, $y\ge 2$}. \cr
+}$$
+The functions $A(x,\cdot)$ are called the \df{rows} of $A(x,y)$, similarly $A(\cdot,y)$ are
+its \df{columns.}
+
+Sometimes, a~single-parameter version of this function is also used. It is defined
+as the diagonal of the previous function, i.e., $A(x):=A(x,x)$.
+
+\example
+We can try evaluating $A(x,y)$ in some points:
+$$\eqalign{
+A(x,2) &= A(x-1, A(x,1)) = A(x-1,2) = A(0,2) = 4, \cr
+A(1,y) &= A(0, A(1,y-1)) = 2A(1,y-1) = 2^{y-1}A(1,1) = 2^y, \cr
+A(2,y) &= A(1, A(2,y-1)) = 2^{A(2,y-1)} = 2\tower y \hbox{~~(the tower of exponentials),} \cr
+A(3,y) &= \hbox{the tower function iterated $y$~times,} \cr
+A(4,3) &= A(3,A(4,2)) = A(3,4) = A(2,A(3,3)) = A(2,A(2,A(3,2))) = \cr
+ &= A(2,A(2,4)) = 2\tower(2\tower 4) = 2\tower 65536. \cr
+}$$
+
+\paran{Inverses}%
+As common for functions of multiple parameters, there is no single function which
+could claim the title of the only true Inverse Ackermann's function.
+The following three functions related to the inverse of the function~$A$ are often considered:
+
+\defn\id{ackerinv}%
+The \df{$i$-th row inverse} $\lambda_i(n)$ of the Ackermann's function is defined by:
+$$
+\lambda_i(n) := \min\{ y \mid A(i,y) > \log n \}.
+$$
+The \df{diagonal inverse} $\alpha(n)$ is defined by:
+$$
+\alpha(n) := \min\{ x \mid A(x) > \log n \}.
+$$
+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
+$\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
+columns, except the first three columns which are constant. Therefore for a~fixed~$n$,
+$\alpha(m,n)$ is maximized at $m=n$. So $\alpha(m,n) \le 3$ when $\log n < A(3,4)$,
+which covers all values of~$m$ that are likely to occur in practice.
+
+\lemma
+$\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 $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,\lambda_i(n))$, which
+is greater than $\log n$ for all $x \ge i$.
+\qed
+