Larger cover letters.

[saga.git] / notation.tex

diff --git a/notation.tex b/notation.tex
index e331e972bf59011970285c0742f594dd77fe45f6..e1e424f4ea29e21399375eac188f26167d2424a2 100644 (file)
--- a/notation.tex
+++ b/notation.tex
@@ -2,7 +2,7 @@
 \input macros.tex
 \fi
 
-\chapter{Notation}
+\chapter{Notation}\id{notapp}%
 
 \section{Symbols}
 
@@ -63,10 +63,10 @@
 \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{$\lambda_i(n)$}{inverse of the $i$-th row of the Ackermann's function \[ackerinv]}
-\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{$\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]}
@@ -76,7 +76,7 @@
 \n{$G[U]$}{subgraph induced by a~set $U\subset V(G)$}
 \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) \mid x\in X \}$}
 \n{$f[e]$}{as edges are two-element sets, $f[e]$ maps both endpoints of an edge~$e$}
@@ -124,7 +124,8 @@ 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 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
@@ -133,25 +134,26 @@ 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)\} \mid 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
+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$.
 
 %--------------------------------------------------------------------------------