notation.tex

   1 \ifx\endpart\undefined
   2 \input macros.tex
   3 \fi
   4
   5 \chapter{Notation}
   6
   7 {\obeylines\parskip=0pt
   8 \def\n#1#2{\>\hbox to 6em{#1 \dotfill} #2}
   9 \def\[#1]{~{\it(\ref{#1})}}
  10 \n{$\bb R$}{the set of all real numbers}
  11 \n{$\bb N$}{the set of all natural numbers, including 0}
  12 \n{${\bb N}^+$}{the set of all positive integers}
  13 \n{$\O(g)$}{asymptotic~$O$: $f=\O(g)$ iff $\exists c>0: f(n)\le g(n)$ for all~$n\ge n_0$}
  14 \n{$\Omega(g)$}{asymptotic~$\Omega$: $f=\Omega(g)$ iff $\exists c>0: f(n)\ge g(n)$ for all~$n\ge n_0$}
  15 \n{$\Theta(g)$}{asymptotic~$\Theta$: $f=\Theta(g)$ iff $f=\O(g)$ and $f=\Omega(g)$}
  16 \n{$\widetilde\O(g)$}{$f=\widetilde\O(g)$ iff $f=\O(g\cdot\log^{\O(1)} g)$}
  17 \n{$\poly(n)$}{$f=\poly(n)$ iff $f=\O(n^c)$ for some $c$}
  18 \n{$T[u,v]$}{the path in a tree~$T$ joining vertices $u$ and $v$ \[heavy]}
  19 \n{$T[e]$}{the path in a tree~$T$ joining the endpoints of an~edge~$e$ \[heavy]}
  20 \n{$A\symdiff B$}{symetric difference of sets: $(A\setminus B) \cup (B\setminus A)$}
  21 \n{$G-e$}{graph $G$ with edge $e$ removed}
  22 \n{$G+e$}{graph $G$ with edge $e$ added}
  23 \n{$w(e)$}{weight of an edge $e$}
  24 \n{$V(G)$}{set of vertices of a graph~$G$}
  25 \n{$E(G)$}{set of edges of a graph~$G$}
  26 \n{$n(G)$}{number of vertices of a graph~$G$, that is $\vert V(G)\vert$}
  27 \n{$m(G)$}{number of edges of a graph~$G$, that is $\vert E(G)\vert$}
  28 \n{$V,E,n,m$}{when used without $(G)$, they refer to the input of the current algorithm}
  29 \n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
  30 \n{$\delta_G(U)$}{all edges connecting $U\subset V(G)$ with $V(G)\setminus U$; we usually omit the~$G$}
  31 \n{$\delta_G(v)$}{the edges of a one-vertex cut, i.e., $\delta_G(\{v\})$}
  32 \n{MST}{minimum spanning tree \[mstdef]}
  33 \n{MSF}{minimum spanning forest \[mstdef]}
  34 \n{$\mst(G)$}{the unique minimum spanning tree of a graph~$G$ \[mstnota]}
  35 \n{$\msf(G)$}{the unique minimum spanning forest of a graph~$G$ \[mstnota]}
  36 \n{$X \choose k$}{the set of all $k$-element subsets of a set~$X$}
  37 \n{$G/e$}{multigraph contraction \[contract]}
  38 \n{$G.e$}{simple graph contraction \[simpcont]}
  39 \n{$G/X$, $G.X$}{contraction by a~set $X$ of vertices or edges \[setcont]}
  40 \n{$\alpha(n)$}{the inverse Ackermann's function}
  41 \n{$f[X]$}{function applied to a set: $f[X]:=\{ f(x) ; x\in X \}$}
  42 \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
  43 \n{$\varrho({\cal C})$}{edge density of a graph class~$\cal C$ \[density]}
  44 \n{$\deg_G(v)$}{degree of vertex~$v$ in graph~$G$; we omit $G$ if it is clear from context}
  45 \n{${\E}X$}{expected value of a~random variable~$X$}
  46 \n{${\rm Pr}[\varphi]$}{probability that a predicate~$\varphi$ is true}
  47 \n{$\log n$}{a binary logarithm of the number~$n$}
  48 \n{$f^{(i)}$}{function~$f$ iterated $i$~times: $f^{(0)}(x):=x$, $f^{(i+1)}(x):=f(f^{(i)}(x))$}
  49 \n{$2\tower n$}{the tower function (iterated exponential): $2\tower 0:=1$, $2\tower (n+1):=2^{2\tower n}$}
  50 \n{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i: \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$}
  51 \n{$\beta(m,n)$}{$\beta(m,n) := \min\{i: \log^{(i)}n \le m/n \}$ \[itjarthm]}
  52 \n{$W$}{word size of the RAM \[wordsize]}
  53 \n{$\(x)$}{number~$x\in{\bb N}$ written in binary \[bitnota]}
  54 \n{$\(x)_b$}{$\(x)$ zero-padded to exactly $b$ bits \[bitnota]}
  55 \n{$x[i]$}{when $x\in{\bb N}$: the value of the $i$-th bit of~$x$ \[bitnota]}
  56 \n{$x[B]$}{when $x\in{\bb N}$: the values of the bits at positions in the set~$B$ \[qhnota]}
  57 \n{$\pi[i]$}{when $\pi$ is a~sequence: the $i$-th element of~$\pi$, starting with $\pi[1]$ \[brackets]}
  58 \n{$\pi[i\ldots j]$}{the subsequence $\pi[i], \pi[i+1], \ldots, \pi[j]$}
  59 \n{$\sigma^k$}{the string~$\sigma$ repeated $k$~times \[bitnota]}
  60 \n{$\0$, $\1$}{bits in a~bit string \[bitnota]}
  61 \n{$\equiv$}{congruence modulo a~given number}
  62 \n{$\<LSB>(x)$}{the position of the lowest bit set in~$x$ \[lsbmsb]}
  63 \n{$\<MSB>(x)$}{the position of the highest bit set in~$x$ \[lsbmsb]}
  64 \n{$\bf x$}{a~vector with elements $x_1,\ldots,x_d$; $x$ is its bitwise encoding \[vecnota]}
  65 \n{$\band$}{bitwise conjunction: $(x\band y)[i]=1$ iff $x[i]=1 \land y[i]=1$}
  66 \n{$\bor$}{bitwise disjunction: $(x\bor y)[i]=1$ iff $x[i]=1 \lor y[i]=1$}
  67 \n{$\bnot$}{bitwise negation: $(\bnot x)[i]=1-x[i]$}
  68 \n{$\bxor$}{bitwise non-equivalence: $(x\bxor y)[i]=1$ iff $x[i]\ne y[i]$}
  69 \n{$x \shl n$}{bitwise shift of~$x$ by $n$~positions to the left: $x\shl n = x\cdot 2^n$}
  70 \n{$x \shr n$}{bitwise shift of~$x$ by $n$~positions to the right: $x\shr n = \lfloor x/2^n \rfloor$}
  71 \n{$R_{C,\prec}(x)$}{the rank of~$x$ in a~set~$C$ ordered by~$\prec$ \[rankdef]}
  72 \n{$R^{-1}_{C,\prec}(i)$}{the unrank of~$i$: the $i$-th smallest element of a~set~$C$ ordered by~$\prec$ \[rankdef]}
  73 \n{$[n]$}{the set $\{1,2,\ldots,n\}$ \[pranksect]}
  74 \n{$L(\pi,A)$}{lexicographic ranking function for permutations on a~set~$A\subseteq{\bb N}$ \[brackets]}
  75 \n{$L^{-1}(i,A)$}{lexicographic unranking function, the inverse of~$L$ \[brackets]}
  76 \n{$n^{\underline k}$}{the $k$-th falling factorial power: $n\cdot(n-1)\cdot\ldots\cdot(n-k+1)$ \[kpranksect]}
  77 \n{$H\minorof G$}{$H$ is a~minor of~$G$ \[minordef]}
  78 \n{$K_k$}{the complete graph on~$k$ vertices}
  79 \n{$C_k$}{the cycle on~$k$ vertices}
  80 \n{${\cal P}_A$}{the set of all permutations on a~set~$A$ \[restnota]}
  81 \n{${\cal P}_{A,M}$}{the set of all permutations on~$A$ satisfying the restrictions~$M$ \[restnota]}
  82 \n{$N_0(M)$}{the number of permutations satisfying the restrictions~$M$ \[restnota]}
  83 \n{$M^{i,j}$}{the matrix $M$ with $i$-th row and $j$-th column deleted \[restnota]}
  84 \n{$D_n$}{the $n\times n$ matrix with $D[i,i]=0$ for all~$i$ and ones elsewhere else \[hatrank]}
  85 \n{$\per M$}{the permanent of a~square matrix~$M$}
  86 \n{$G\crpt R$}{graph~$G$ with edges in~$R$ corrupted \[corrnota]}
  87 \n{$R^C$}{$R^C = R\cap \delta(C)$ \[corrnota]}
  88 \n{${\cal D}(G)$}{The optimal MSF decision tree for a~graph~$G$ \[decdef]}
  89 \n{$D(G)$}{The depth of ${\cal D}(G)$ \[decdef]}
  90 \n{$D(m,n)$}{Decision tree complexity of MSF \[decdef]}
  91 }
  92
  93 %--------------------------------------------------------------------------------
  94
  95 \section{Multigraphs and contractions}
  96
  97 Since the formalism of multigraphs is not fixed in the literature, we will
  98 better define it carefully, following \cite{diestel:gt}:
  99
 100 \defn A~\df{multigraph} is an ordered triple $(V,E,M)$, where $V$~is the
 101 set of vertices, $E$~is the set of edges, taken as abstract objects disjoint
 102 with the vertices, and $M$ is a mapping $E\rightarrow V \cup {V \choose 2}$
 103 which assigns to each edge either a pair of vertices or a single vertex
 104 (if the edge is a loop).
 105
 106 \proclaim{Notation}%
 107 When the meaning is clear from the context, we use our notation originally
 108 defined for graphs even for multigraphs. For example, $xy\in E(G)$ becomes a
 109 shorthand for $\exists e\in E(G)$ such that $M(G)(e) = \{x,y\}$. Also, we
 110 consider multigraphs with no multiple edges nor loops and simple graphs to be
 111 the same objects, although they formally differ.
 112
 113 \defn\id{contract}%
 114 Let $G=(V,E,M)$ be a multigraph and $e=xy$ its edge. \df{(Multigraph) contraction of~$G$ along~$e$}
 115 produces a multigraph $G/e=(V',E',M')$ such that:
 116 $$\eqalign{
 117 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
 118 E' &= E(G) - \{e\},\cr
 119 M'(f) &= \{ m(v) ; v\in M(f) \} \quad\hbox{for every $f=\in E'$, and}\cr
 120 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
 121 }$$
 122
 123 Sometimes we need contraction for simple graphs as well. It corresponds to performing
 124 the multigraph contraction, unifying parallel edges and deleting loops.
 125
 126 \defn\id{simpcont}%
 127 Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction of~$G$ along~$e$}
 128 produces a graph $G.e=(V',E')$ such that:
 129 $$\eqalign{
 130 V' &= (V(G) \setminus \{x,y\}) \cup \{v_e\},\quad\hbox{where $v_e$ is a new vertex,}\cr
 131 E' &= \{ \{m(x),m(y)\} ; xy\in E \land m(x)\ne m(y) \},\cr
 132 m(x) &= \cases{v_e & \hbox{for $v=x,y,$}\cr v & \hbox{otherwise.}} \cr
 133 }$$
 134
 135 \defn\id{setcont}%
 136 We can also extend the above definitions to contractions by a~set of vertices or edges.
 137 For $F\subseteq E(G)$, the graph $G/F$ is defined as $(G/f_1)/f_2/\ldots/f_k$ where
 138 $f_1,\ldots,f_k$ are the elements of~$F$ (you can observe that the result
 139 does not depend on the order of edges). For $U\subseteq V(G)$, we define $G/U$
 140 as the graph with all vertices of~$U$ merged to a~single vertex, that is $(G\cup U^*)/U^*$,
 141 where $U^*$ is the complete graph on~$U$. Similarly for $G.F$ and $G.U$.
 142
 143 %--------------------------------------------------------------------------------
 144
 145 \section{Ackermann function and its inverse}\id{ackersec}%
 146
 147 \endpart