From fbc659af8572da70e464fd2f5e1f7dae4ac8128c Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Sat, 19 Apr 2008 15:14:25 +0200 Subject: [PATCH] Unified set notation. --- PLAN | 12 +++++++----- adv.tex | 4 ++-- notation.tex | 10 +++++----- ram.tex | 2 +- rank.tex | 6 +++--- 5 files changed, 18 insertions(+), 16 deletions(-) diff --git a/PLAN b/PLAN index c11700f..6f6313e 100644 --- a/PLAN +++ b/PLAN @@ -99,15 +99,17 @@ Notation: - impedance mismatch in terminology: contraction of G along e vs. contraction of e. - use \delta(X) notation - unify use of n(G) vs. n -- use calligraphic letters from ams? - change the notation for contractions -- use double slash instead of the dot? - introduce \widehat\O early -- unify { x ; ... }, { x | ...} and { x : ... } - Ackermann: which of the Tarjan's set union papers should we cite? -- Ackermann function vs. Ackermann's function -Varia: +Typography: -- cite GA booklet - formatting of multi-line \algin, \algout +- use calligraphic letters from ams? + +Global: + +- Intro: cite GA booklet - each chapter should make clear in which model we work +- clean up bibliography diff --git a/adv.tex b/adv.tex index 0f2d5d9..104a814 100644 --- a/adv.tex +++ b/adv.tex @@ -473,7 +473,7 @@ how the algorithm could have stopped growing the tree~$R_i^j$: \thm\id{itjarthm}% The Iterated Jarn\'\i{}k's algorithm finds the MST of the input graph in time -$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i: \log^{(i)}n \le m/n \}$. +$\O(m\timesbeta(m,n))$, where $\beta(m,n):=\min\{ i \mid \log^{(i)}n \le m/n \}$. \proof Phases are finite and in every phase at least one edge is contracted, so the outer @@ -567,7 +567,7 @@ we will find the heaviest edge of the tree path $T[u,v]$ and compare its weight to $w(uv)$. It is therefore sufficient to solve the following problem: \problem -Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] ; u,v\in V(T) \}$ +Given a~weighted tree~$T$ and a~set of \df{query paths} $Q \subseteq \{ T[u,v] \mid u,v\in V(T) \}$ specified by their endpoints, find the heaviest edge (\df{peak}) for every path in~$Q$. \paran{Bor\o{u}vka trees}% diff --git a/notation.tex b/notation.tex index 5e46fe3..24a4624 100644 --- a/notation.tex +++ b/notation.tex @@ -37,7 +37,7 @@ \n{$G/e$}{multigraph contraction \[contract]} \n{$G.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} @@ -46,8 +46,8 @@ \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{$\log^* n$}{the iterated logarithm: $\log^*n := \min\{i \mid \log^{(i)}n \le 1\}$; the inverse of~$2\tower n$} +\n{$\beta(m,n)$}{$\beta(m,n) := \min\{i \mid \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]} @@ -120,7 +120,7 @@ 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 }$$ @@ -132,7 +132,7 @@ Let $G=(V,E)$ a simple graph and $e=xy$ its edge. \df{(Simple graph) contraction produces a graph $G.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 +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 }$$ diff --git a/ram.tex b/ram.tex index 651ad74..9b0084a 100644 --- a/ram.tex +++ b/ram.tex @@ -936,7 +936,7 @@ lengths of the strings in~$S$. \defn For our set~$X$, we define~$T$ as a~compressed trie for the set of binary -encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W ; x\in X \}$. +encodings of the numbers~$x_i$, padded to exactly $W$~bits, i.e., for $S = \{ \(x)_W \mid x\in X \}$. \obs The trie~$T$ has several interesting properties. Since all words in~$S$ have the same diff --git a/rank.tex b/rank.tex index a2b5ef6..82c191b 100644 --- a/rank.tex +++ b/rank.tex @@ -339,7 +339,7 @@ $T(\pi)$ avoids the holes. Let~$H\subseteq B$ be any set of holes in the board. Then: \itemize\ibull \:$N_j$ denotes the number of placements of $n$~rooks on the board such that exactly~$j$ of the rooks -stand on holes. That is, $N_j := \#\{ \pi\in{\cal P}: \#(H\cap T(\pi)) = j \}$. +stand on holes. That is, $N_j := \#\{ \pi\in{\cal P} \mid \#(H\cap T(\pi)) = j \}$. \:$r_k$ is the number of ways how to place $k$~rooks on the holes. In other words, this is the number of $k$-element subsets of~$H$ such that no two elements share a~common row or column. @@ -375,7 +375,7 @@ $$N_0 = N(0) = \sum_{k=0}^n (-1)^k \cdot (n-k)! \cdot r_k.$$ \example\id{hatcheck}% Let us apply this theory to the hatcheck lady problem. The set~$H$ of holes is the main diagonal -of the board: $H=\{ (i,i) : i\in[n] \}$. When we want to place $k$~rooks on the holes, +of the board: $H=\{ (i,i) \mid i\in[n] \}$. When we want to place $k$~rooks on the holes, we can do that in $r_k={n\choose k}$ ways. By the previous corollary, the number of derangements is: $$ @@ -599,7 +599,7 @@ instead. We will show that for the derangements one can achieve linear time comp \nota\id{hatrank}% As we already know, the hatcheck permutations correspond to restriction matrices that contain zeroes only on the main diagonal and graphs that are -complete bipartite with the matching $\{(i,i) : i\in[n]\}$ deleted. For +complete bipartite with the matching $\{(i,i) \mid i\in[n]\}$ deleted. For a~given order~$n$, we will call this matrix~$D_n$ and the graph~$G_n$ and we will show that the submatrices of~$D_n$ share several nice properties: -- 2.39.5