Counts of vertices of each degree

PDF p. 35: Section 6.2 opening

Let $n\ge 1$ be an integer, $p\in [0,1]$, and $G(n,p)$ be the random simple graph on $[n]=\{1,\dots ,n\}$ in which distinct possible edges occur independently with probability $p$. For a vertex $v$, its degree $d(v)$ is the number of vertices adjacent to it. For each integer $k$, define $X_k={\sum }_{v=1}^n{\mathbf{1}}_{\{d(v)=k\}}$, $X_{\le k}={\sum }_{v=1}^n{\mathbf{1}}_{\{d(v)\le k\}}$, and $X_{\ge k}={\sum }_{v=1}^n{\mathbf{1}}_{\{d(v)\ge k\}}$. Here an indicator is one when its displayed event occurs and zero otherwise. Thus these variables count vertices of degree exactly $k$, at most $k$, and at least $k$, respectively.

Put $f_k=\mathbb{P}(\mathrm{Bin}(n-1,p)=k)$, where $\mathrm{Bin}(n-1,p)$ denotes the law of the sum of $n-1$ independent Bernoulli$(p)$ variables; each such variable is one with probability $p$ and zero with probability $1-p$. When $n=1$, the sum is zero.

Erdős–Rényi random graph and high probability

Adjacency, degrees, graph Laplacian, and spectral notation

Bernoulli random variables and binomial random variables as sums of independent Bernoulli trials

The indicator random variable of an event

Given: The data in Facts & Assumptions.

Goal: Establish that the displayed notation has the stated meaning.

1.1 By [F1], every graph outcome has a definite degree at each of its finitely many vertices. Each degree comparison therefore determines an event. By [F2], its indicator is defined and contributes one exactly for a vertex satisfying the comparison. The three finite sums consequently give the three stated counts on every outcome. [F1, F2]

2.1 Since $n-1$ is a nonnegative integer, [F3] defines the binomial law, including the empty-sum case. Its probability of the event that the sum equals $k$ is therefore a well-defined number $f_k$. Together with step 1.1 this establishes the notation. [given, F3, step 1.1] ∎

The degree-count and $f_k$ notation is attributed to the article, Section 6.2 opening. The justification above uses the stated mathematical suppliers.