Skip to main content
\(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

AppendixCList of Notation

Symbol Description Location
\(n!\) \(n\) factorial Paragraph
\(P(m,n)\) number of permutations Paragraph
\(\binom{n}{k}\) binomial coefficient Paragraph
\(C(n,k)\) binomial coefficient (inline) Paragraph
\(\binom{n}{k_1,k_2,k_3,\dots,k_r}\) multinomial coefficient Paragraph
\(\cgP\) polynomial time problems Paragraph
\(\cgN\cgP\) nondeterministic polynomial time problems Paragraph
\(\deg_\bfG(v)\) degree of vertex \(v\) in graph \(\bfG\) Paragraph
\(\bfK_n\) complete graph on \(n\) vertices Paragraph
\(\bfI_n\) independent graph on \(n\) vertices Paragraph
\(\bfP_n\) path with \(n\) vertices Paragraph
\(\bfC_n\) path with \(n\) vertices Paragraph
\(\chi(\bfG)\) chromatic number of a graph \(\bfG\) Paragraph
\(\omega(\bfG)\) clique number of \(\bfG\) Paragraph
\(x\| y\) \(x\) and \(y\) are incomparable Paragraph
\(\height(\bfP)\) height of poset \(\bfP\) Paragraph
\(\width(\bfP)\) width of poset \(\bfP\) Paragraph
\(D(x), D(S),D[x], D[S]\) down set Paragraph
\(U(x), U(S), U[x], U[S]\) up set Paragraph
\(\bfn\) chain with \(n\) points Paragraph
\(\bfP+\bfQ\) disjoint sum of posets Paragraph
\(\phi(n)\) Euler \(\phi\) function Paragraph
\(\binom{p}{k}\) generalized binomial coefficient Definition 8.8
\(Af(n)\) advancement operator applied to \(f(n)\) Paragraph
\(P(A|B)\) probability of \(A\) given \(B\) Paragraph
\(C(X,k)\) family of all \(k\)-element subsets of \(X\) Paragraph
\(R(m,n)\) Ramsey number Paragraph
\(\langle C\rangle\) equivalence class of \(C\) Paragraph
\(\stab_G(C)\) stabilizer of \(C\) under action of \(G\) Paragraph
\(\overline{E}\) complement of event \(E\) Paragraph
\(x\in X\) \(x\) is a member of the set \(X\) Paragraph
\(x\notin X\) \(x\) is not a member of the set \(X\) Paragraph
\(X\cap Y\) intersection of \(X\) and \(Y\) Paragraph
\(X\cup Y\) union of \(X\) and \(Y\) Paragraph
\(\emptyset\) empty set Paragraph
\(\posints\) set of positive integers Paragraph
\(\ints\) set of integers Paragraph
\(\rats\) set of rational numbers Paragraph
\(\reals\) set of real numbers Paragraph
\(\nonnegints\) set of non-negative integers Paragraph
\([n]\) \(\{1,2,\dots,n\}\) Paragraph
\(X\subseteq Y\) \(X\) is a subset of \(Y\) Paragraph
\(X\subsetneq Y\) \(X\) is a proper subset of \(Y\) Paragraph
\(X\times Y\) cartesian product of \(X\) and \(Y\) Paragraph
\(f\colon X\rightarrow Y\) \(f\) is a function from \(X\) to \(Y\) Paragraph
\(f:X\injection Y\) \(f\) is an injection from \(X\) to \(Y\) Paragraph
\(f\colon X\surjection Y\) \(f\) is a surjection from \(X\) to \(Y\) Paragraph
\(f\colon X\bijection Y\) \(f\) is a bijection from \(X\) to \(Y\) Paragraph
\(|X|\) cardinality of set \(X\) Paragraph