Fundamental Definitions and Notations

In the study of algorithms and probability, establishing a clear and consistent language is paramount. We begin by defining the fundamental building blocks and notations that will serve as the foundation for our explorations in graph theory and probability. These notations are not mere conventions; they are the precise tools with which we articulate complex relationships and solve intricate problems.

Sets of Numbers

We begin with the familiar sets of numbers, each denoted by a specific symbol and encompassing a particular range of values:

• Natural Numbers ($\mathbb{N}$): The set of positive integers, commencing from one and extending infinitely:

  $$\mathbb{N}=\{1,2,3,\dots \}$$

• Natural Numbers with Zero (${\mathbb{N}}_0$): The set of non-negative integers, including zero:

  $${\mathbb{N}}_0=\{0,1,2,3,\dots \}$$

• Integers ($\mathbb{Z}$): The set of all whole numbers, including both positive and negative numbers, and zero:

  $$\mathbb{Z}=\{\dots ,-3,-2,-1,0,1,2,3,\dots \}$$

• Real Numbers ($\mathbb{R}$): The set of all numbers that can be represented on a number line, including rational and irrational numbers.

• Positive Real Numbers (${\mathbb{R}}^{+}$): The set of real numbers strictly greater than zero.

• Non-negative Real Numbers (${\mathbb{R}}_{\ge 0}$ or ${\mathbb{R}}^0$): The set of real numbers greater than or equal to zero.

Logarithmic Notation

We will frequently encounter logarithmic functions. Let us clarify the notation we will adopt:

• Natural Logarithm (ln): The logarithm to the base $e$, where $e$ is Euler’s number, approximately 2.71828…

• Logarithm to Base 2 (log): Unless specified otherwise, ‘log’ will denote the logarithm to the base 2.

Set Operations and Cardinality

• Cardinality of a Set ($|A|$): For any set $A$, $|A|$ denotes its cardinality, which is the number of elements in $A$.

• Cartesian Product ($A\times B$): For two sets $A$ and $B$, their Cartesian product $A\times B$ is the set of all ordered pairs $(a,b)$ where $a$ is an element of $A$ and $b$ is an element of $B$:

  $$A\times B=\{(a,b)\mid a\in A,b\in B\}$$

• Power Set ($2^A$): The power set of a set $A$, denoted by $2^A$, is the set of all subsets of $A$:

  $$2^A=\{X\mid X\subseteq A\}$$

• k-element Subsets ($\left(\genfrac{}{}{0ex}{}{A}{k}\right)$): The notation $\left(\genfrac{}{}{0ex}{}{A}{k}\right)$ represents the set of all subsets of $A$ that contain exactly $k$ elements:

  $$\left(\genfrac{}{}{0ex}{}{A}{k}\right)=\{X\mid X\subseteq A,|X|=k\}$$

  The cardinality of $\left(\genfrac{}{}{0ex}{}{A}{k}\right)$ is given by the binomial coefficient $\left(\genfrac{}{}{0ex}{}{|A|}{k}\right)$.

Graph Theory Notations

We now introduce notations specific to graph theory, which will be extensively used in subsequent chapters.

• Graph ($G=(V,E)$): An undirected graph $G$ is defined as a pair of sets $(V,E)$, where $V$ is a finite, non-empty set of vertices (or nodes), and $E$ is a set of edges. In undirected graphs, edges are two-element subsets of $V$. Formally,

  $$E\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)=\{\{x,y\}\mid x,y\in V,x\ne y\}$$

• Directed Graph ($D=(V,A)$): A directed graph (or digraph) $D$ is also a pair $(V,A)$, where $V$ is again the vertex set, and $A$ is a set of directed edges, or arcs. Arcs are ordered pairs of vertices. Formally,

  $$A\subseteq V\times V$$

Minimization Notation

• Minimization Symbol ($\stackrel{!}{=}\text{min}$): The notation ”… $\stackrel{!}{=}\text{min}$ …” is used to indicate that the expression on the left-hand side is to be minimized. This will be frequently used in optimization problems related to graphs and other areas.

These fundamental notations provide the vocabulary for the discussions and problem-solving we will undertake in graph theory and probability. A firm grasp of these definitions is essential for navigating the more complex concepts to come.