# Symmetric–Reciprocal–Match Method for
Vector Network Analyzer Calibration

Ziad Hatab, Michael Ernst Gadringer, and Wolfgang Bösch
Graz University of Technology, Austria
{z.hatab; michael.gadringer<EMAIL_ADDRESS>Software implementation and
measurements are available online:
https://github.com/ZiadHatab/srm-calibration

###### Abstract

This paper proposes a new approach, the symmetric-reciprocal-match (SRM)
method, for calibrating vector network analyzers (VNAs). The method involves
using multiple symmetric one-port loads, a two-port reciprocal device, and a
matched load. The load standards consist of two-port symmetric one-port
devices, and at least three unique loads are used. However, the specific
impedances of the loads are not specified. The reciprocal device can be any
transmissive device, although a non-reciprocal device can also be used if only
the one-port error boxes are of interest. The matched load is fully defined
and can be asymmetric. We numerically demonstrated the proposed method’s
accuracy with synthetic data and with measurements of coaxial standards using
a commercial short-open-load-reciprocal (SOLR) calibration kit with
verification standards. An advantage of the proposed method is that only the
match standard is defined, whereas the remaining standards are partially
defined, either through symmetry or reciprocity.

###### Index Terms:

vector network analyzer, calibration, microwave measurement

##  I Introduction

The most commonly used method for calibrating vector network analyzers (VNAs)
is the short-open-load-thru (SOLT) method [1], which requires that all four
standards to be fully characterized or modeled. In the past, many VNAs used a
three-sampler architecture with three receivers.To account for the non-driving
port’s termination mismatches (switch terms), the VNA is modeled with the
well-known 12-term model [2]. This model forms the foundation of the SOLT
calibration.

Nowadays, modern VNAs use a full-reflectometry architecture that allows for
sampling all waves, thus directly measuring the switch terms of a VNA by
simply connecting a transmissive device between the ports [3]. This upgraded
architecture enabled the use of the simplified error box model of VNAs [4],
which has led to many new advanced calibration methods that surpass the
accuracy of SOLT [2]. Furthermore, even with the three-sampler VNA
architecture, it is possible to indirectly measure the switch terms of the VNA
using a set of reciprocal devices, which enable the application of the error
box model [5]. A well-known family of calibration methods based on the error
box model is the self-calibration methods [2], which do not require full
characterization of some of the standards. One of the most used self-
calibration methods nowadays is the short-open-load-reciprocal (SOLR) method
[6], which is the same as SOLT, but with any transmissive reciprocal device
instead of the thru standard. SOLR has proven useful in scenarios where a
direct connection is unavailable. However, the drawback of the SOLR method is
the requirement of the full definition of the short-open-load (SOL) standards,
which bounds the accuracy of SOLR to the SOL standards.

Other self-calibration methods include thru-reflect-line (TRL) and multiline
TRL [7, 8, 9, 10], which use line standards of different lengths, thru
connection, and symmetric unknown reflect standard. The thru standard in TRL
is fully defined. However, there is an implementation that eliminates the
requirement of the thru standard for any transmissive device with an
additional reflect standard [11]. While multiline TRL is a very accurate
calibration method, especially at millimeter-wave frequencies, it cannot be
applied at lower frequencies, as it results in using an extremely long line
standard. A common replacement for the multiline TRL method for on-wafer
application is the line-reflect-match (LRM), thru-match-reflect-reflect
(TMRR), and line-reflect-reflect-match (LRRM) methods [12, 13, 14, 15]. These
methods use unknown symmetric reflect standards and one known match standard.
However, these methods suffer from some impracticality, especially in defining
the line standard and shifting the reference plane, as opposed to the TRL
method. These methods can also be extended to account for crosstalk [16, 17,
18]. Additionally, due to the requirement of defining the thru/line standard,
such methods can be challenging to use in on-wafer measurement scenarios where
the probes are orthogonal or at an angle [19].

In this paper, we propose a new approach to self-calibration of VNAs using
multiple symmetric one-port loads, a two-port reciprocal device, and a matched
load. The multi-load one-port standards are two-port symmetric loads, and at
least three unique loads must be used. The values of the loads themselves are
not specified. For example, a short, an open, and any finite impedance load
would be suitable. The reciprocal device can be any transmissive device. In
fact, if we only care about the one-port error boxes of the VNA, then the two-
port device can be any transmissive device, even if it is non-reciprocal.
Lastly, the matched load is fully defined but can be asymmetric. The match
standard can be implemented as part of the symmetric one-port loads to reduce
the number of standards. We refer to this calibration method as the symmetric-
reciprocal-match (SRM) method. All standards are generally partially defined,
except for the match standard. We demonstrate the method using synthetic data
of coplanar waveguide (CPW) structures, as well as measurements with
commercial SOLR coaxial standards.

A significant benefit of the proposed approach is that all the standards are
partially defined, except for the match standard. This is in contrast to
LRRM/LRM/TMRR approaches, which necessitate fully defined thru/line standards.
As a result, such techniques can be challenging in the case of on-wafer setups
where the probes are positioned at an orthogonal angle. Equivalently, the SOLR
calibration addresses the problem of the thru/line connection by using any
two-port reciprocal device instead but necessitates the specification of the
remaining standards. In brief, our SRM technique combines the benefits of
LRRM/LRM/TMRR techniques in utilizing undefined symmetric standards, as well
as the SOLR technique in utilizing a two-port reciprocal device. This revised
definition of the standards enables accurate calibration by limiting the
definition to solely the match standard.

The remainder of this article is structured as follows. In Section Section II,
we discuss our SRM method when using a thru standard instead of any reciprocal
device, highlighting the method’s fundamentals. Afterward, in Section III, we
extend the mathematics of the calibration to consider any transmissive
reciprocal device. Section IV introduces a special case of the SRM method when
considering a fixed distance between measuring ports, which is often the case
in on-wafer applications. Lastly, in Section V, we provide numerical analysis
using synthetic data and experimental measurements using commercial coaxial
$2.92\,\mathrm{mm}$ calibration and verification standards and conclude in
Section VI.

##  II The Simple Case Using a Thru Standard

In the general case of SRM calibration, no thru standard is required. Any
transmissive reciprocal device would suffice. If only the one-port error boxes
are desired, any transmissive device would be acceptable. However, the
derivation of the generalized SRM calibration is based on creating an
artificial thru standard via mathematical reformulation and additional one-
port measurements. The handling of the artificial thru standard is explained
in more detail in Section III. In this section, we assume a fully defined thru
standard to derive the calibration workflow and extend it to the general case
in Section III.

To start the derivation, we use the error box model of a two-port VNA, as
illustrated in Fig. 1. This model is expressed in T-parameters as follows:

$\boldsymbol{M}_{\mathrm{stand}}=\underbrace{k_{a}k_{b}}_{k}\underbrace{\left[\begin{matrix}a_{11}&a_{12}\\\\[5.0pt]
\
a_{21}&1\end{matrix}\right]}_{\boldsymbol{A}}\boldsymbol{T}_{\mathrm{stand}}\underbrace{\left[\begin{matrix}b_{11}&b_{12}\\\\[5.0pt]
b_{21}&1\end{matrix}\right]}_{\boldsymbol{B}},$ (1)

where $\boldsymbol{M}_{\mathrm{stand}}$ and $\boldsymbol{T}_{\mathrm{stand}}$
represent the measured and actual T-parameters of the standard, respectively.
The matrices $\boldsymbol{A}$ and $\boldsymbol{B}$ are the one-port error
boxes containing the first six error terms, and $k$ is the seventh error term
that describes the transmission error between the ports.

Figure 1: Two-port VNA error box model. Matrices are given as T-parameters.

For a thru standard, the measured T-parameters are provided as follows:

$\boldsymbol{M}_{\mathrm{thru}}=k\boldsymbol{A}\boldsymbol{B}.$ (2)

In the next step, we will focus on measuring one-port standards. For the SRM
method, we require at least three symmetric two-port standards made from one-
port devices, and at least three of them should exhibit unique electrical
responses. Examples of such standards include short, open, and impedance. It
is not necessary to know the exact response of the standards themselves. Fig.
2 provides an illustration of the error box for one-port measurements.

Figure 2: Two-port VNA error box model that illustrates the measurement of
one-port standards. All matrices are provided as T-parameters. The index $i$
indicates the measured standard, where $i=1,2,\ldots,M$, with $M\geq 3$.

The measured input reflection coefficient seen from each port is given as
follows:

$\Gamma_{a}^{(i)}=\frac{a_{11}\rho^{(i)}+a_{12}}{a_{21}\rho^{(i)}+1};\quad\Gamma_{b}^{(i)}=\frac{b_{11}\rho^{(i)}-b_{21}}{1-b_{12}\rho^{(i)}},$
(3)

where $\Gamma_{a}^{(i)}$ and $\Gamma_{b}^{(i)}$ are the $i$th measured
reflection coefficients from the left and right ports, respectively. The
actual response of the standard, which is assumed to be unknown, is denoted by
$\rho^{(i)}$.

The expression for the input reflection coefficient, as given in (3), is in
the form of a Möbius transformation (also known as a bilinear transformation)
[20, Chapter 3]. One important property of the Möbius transformation is that
it can be described by an equivalent $2\times 2$ matrix notation. For
instance, (4) provides a general Möbius transformation with coefficients
$a,b,c,d\in\mathbb{C}$, along with its corresponding $2\times 2$ matrix
representation.

$f(z)=\frac{az+b}{cz+d}\quad\longleftrightarrow\quad[f]=\begin{bmatrix}a&b\\\
c&d\end{bmatrix}$ (4)

In (4), we use brackets $[\cdot]$ to describe matrices associated with a
Möbius transformation. The transformation coefficients are only unique up to a
complex scalar multiple. This property of the Möbius transform can be easily
shown by multiplying the numerator and denominator with a non-zero complex
scalar. In terms of matrix notation, scaling the matrix with a complex scalar
still represents the same Möbius transformation. Therefore,

$\quad[f]\equiv\kappa[f],\quad\kappa\neq 0$ (5)

The matrix representation of the Möbius transformation possesses an elegant
property in its ability to describe composite Möbius transformations. In
essence, when we compose one Möbius transformation with another, we obtain a
new Möbius transformation with updated coefficients. This property can be
expressed in matrix notation by computing the matrix product of the individual
Möbius transformations. To illustrate this concept, we provide an example of
the composition of two Möbius transformations $f_{1}(z)$ and $f_{2}(z)$, which
are defined as follows:

$\displaystyle f_{1}(z)$
$\displaystyle=\frac{a_{1}z+b_{1}}{c_{1}z+d_{1}}\quad\longleftrightarrow\quad[f_{1}]=\begin{bmatrix}a_{1}&b_{1}\\\
c_{1}&d_{1}\end{bmatrix}$ (6a) $\displaystyle f_{2}(z)$
$\displaystyle=\frac{a_{2}z+b_{2}}{c_{2}z+d_{2}}\quad\longleftrightarrow\quad[f_{2}]=\begin{bmatrix}a_{2}&b_{2}\\\
c_{2}&d_{2}\end{bmatrix}$ (6b)

The composite transformation is given as follows:

$\displaystyle g(z)=(f_{1}\circ f_{2})(z)$
$\displaystyle=\frac{a_{1}f_{2}(z)+b_{1}}{c_{1}f_{2}(z)+d_{1}}$ (7)
$\displaystyle=\frac{(a_{1}a_{2}+b_{1}c_{2})z+a_{1}b_{2}+b_{1}d_{2}}{(a_{2}c_{1}+c_{2}d_{1})z+b_{2}c_{1}+d_{1}d_{2}}$

Therefore, the corresponding matrix equivalent of the composite Möbius
transformation $g(z)$ is given as follows:

$[g]=\begin{bmatrix}a_{1}a_{2}+b_{1}c_{2}&a_{1}b_{2}+b_{1}d_{2}\\\\[5.0pt]
a_{2}c_{1}+c_{2}d_{1}&b_{2}c_{1}+d_{1}d_{2}\end{bmatrix}=[f_{1}][f_{2}]$ (8)

which is the same as multiplying the matrices $[f_{1}]$ and $[f_{2}]$.

Using matrix notation for the Möbius transformation, we can describe the input
reflection coefficient measured from the left port as follows:

$\Gamma_{a}^{(i)}=\frac{a_{11}\rho^{(i)}+a_{12}}{a_{21}\rho^{(i)}+1}\longleftrightarrow[\Gamma_{a}^{(i)}]=\underbrace{\begin{bmatrix}a_{11}&a_{12}\\\\[5.0pt]
a_{21}&1\end{bmatrix}}_{\boldsymbol{A}}$ (9)

To address the error box on the right side, we perform a similar process as
before, but instead of using the measured reflection coefficient, we
reformulate in terms of the reflection coefficient $\rho^{(i)}$ as a function
of the measured reflection coefficient $\Gamma_{b}^{(i)}$, which is given as
follows:

$\rho^{(i)}=\frac{\Gamma_{b}^{(i)}+b_{21}}{b_{12}\Gamma_{b}^{(i)}+b_{11}}\longleftrightarrow[\rho^{(i)}]=\underbrace{\begin{bmatrix}1&b_{21}\\\\[5.0pt]
b_{12}&b_{11}\end{bmatrix}}_{\boldsymbol{P}\boldsymbol{B}\boldsymbol{P}}$ (10)

where $\boldsymbol{P}$ is a $2\times 2$ permutation matrix defined as

$\boldsymbol{P}=\boldsymbol{P}^{T}=\boldsymbol{P}^{-1}=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}.$ (11)

By composing (10) with (9), we obtain a new Möbius transformation that
describes the input reflection coefficient from the left port using
measurements of the right port. This relationship can be written as follows:

$\Gamma_{a}^{(i)}=\frac{h_{11}\Gamma_{b}^{(i)}+h_{12}}{h_{21}\Gamma_{b}^{(i)}+h_{22}}\longleftrightarrow[\Gamma_{a}^{(i)}]=\boldsymbol{H}=\begin{bmatrix}h_{11}&h_{12}\\\
h_{21}&h_{22}\end{bmatrix}$ (12)

Here, we use the variable $\boldsymbol{H}$ to describe the Möbius
transformation in (12) and differentiate it from the Möbius transformation in
(9) to avoid confusion. It is important to note that both transformations are
different, as they have distinct input parameters.

Due to the composite property of Möbius transformations, the coefficients of
the transformation can be expressed as follows:

$\boldsymbol{H}=\nu\boldsymbol{A}\boldsymbol{P}\boldsymbol{B}\boldsymbol{P},\qquad\forall\,\nu\neq
0.$ (13)

It is important to note that the constant $\nu$ is included because the
coefficients of a Möbius transformation can only be defined up to a non-zero
complex-valued scalar constant.

By solving for the coefficients $h_{ij}$, we can determine (13). This equation
is later used for establishing the calibration procedure by combining it with
the thru standard. Since the coefficients $h_{ij}$ are defined by the Möbius
transformation in (12), which is based on the measurements of the symmetric
one-port standards, we can rewrite the Möbius transformation as a linear
system of equations in terms of its coefficients. Assuming that $M\geq 3$ one-
port standards were measured, the coefficients $h_{ij}$ can be described as
follows:

$\underbrace{\left[\begin{matrix}-\Gamma_{b}^{(1)}&-1&\Gamma_{b}^{(1)}\Gamma_{a}^{(1)}&\Gamma_{a}^{(1)}\\\
-\Gamma_{b}^{(2)}&-1&\Gamma_{b}^{(2)}\Gamma_{a}^{(2)}&\Gamma_{a}^{(2)}\\\
\vdots&\vdots&\vdots&\vdots\\\
-\Gamma_{b}^{(M)}&-1&\Gamma_{b}^{(M)}\Gamma_{a}^{(M)}&\Gamma_{a}^{(M)}\end{matrix}\right]}_{\boldsymbol{G}}\underbrace{\left[\begin{matrix}h_{11}\\\
h_{12}\\\ h_{21}\\\
h_{22}\end{matrix}\right]}_{\boldsymbol{h}}=\boldsymbol{0}$ (14)

The solution for the vector $\boldsymbol{h}$ is found in the nullspace of
$\boldsymbol{G}$, as the system matrix $\boldsymbol{G}$ contains at least one
nullspace due to the equality to zero in (14). We may have more than one
nullspace, but only if $\mathrm{rank}(\boldsymbol{G})<3$, which can only
happen if we do not use at least three unique one-port standards.

While the nullspace $\boldsymbol{G}$ satisfies the solution of (14), we can
optimally estimate the nullspace of $\boldsymbol{G}$ in the presence of
disturbance by computing its singular value decomposition (SVD) and using the
right singular vector that corresponds to the smallest singular value [21]. As
$\boldsymbol{G}$ is of dimension 4 (i.e., number of columns), it has four
singular values and vectors. We decompose the matrix $\boldsymbol{G}$ using
SVD as follows:

$\boldsymbol{G}=\sum_{i=1}^{4}s_{i}\boldsymbol{u}_{i}\boldsymbol{v}_{i}^{H}$
(15)

where $s_{i}$ is the $i$th singular value, while $\boldsymbol{u}_{i}$ and
$\boldsymbol{v}_{i}$ are the $i$th left and right singular vectors,
respectively. The conventional ordering of the singular values is in
decreasing order. Therefore, the smallest singular value is $s_{4}$. Hence,
the solution for $\boldsymbol{h}$ is given by the fourth right singular vector
as follows:

$\boldsymbol{h}=\boldsymbol{v}_{4}$ (16)

Now that we have solved for $\boldsymbol{h}$, and hence $\boldsymbol{H}$ in
(13), we can combine the measurements of the thru standards with the results
of $\boldsymbol{H}$ to form an eigenvalue problem regarding the error box
coefficients. The combined result for the left error box is defined as
follows:

$\boldsymbol{M}_{\mathrm{thru}}\boldsymbol{P}\boldsymbol{H}^{-1}=\frac{k}{\nu}\boldsymbol{A}\boldsymbol{P}\boldsymbol{A}^{-1}$
(17)

Although (17) is not strictly in the canonical form for an eigenvalue
decomposition, as the middle matrix is not diagonal, it can still be
decomposed because the middle matrix is a constant permutation matrix. If we
apply the eigendecomposition to (17), we obtain the following decomposition:

$\boldsymbol{M}_{\mathrm{thru}}\boldsymbol{P}\boldsymbol{H}^{-1}=\frac{k}{\nu}\boldsymbol{A}\boldsymbol{P}\boldsymbol{A}^{-1}=\boldsymbol{W}_{a}\boldsymbol{\Lambda}\boldsymbol{W}_{a}^{-1},$
(18)

where the matrix $\boldsymbol{W}_{a}$ corresponds to the eigenvectors, and the
matrix $\boldsymbol{\Lambda}$ corresponds to the eigenvalues. Both are
calculated as follows:

$\displaystyle\boldsymbol{W}_{a}$
$\displaystyle=\begin{bmatrix}w_{11}^{(a)}&w_{12}^{(a)}\\\\[5.0pt]
w_{21}^{(a)}&w_{22}^{(a)}\end{bmatrix}=\begin{bmatrix}\frac{a_{11}+a_{12}}{a_{21}+1}&\frac{-a_{11}+a_{12}}{-a_{21}+1}\\\\[5.0pt]
1&1\end{bmatrix}$ (19a) $\displaystyle\boldsymbol{\Lambda}$
$\displaystyle=\begin{bmatrix}\lambda_{1}&0\\\\[5.0pt]
0&\lambda_{2}\end{bmatrix}=\begin{bmatrix}\frac{k}{\nu}&0\\\\[5.0pt]
0&-\frac{k}{\nu}\end{bmatrix}$ (19b)

Generally, the order of the eigenvectors and eigenvalues is not unique. To
ensure the correct order, we need to know the value of $k/\nu$. However, this
term is still unknown at this stage. After solving for the error terms using
both possible solutions, the sorting is done through trial and error. For
instance, once the error terms have been solved, we could use one of the one-
port standards as a metric to determine the correct order.

We can solve the eigenvalue problem for matrix $\boldsymbol{B}$ by reversing
the multiplication order of the matrices in (17). This gives us the following
equation:

$\left(\boldsymbol{P}\boldsymbol{H}^{-1}\boldsymbol{M}_{\mathrm{thru}}\right)^{T}=\frac{k}{\nu}\boldsymbol{B}^{T}\boldsymbol{P}\boldsymbol{B}^{-T}=\boldsymbol{W}_{b}\boldsymbol{\Lambda}\boldsymbol{W}_{b}^{-1}$
(20)

Using the transpose operation is optional, but it allows us to derive the
eigenvectors in a similar order as with the left error box. As a result, the
eigenvectors and eigenvalues are given as follows:

$\displaystyle\boldsymbol{W}_{b}$
$\displaystyle=\begin{bmatrix}w_{11}^{(b)}&w_{12}^{(b)}\\\\[5.0pt]
w_{21}^{(b)}&w_{22}^{(b)}\end{bmatrix}=\begin{bmatrix}\frac{b_{11}+b_{21}}{b_{12}+1}&\frac{-b_{11}+b_{21}}{-b_{12}+1}\\\\[5.0pt]
1&1\end{bmatrix}$ (21a) $\displaystyle\boldsymbol{\Lambda}$
$\displaystyle=\begin{bmatrix}\lambda_{1}&0\\\\[5.0pt]
0&\lambda_{2}\end{bmatrix}=\begin{bmatrix}\frac{k}{\nu}&0\\\\[5.0pt]
0&-\frac{k}{\nu}\end{bmatrix}$ (21b)

Finally, we need an additional equation for each port to calculate the error
terms from each error box. This equation comes from the match standard, which
defines the reference impedance of the calibration. In general, the match
standard does not have to be the same at each port. However, since we are most
likely to use an impedance standard as part of the symmetric one-port devices,
it makes sense to reuse the match standards. For each port, the reflection
coefficient of a match standard is given as follows:

$\rho_{a}^{(m)}=\frac{Z_{a}^{(m)}-Z_{a}^{(ref)}}{Z_{a}^{(m)}+Z_{a}^{(ref)}};\quad\rho_{b}^{(m)}=\frac{Z_{b}^{(m)}-Z_{b}^{(ref)}}{Z_{b}^{(m)}+Z_{b}^{(ref)}}$
(22)

where $Z_{a}^{(m)}$ and $Z_{b}^{(m)}$ represent the complex impedance
definition of the match standard from each port. The user sets the values of
$Z_{a}^{(ref)}$ and $Z_{b}^{(ref)}$ to specify the reference impedance, for
example, $50\,\Omega$.

By utilizing knowledge of the match standard and the equation that describes
the input reflection coefficient, as given in (3), we can combine this result
with the eigenvectors to form a linear system of equations for each port. The
following is for the left port:

$\left[\begin{matrix}-1&-1&w_{11}^{(a)}&w_{11}^{(a)}\\\
1&-1&-w_{12}^{(a)}&w_{12}^{(a)}\\\
-\rho_{a}^{(m)}&-1&\Gamma_{a}^{(m)}\rho_{a}^{(m)}&\Gamma_{a}^{(m)}\end{matrix}\right]\left[\begin{matrix}a_{11}\\\
a_{12}\\\ a_{21}\\\ 1\end{matrix}\right]=\boldsymbol{0}$ (23)

The system of equations for the right port can be obtained in a similar way,
resulting in the following system of equations:

$\left[\begin{matrix}-1&-1&w_{11}^{(b)}&w_{11}^{(b)}\\\
1&-1&-w_{12}^{(b)}&w_{12}^{(b)}\\\
-\rho_{b}^{(m)}&1&-\Gamma_{b}^{(m)}\rho_{b}^{(m)}&\Gamma_{b}^{(m)}\end{matrix}\right]\left[\begin{matrix}b_{11}\\\
b_{21}\\\ b_{12}\\\ 1\end{matrix}\right]=\boldsymbol{0}$ (24)

The error terms are solved by finding the nullspace of the system matrix.
However, since the nullspace is only unique up to a scalar factor, we
normalize it by the last element to make it equal to 1. The system matrix can
be extended by an arbitrary number of defined impedance standards to improve
the solution. It is important to note that we obtain two systems of equations
for each port since the order of the eigenvectors is unknown. As a result, we
solve for both possible orderings and choose the answer that results in a
calibrated measurement closest to a known estimate, like the usage of a
reflect standard.

An interesting observation to note is the structure of (23) and (24), where
the first two rows in the system matrix obtained from the eigenvectors
resemble measurements of ideal short and open standards. In general, the
expression of (23) and (24) are identical to that of a one-port SOL
calibration when assuming ideal short and open standards. Thus, we were able
to replicate measurements of ideal open and short standards by using symmetric
undefined one-port devices and a thru standard.

The final error term that needs to be solved is the transmission error term
$k$. Since we are working with a thru standard, we can directly extract $k$ by
multiplying the inverse of the one-port error boxes by the measurements of the
thru standard. In Section III, we introduce a different approach for computing
$k$ using any transmissive reciprocal standard, as done in SOLR calibration
[6].

##  III Generalization without a Thru Standard

In the previous section, we explained how to calculate the error terms using
at least three symmetric one-port standards, a thru standard, and a match
standard. The thru standard can cause difficulties, as it is not always
possible to physically achieve such a standard.

The equations derived in the previous section can be used without changes if
we obtain an equation similar to that of a thru standard, as given in (2).
Therefore, this section aims to derive what we will refer to as a virtual thru
standard by using additional one-port standards.

The necessary standards, excluding the match standard, for the generalized SRM
calibration are shown in Fig. 3. The network standard is an unknown
transmissive two-port standard. This standard does not need to be reciprocal
for deriving only one-port error terms. The additional network-load standard
uses the same two-port network standard and the same one-port symmetric
standards. As mentioned in the previous section, we require at least $M\geq 3$
one-port symmetric standards. Hence, we also need a corresponding network-load
standard for every symmetric one-port load standard. Generally, we only need
the network-load standard from one port, which could be from either ports.

Figure 3: Two-port VNA error box model illustrating the standards used to
create a virtual thru standard. All matrices are provided as T-parameters. The
index $i$ indicates the measured standard, where $i=1,2,\ldots,M$, with $M\geq
3$.

Based on the network standard, the following measurement is available:

$\boldsymbol{M}_{\mathrm{net}}=k\boldsymbol{A}\underbrace{\begin{bmatrix}\frac{-\det\left(\boldsymbol{S}\right)}{S_{21}}&\frac{S_{11}}{S_{21}}\\\\[5.0pt]
\frac{-S_{22}}{S_{21}}&\frac{1}{S_{21}}\end{bmatrix}}_{\boldsymbol{N}}\boldsymbol{B}$
(25)

where $\det\left(\boldsymbol{S}\right)=S_{11}S_{22}-S_{12}S_{21}$.

A similar expression to the matrix $\boldsymbol{H}$ in (13) can be obtained
using the network-load standard from the left port and the load standards from
the right ports. This results in an expression similar to (13), but with
$\boldsymbol{A}$ replaced by $\boldsymbol{A}\boldsymbol{N}$ and with an
adjustment to the scaling factor. The scaling factor is unknown and does not
need to be equal to the constant in (13). We can also achieve the same result
by considering the network-load standards from the right port and symmetric
load standards from the left port. As a result, combining the network-load
standards with the symmetric load standards, we obtain the following result
for each port depending on where the network-load was implemented:

$\displaystyle\boldsymbol{F}_{a}$
$\displaystyle=\eta\boldsymbol{A}\boldsymbol{N}\boldsymbol{P}\boldsymbol{B}\boldsymbol{P},\qquad\forall\,\eta\neq
0,$ (26a) $\displaystyle\boldsymbol{F}_{b}$
$\displaystyle=\zeta\boldsymbol{A}\boldsymbol{P}\boldsymbol{N}\boldsymbol{B}\boldsymbol{P},\qquad\forall\,\zeta\neq
0$ (26b)

Using the results of $\boldsymbol{M}_{\mathrm{net}}$, $\boldsymbol{H}$, and
$\boldsymbol{F}$ from (25), (13), and (26), respectively, we can create a
virtual thru standard by combining them in the following manner:

$\displaystyle\boldsymbol{M}_{\mathrm{thru}}$
$\displaystyle=\boldsymbol{H}\boldsymbol{F}_{a}^{-1}\boldsymbol{M}_{\mathrm{net}}=\frac{\nu}{\eta}k\boldsymbol{A}\boldsymbol{B}$
(27a) $\displaystyle\boldsymbol{M}_{\mathrm{thru}}$
$\displaystyle=\boldsymbol{M}_{\mathrm{net}}\boldsymbol{P}\boldsymbol{F}_{b}^{-1}\boldsymbol{H}\boldsymbol{P}=\frac{\nu}{\zeta}k\boldsymbol{A}\boldsymbol{B}$
(27b)

Therefore, we can obtain a thru measurement without measuring a thru standard
using the results of (27). We simply use the results from the previous section
and substitute (27) in place of the thru measurements. The only difference we
obtain are the eigenvalues, which result in $\pm k/\eta$ or $\pm k/\zeta$.
However, this change does not affect anything, as $\nu$, $\eta$, and $\zeta$
are the result of the normalization choice of the Möbius transformation and
are assumed regardless unknown.

To complete the two-port calibration, we must solve for the transmission error
term $k$. We can use the same method as in SOLR calibration [6] by calculating
$k$ through the determinate of the one-port corrected measurement of the
network standard, given that it is reciprocal (i.e., $S_{21}=S_{12}$).
Assuming the network standard is indeed reciprocal, we can solve for $k$ by
first applying the one-port error boxes to the measurement of the network
standard as follows:

$\boldsymbol{A}^{-1}\boldsymbol{M}_{\mathrm{net}}\boldsymbol{B}^{-1}=k\boldsymbol{N}$
(28)

Afterward, by taking the determinant from both sides, we obtain the following:

$\det\left(\boldsymbol{A}^{-1}\boldsymbol{M}_{\mathrm{net}}\boldsymbol{B}^{-1}\right)=k^{2}\underbrace{\det\left(\boldsymbol{N}\right)}_{=1}$
(29)

Hence, $k$ is solved as follows:

$k=\pm\sqrt{\det\left(\boldsymbol{A}^{-1}\boldsymbol{M}_{\mathrm{recip}}\boldsymbol{B}^{-1}\right)}$
(30)

where the selection of the appropriate sign is determined by comparing it to a
known estimate of the network.

##  IV Special Layout for On-wafer Application

The presented SRM calibration method applies to any measurement setup where
the standards can be implemented. However, a particular case for on-wafer
calibration arises when considering that the distance between the probes must
remain constant. Semi-automatic probe station users often request this
requirement, where only the chuck platform is motorized. For these measurement
setups, the standards must be implemented with a constant distance between the
probes to perform the calibration automatically.

Considering the standards depicted in Fig. 3, we can see that the right probe
would need to be moved to the right to measure the network-load standard. The
network standard already dictates the distance between the probes, and
cascading another standard would naturally increase the spacing, requiring
probe movement.

In planar circuit calibration, as in on-wafer measurement setups, we can
advantageously apply the property of the network standard to represent any
symmetric transmissive network. Hence, we can split the network into two
cascaded flipped asymmetric networks. With this notation, we can use half of
the network to define the network-load standard. An illustration of coplanar
waveguide (CPW) standards is depicted in Fig. 4.

Figure 4: Illustration of CPW structures implementing the proposed half-
network approach of SRM calibration. The match standard is optional if the
symmetric impedance standard is reused as the match standard.

For any symmetric network (i.e., $S_{ij}=S_{ji}$), we can divide its
T-parameters into two cascaded networks that are identical and flipped [22].
This network can be expressed as follows:

$\boldsymbol{N}=\boldsymbol{R}\boldsymbol{P}\boldsymbol{R}^{-1}\boldsymbol{P}$
(31)

where $\boldsymbol{P}$ represents the permutation matrix, as defined in (11),
and $\boldsymbol{R}$ is the half-asymmetric part of the network standard.

By substituting the new definition of the network standard from (31) into the
expressions (25), (13), and (26), we arrive at the following expressions:

$\displaystyle\boldsymbol{M}_{\mathrm{net}}$
$\displaystyle=k\boldsymbol{A}\boldsymbol{R}\boldsymbol{P}\boldsymbol{R}^{-1}\boldsymbol{P}\boldsymbol{B}$
(32a) $\displaystyle\boldsymbol{F}_{a}$
$\displaystyle=\eta\boldsymbol{A}\boldsymbol{R}\boldsymbol{P}\boldsymbol{B}\boldsymbol{P},\qquad\forall\,\eta\neq
0$ (32b) $\displaystyle\boldsymbol{F}_{b}$
$\displaystyle=\zeta\boldsymbol{A}\boldsymbol{R}^{-1}\boldsymbol{P}\boldsymbol{B}\boldsymbol{P},\qquad\forall\,\zeta\neq
0.$ (32c)

Therefore, by combining the results of the above expressions with
$\boldsymbol{H}$ from (13), we create a virtual thru standard as follows:

$\displaystyle\boldsymbol{M}_{\mathrm{thru}}$
$\displaystyle=\boldsymbol{H}\boldsymbol{F}_{a}^{-1}\boldsymbol{M}_{\mathrm{net}}\boldsymbol{P}\boldsymbol{H}^{-1}\boldsymbol{F}_{a}\boldsymbol{P}=k\boldsymbol{A}\boldsymbol{B},$
(33a) $\displaystyle\boldsymbol{M}_{\mathrm{thru}}$
$\displaystyle=\boldsymbol{F}_{b}\boldsymbol{H}^{-1}\boldsymbol{M}_{\mathrm{net}}\boldsymbol{P}\boldsymbol{F}_{b}^{-1}\boldsymbol{H}\boldsymbol{P}=k\boldsymbol{A}\boldsymbol{B}.$
(33b)

With the virtual thru standard being established, the remaining calibration
process follows the same procedure discussed in the previous section.

One elegant application using half-network standards is the use of angled
calibration. This method involves positioning the probes at an angle rather
than facing each other. Traditional calibration methods such as TRL, LRM, and
LRRM do not allow this type of calibration, whereas SOLR is often used for
such scenarios [19]. Fig. 5 illustrates a potential implementation of the
network and half-network standards at a $90^{\circ}$ angle.

Figure 5: Illustration of CPW structures implementing the half network-load
standards in an orthogonal orientation. The symmetric one-port standards are
not shown, as they do not pose any mechanical challenge in orthogonal
orientation.

##  V Experiments

This section discusses two experiments. The first experiment involves
numerical analysis using synthetic data to demonstrate different aspects of
SRM calibration. It includes a demonstration of the SRM method using network-
load standards with a full-network (as discussed in Section III) and with
half-network (as discussed in Section IV). In the second experiment, we
present measurements using SOLR coaxial standards and compare the SRM method
against SOLR calibration using characterized verification standards with
defined uncertainties.

###  V-A Numerical Analysis

The procedure for the numerical analysis involves creating synthetic data of
CPW standards using the model developed in [23, 24, 25]. To emulate an on-
wafer setup accurately, we utilize error boxes from an actual on-wafer setup
that was extracted using multiline TRL calibration on an impedance substrate
standard (ISS). Further details on the measurement setup can be found in [10],
where the accuracy of the CPW model was tested against the measurements. The
measurement data set is available via [26]. In this numerical setting, the aim
is to generate SRM standards based on the CPW model and embed them within the
error boxes of the actual VNA setup. A block diagram summarizing this
numerical experiment is depicted in Fig. 6.

Figure 6: Block diagram illustration of the numerical simulation concept to
generate realistic synthetic data.

Regarding the geometric parameters of the CPW structure used for simulation,
we employed the following dimensions, which are based on the actual measured
ISS: signal width of $49.1\,\mu\mathrm{m}$, ground width of
$273.3\,\mu\mathrm{m}$, conductor spacing of $25.5\,\mu\mathrm{m}$, and
conductor thickness of $4.9\,\mu\mathrm{m}$. The substrate is made of lossless
Alumina with a dielectric constant of $9.9$. The conductor is made of gold
with relative conductivity to copper of $70\%$, where the conductivity of
copper is $58\,\mathrm{MS/m}$.

For the SRM standards, we implemented match, short, and open standards as non-
ideal standards, as shown in Fig. 7. To create the network-load standards, we
used a $4\,\mathrm{mm}$ CPW line as the reciprocal standard, which is combined
with the non-ideal match, short, and open standards. Additionally, as
discussed in Section IV, we created half network-load standards using half of
the reciprocal standard, i.e., a $2\,\mathrm{mm}$ CPW line. The CPW standards
are similar to the illustration in Fig. 4 for the half network-load standards,
except that the match is reused from the symmetric standards.

We used $Z^{ref}=50\,\Omega$ as the reference impedance for calibration for
both ports. In the SRM calibration procedure, all standards are not specified
except for the match that enables the definition of the reference impedance.

(a)  (b)

(c)

Figure 7: Models used to simulate non-ideal load standards (a) $50\,\Omega$
match standard with $L_{0}=5\,\mathrm{pH},C_{0}=0.5\,\mathrm{fF}$, (b) short
standard with $L_{0}=10\,\mathrm{pH},C_{0}=0.5\,\mathrm{fF}$, and open
standard with $C_{0}=10\,\mathrm{fF},L_{0}=0.5\,\mathrm{pH}$. All standards
are offset by a $200\,\mu\mathrm{m}$ CPW line segment.

To verify the accuracy of the calibration, we included a stepped impedance
line as DUT, which uses the same CPW structure with the only exception of
signal width equal to $15\,\mu\mathrm{m}$. The data has been processed using
Python with the help of the package scikit-rf [27]. Fig. 8 shows the DUT
before and after embedding in the error boxes.

Figure 8: DUT S-parameter response before and after embedding within the error
boxes.

To verify the numerical accuracy of the calibration, we define an error metric
as the magnitude of the error vector of the calibrated response to the actual
response given by

$\text{Error}_{ij}\
(\mathrm{dB})=20\,\mathrm{log}_{10}\left|S_{ij}^{\mathrm{cal}}-S_{ij}^{\mathrm{true}}\right|$
(34)

where $S_{ij}^{\mathrm{cal}}$ represents the calibrated value and
$S_{ij}^{\mathrm{true}}$ is the corresponding true value.

Applying the SRM method using both full-network and half-network variants, we
observe in Fig. 9 that both methods yield errors approaching zero, constrained
only by the numerical precision of the software.

Figure 9: The error of the calibrated DUT using the SRM method, once with a
full-network approach and secondly with a half-network approach.

###  V-B Coaxial Measurements

The measurement involves comparing the proposed SRM method with a SOLR
calibration using a commercial SOLR coaxial calibration kit with a
$2.92\,\mathrm{mm}$ interface [28]. The calibration results are compared to
fully characterized verification standards with defined uncertainty bounds.
The VNA used for the measurement is a ZVA from Rohde&Schwarz (R&S), and the
used calibration kit is the ZN-Z229 $2.92\,\mathrm{mm}$ calibration kit from
R&S. The standards used from the kit are short, open, and match standards with
female interfaces, along with two adapters, one female-female and one female-
male of equal length. This data is used to conduct the SOLR calibration. The
adapter standard is assumed to be unknown during the SOLR calibration process.

For the implementation of SRM standards, the symmetrical standards are
directly measured by connecting the three one-port devices at both ports:
short, open, and match. The female-female adapter is used to represent the
reciprocal network. For the network-load standard, the symmetrical one-port
devices are connected to the female-male adapter and measured at the left
port. In all steps, the standards are assumed unknown, except for the match
standard, which is only defined in the final step of the calibration via (23)
and (24). An example that illustrates the measurement of the standards is
shown in Fig. 10.

(a)  (b)  (c)

Figure 10: Example photos of measured coaxial standards. (a) load standard,
(b) adapter (network), and (c) load connected with an adapter (network-load).

The verification kit utilized for the comparison is the ZV-Z429
$2.92\,\mathrm{mm}$ verification kit from R&S. The kit contains a mismatch
standard and an offset short standard with female interfaces. These
verification standards have been previously characterized by the manufacturer,
and their S-parameters are provided with uncertainty bounds.

The results from calibrating the mismatch and offset short verification kit
using both SOLR and SRM calibration methods are depicted in Fig. 11. The plots
reveal that both calibration methods produced similar outcomes, with errors
relative to the reference data of the verification kit remaining below
$-30\,\mathrm{dB}$. To facilitate visual comparison, we opted to plot the
group delay instead of the phase. In both, the SOLR and SRM calibration, the
group delay overlaps with the reference data for both mismatch and offset
short. However, we observe a small discrepancy in the magnitude response of
the offset short standard after $15\,\mathrm{GHz}$, where ripples can be
observed. Nevertheless, this falls within the uncertainty bounds of the
magnitude response of the offset short.

Figure 11: Comparison of calibrated mismatch and offset short verification
kits using SOLR and SRM methods. The uncertainty bounds are of the reference
measurement and reported as $95\%$ expanded uncertainty.

A possible cause for the variation in the magnitude of the calibrated offset
short with the SRM method is likely due to the pin gap of the connectors, as
the SRM method involves more measurements using the network-load standards. We
have summarized the pin gap after mating for the different standards in Table
I. The table shows that the adapter standard used to create the network-load
standard has the most significant pin gap distance (i.e.,
$54.61\,\mu\mathrm{m}$). This ripple is also noticeable when analyzing the
difference between the error terms of SOLR and SRM calibrations, as shown in
Fig. 12. It is evident that both ports exhibit ripple in source matching term,
which is most likely caused by the pin gap, as the source match error term
describes the reflection at the calibration plane, which is where the pin gap
would show its most effects [29].

TABLE I: Pin gap of mated connectors. Values are reported in $\mu\mathrm{m}$. The pin depth gauge has a resolution of $2.54\,\mu\mathrm{m}$ ($0.0001\,\mathrm{in}$). The letter “f” stands for female (jack) and “m” for male (plug). |  | Short
---
(f)
| Open
---
(f)
| Match
---
(f)
| Adapter
---
(ff)
| Adapter
---
(fm)
| Port 1
---
(m)
31.75 | 31.75 | 31.75 | 35.56 | 54.61
| Port 2
---
(m)
31.75 | 31.75 | 31.75 | 36.83 | -
| Adapter
---
(fm)
31.75 | 31.75 | 31.75 | - | -
Figure 12: The magnitude of the error vector of the VNA’s error terms obtained
from SOLR and SRM calibration methods.

A final comparison is made between the calibrated female-female adapter of
both calibration methods. In both SOLR and SRM methods, the adapter was
assumed to be unknown but reciprocal during the calibration process. The
reference S-parameters of the adapter were provided by the manufacturer and
used to establish the error metric. However, no uncertainty bounds were
available. Fig. 13 depicts the calibrated adapter derived from both SOLR and
SRM methods. These measurement results are compared to the reference
S-parameters of the adapter. Both calibration procedures deliver comparable
results with similar errors.

Although SOLR and SRM delivered similar results in this experimental example,
it is important to note that for the SOLR method, all SOL standards already
have be characterized beforehand, whereas for the SRM method only the match
standard must be characterized.

Figure 13: Comparison of the calibrated female-female adapter using SOLR and
SRM methods.

##  VI Conclusion

This article presents a new VNA calibration method based on partially defined
standards. The proposed SRM method uses one-port symmetric standards, a two-
port reciprocal device, a combination of the reciprocal device with the one-
port device, and a match standard. Only the match standard must be
characterized among all standards, defining the calibration’s reference
impedance.

We have extended our proposed method to the particular case of an on-wafer
setup, where the probes are fixed in distance. To do this, we restricted the
two-port reciprocal device to be symmetric, allowing us to use half of it to
define the network-load standards.

To demonstrate the SRM method, we performed numerical analysis using CPW
synthetic data based on an actual on-wafer measurement setup. Additionally, we
have shown the SRM method using measurements based on commercial
$2.92\,\mathrm{mm}$ coaxial standards, indicating that the method is
compatible with commercial SOLR standards where only the match standard is
specified. Overall, the proposed SRM method offers greater flexibility in
standard definition, potentially decreasing errors associated with inadequate
calibration standard specifications.

## Acknowledgment

The financial support by the Austrian Federal Ministry for Digital and
Economic Affairs and the National Foundation for Research, Technology, and
Development is gratefully acknowledged.

## References

  * [1] W. Kruppa and K. Sodomsky, “An explicit solution for the scattering parameters of a linear two-port measured with an imperfect test set (correspondence),” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 19, no. 1, pp. 122–123, 1971, doi: 10.1109/TMTT.1971.1127466.
  * [2] A. Rumiantsev and N. Ridler, “VNA calibration,” _IEEE Microwave Magazine_ , vol. 9, no. 3, pp. 86–99, jun 2008, doi: 10.1109/mmm.2008.919925.
  * [3] J. A. Jargon, D. F. Williams, and A. Sanders, “The relationship between switch-term-corrected scattering-parameters and wave-parameters measured with a two-port vector network analyzer,” _IEEE Microwave and Wireless Components Letters_ , vol. 28, no. 10, pp. 951–953, oct 2018, doi: 10.1109/LMWC.2018.2867076.
  * [4] R. B. Marks, “Formulations of the basic vector network analyzer error model including switch-terms,” in _50th ARFTG Conference Digest_ , vol. 32, 1997, doi: 10.1109/ARFTG.1997.327265. pp. 115–126.
  * [5] Z. Hatab, M. E. Gadringer, and W. Bösch, “Indirect measurement of switch terms of a vector network analyzer with reciprocal devices,” _IEEE Microwave and Wireless Technology Letters_ , pp. 1–4, 2023, doi: 10.1109/LMWT.2023.3311032.
  * [6] A. Ferrero and U. Pisani, “Two-port network analyzer calibration using an unknown ’thru’,” _IEEE Microwave and Guided Wave Letters_ , vol. 2, no. 12, pp. 505–507, 1992, doi: 10.1109/75.173410.
  * [7] G. Engen and C. Hoer, “Thru-reflect-line: An improved technique for calibrating the dual six-port automatic network analyzer,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 27, no. 12, pp. 987–993, 1979, doi: 10.1109/TMTT.1979.1129778.
  * [8] R. Marks, “A multiline method of network analyzer calibration,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 39, no. 7, pp. 1205–1215, 1991, doi: 10.1109/22.85388.
  * [9] Z. Hatab, M. Gadringer, and W. Bösch, “Improving the reliability of the multiline trl calibration algorithm,” in _2022 98th ARFTG Microwave Measurement Conference (ARFTG)_. IEEE, jan 2022, doi: 10.1109/ARFTG52954.2022.9844064. pp. 1–5.
  * [10] Z. Hatab, M. E. Gadringer, and W. Bösch, “Propagation of linear uncertainties through multiline thru-reflect-line calibration,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 72, pp. 1–9, 2023, doi: 10.1109/TIM.2023.3296123.
  * [11] ——, “A thru-free multiline calibration,” _IEEE Transactions on Instrumentation and Measurement_ , pp. 1–9, 2023, doi: 10.1109/TIM.2023.3308226.
  * [12] H.-J. Eul and B. Schiek, “Thru-match-reflect: One result of a rigorous theory for de-embedding and network analyzer calibration,” in _1988 18th European Microwave Conference_ , 1988, doi: 10.1109/EUMA.1988.333924. pp. 909–914.
  * [13] W. Zhao _et al._ , “A unified approach for reformulations of lrm/lrmm/lrrm calibration algorithms based on the t-matrix representation,” _Applied Sciences_ , vol. 7, no. 9, 2017, doi: 10.3390/app7090866.
  * [14] A. Rumiantsev, T. Fu, and R. Doerner, “Improving wafer-level calibration consistency with tmrr calibration method,” in _2018 91st ARFTG Microwave Measurement Conference (ARFTG)_ , 2018, doi: 10.1109/ARFTG.2018.8423837. pp. 1–4.
  * [15] L. Hayden, “An enhanced line-reflect-reflect-match calibration,” in _2006 67th ARFTG Conference_ , 2006, doi: 10.1109/ARFTG.2006.4734364. pp. 143–149.
  * [16] D. F. Williams, F.-J. Schmückle, R. Doerner, G. N. Phung, U. Arz, and W. Heinrich, “Crosstalk corrections for coplanar-waveguide scattering-parameter calibrations,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 62, no. 8, pp. 1748–1761, aug 2014, doi: 10.1109/TMTT.2014.2331623.
  * [17] K. Dahlberg and K. Silvonen, “A method to determine lrrm calibration standards in measurement configurations affected by leakage,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 62, no. 9, pp. 2132–2139, sep 2014, doi: 10.1109/TMTT.2014.2333494.
  * [18] Y. Wang _et al._ , “An advanced calibration method for probe leakage correction in on-wafer test systems,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 71, no. 2, pp. 682–690, feb 2023, doi: 10.1109/TMTT.2022.3200050.
  * [19] S. Basu and L. Hayden, “An solr calibration for accurate measurement of orthogonal on-wafer duts,” in _1997 IEEE MTT-S International Microwave Symposium Digest_ , vol. 3. IEEE, 1997, doi: 10.1109/MWSYM.1997.596575. pp. 1335–1338 vol.3.
  * [20] T. Needham and R. Penrose, _Visual Complex Analysis: 25th Anniversary Edition_. Oxford University Press, 02 2023\. ISBN 9780192868916
  * [21] G. Strang, “The fundamental theorem of linear algebra,” _The American Mathematical Monthly_ , vol. 100, no. 9, pp. 848–855, nov 1993, doi: 10.2307/2324660.
  * [22] R. Marks and D. Williams, “A general waveguide circuit theory,” _Journal of Research (NIST JRES), National Institute of Standards and Technology, Gaithersburg, MD_ , no. 97, 1992, doi: 10.6028/jres.097.024.
  * [23] G. N. Phung, U. Arz, K. Kuhlmann, R. Doerner, and W. Heinrich, “Improved modeling of radiation effects in coplanar waveguides with finite ground width,” in _2020 50th European Microwave Conference (EuMC)_. IEEE, jan 2021, doi: 10.23919/eumc48046.2021.9338133.
  * [24] F. Schnieder, T. Tischler, and W. Heinrich, “Modeling dispersion and radiation characteristics of conductor-backed CPW with finite ground width,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 51, no. 1, pp. 137–143, jan 2003, doi: 10.1109/tmtt.2002.806926.
  * [25] W. Heinrich, “Quasi-TEM description of MMIC coplanar lines including conductor-loss effects,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 41, no. 1, pp. 45–52, 1993, doi: 10.1109/22.210228.
  * [26] Z. Hatab, “Linear uncertainty propagation in multiline trl calibration: Dataset and code,” 2023. [Online]. Available: https://doi.org/10.3217/GVZYW-1EA97
  * [27] A. Arsenovic _et al._ , “scikit-rf: An open source python package for microwave network creation, analysis, and calibration [speaker’s corner],” _IEEE Microwave Magazine_ , vol. 23, no. 1, pp. 98–105, jan 2022, doi: 10.1109/MMM.2021.3117139.
  * [28] “Ieee standard for precision coaxial connectors at rf, microwave, and millimeter-wave frequencies–part 1: General requirements, definitions, and detailed specifications,” _IEEE Std 287.1-2021_ , pp. 1–136, 2022, doi: 10.1109/IEEESTD.2022.9889249.
  * [29] _Guidelines on the Evaluation of Vector Network Analysers (Calibration Guide No. 12 Version 3.0)_ , EURAMET, Mar. 2018. [Online]. Available: https://www.euramet.org/publications-media-centre/calibration-guidelines


# Randomized greedy algorithm for independent sets in regular uniform
hypergraphs with large girth

Jiaxi Nie111E-mail<EMAIL_ADDRESS>Jacques Verstraëte222E-mail:
<EMAIL_ADDRESS>

Department of Mathematics
University of California, San Diego
9500 Gilman Drive
La Jolla CA 92093-0112

###### Abstract

In this paper, we consider a randomized greedy algorithm for independent sets
in $r$-uniform $d$-regular hypergraphs $G$ on $n$ vertices with girth $g$. By
analyzing the expected size of the independent sets generated by this
algorithm, we show that $\alpha(G)\geq(f(d,r)-\epsilon(g,d,r))n$, where
$\epsilon(g,d,r)$ converges to $0$ as $g\rightarrow\infty$ for fixed $d$ and
$r$, and $f(d,r)$ is determined by a differential equation. This extends
earlier results of Gamarnik and Goldberg for graphs [8]. We also prove that
when applying this algorithm to uniform linear hypergraphs with bounded
degree, the size of the independent sets generated by this algorithm
concentrate around the mean asymptotically almost surely.

KEYWORDS: Randomized greedy algorithm, independent sets, hypergraphs with
large girth.

##  1 Introduction

A hypergraph is a pair $(V,E)$ where $V$ is a set and $E$ is a family of
nonempty subsets of $V$. The $x\in V$ are called vertices and the $e\in E$ are
called edges. We use the notations $v(G)=|V(G)|$, $e(G)=|E(G)|$. A hypergraph
is called $r$-uniform if all edges have size $r$. A linear hypergraph is a
hypergraph $(V,E)$ such that for any distinct edges $e,f\in E$, $|e\cap f|\leq
1$. The degree of a vertex $v$, denoted by $d(v)$, is the number of edges that
contains it. A hypergraph is $d$-regular if all vertices have degree $d$. An
independent set of a hypergraph $G$ is a subset of $V(G)$ which does not
contain any edge of $G$. The maximum size of an independent set in $G$ is
called the independence number of $G$, denoted $\alpha(G)$.

In this paper, we study a natural randomized greedy algorithm for finding
independent sets in hypergraphs. The algorithm iteratively selects a vertex
uniformly randomly from all remaining vertices of the hypergraph and adds it
to the independent set so far, and then deletes all remaining vertices that
form an edge with the set of selected vertices, and repeat until no vertices
remain. The independent set generated by this algorithm for a hypergraph $G$
is denoted $\mathcal{I}(G)$.

###  1.1 Independent sets in graphs

Turán’s Theorem [14] shows that an $n$-vertex graph with average degree $d$
has independence number $\alpha(G)\geq n/(d+1)$, with equality only for a
disjoint union of cliques $K_{d+1}$. For triangle-free graphs $G$, Ajtai,
Komlós and Szemerédi [2] improved this bound by a factor of order $\log d$,
and Shearer [12] gave a further improvement:

######  Theorem 1.

Let $G$ be an $n$-vertex graph triangle-free of average degree $d\geq 2$. Then

$\alpha(G)\geq\frac{d\log d-d+1}{(d-1)^{2}}\cdot n.$ (1)

The girth of a graph containing a cycle is the length of a shortest cycle in
the graph. For graphs with high girth, Shearer [13] improved (1), and Lauer
and Wormald [9] showed that there exist a function $\delta=\delta(g)$ such
that $lim_{g\rightarrow\infty}\delta(g)=0$ and if $G$ is a $d$-regular graph
of girth $g$, then

$\alpha(G)\geq\frac{1}{2}(1-(d-1)^{-\frac{2}{d-2}})n-\delta n.$ (2)

By analyzing the performance of the greedy algorithm, Gamarnik and Goldberg
[8] prove the same bound, with an explicit form for $\delta$. It is convenient
to let

$\epsilon=\epsilon(d,g)=\frac{d(d-1)^{\lfloor\frac{g-3}{2}\rfloor}}{(\lfloor\frac{g-1}{2}\rfloor)!}.$
(3)

Note that for each fixed $d$, $\epsilon(d,g)\rightarrow 0$ as
$g\rightarrow\infty$.

######  Theorem 2.

Let integers $d\geq 3$ and $g\geq 4$, and let $G$ be a $d$-regular graph on
$n$ vertices with girth $g$, and let $\mathcal{I}$ be the independent set
generated by the greedy algorithm. Then

$\Bigl{(}\frac{1-(d-1)^{-2/(d-2)}}{2}-\epsilon\Bigr{)}n\leq\mathbb{E}[|\mathcal{I}|]\leq\Bigl{(}\frac{1-(d-1)^{-2/(d-2)}}{2}+\epsilon\Bigr{)}n,$
(4)

The bounds are effective when $d$ is fixed and $g$ is large and, in
particular, Theorem 2 shows

$\alpha(G)\geq\Bigl{(}\frac{1-(d-1)^{-2/(d-2)}}{2}-\epsilon\Bigr{)}n.$ (5)

We also observe that when $g$ is sufficiently large relative to $d$, this
bound agrees with (1) asymptotically as $d\rightarrow\infty$, since

$(d-1)^{-2/(d-2)}=\exp\left(-\frac{2\log(d-1)}{d-2}\right)=1-\frac{2\log(d-1)}{d-2}(1+o_{d}(1)),$

where $o_{d}(1)$ here represents a function of $d$ that converges to zero as
$d\rightarrow\infty$. When we say a function $f(x)$ is asymptotic to $g(x)$ as
$x\rightarrow\infty$(which is abbreviated $f\sim g$), it means that
$\lim_{x\rightarrow\infty}f(x)/g(x)=1$.

###  1.2 Independent sets in hypergraphs

For $(r+1)$-uniform hypergraphs with average degree $d$, Caro and Tuza [5]
showed that

$\alpha(G)\geq\frac{d!}{\prod_{i=1}^{d}(i+\frac{1}{r})}\cdot n.$ (6)

The same bound can also be obtained by extending the Caro-Wei [4] [15] bound
for independent sets in graphs: taking a random ordering of the vertices of
the hypergraph, let $I$ be the set of vertices $v$ such that for every edge
$e$ containing $v$, $v$ is not the smallest vertex in $e$. Then it can be
shown via elementary combinatorial methods that

$\mathbb{E}[|I|]\geq\sum_{v\in
V}\frac{d!}{\prod_{i=1}^{d}(i+\frac{1}{r})}=\frac{d!}{\prod_{i=1}^{d}(i+\frac{1}{r})}\cdot
n.$ (7)

The same algorithm can be implemented via the following random process, which
provide a different (and possibly easier) way to analyze the outcome (see for
example in Dutta, Mubayi and Subramanian [7]):

  1. 1.

Equip each vertex with i.i.d. weight from the uniform distribution on [0,1].
Then with probability 1, all vertices will have distinct weights.

  2. 2.

Select all the vertices that are not the smallest-weighted vertex in any edge
that contains it. These vertices form an independent set.

If we select vertices in a more careful way – iteratively select the vertex
with largest weight, i.e., select the vertex with largest weight, delete
vertices that form an edge with the vertices selected thus far, and repeat –
then this random process will be equivalent to the randomized greedy
algorithm. In any case, a computation shows

$\mathbb{E}[|I|]\geq n\int_{0}^{1}(1-x^{r})^{d}dx$ (8)

which gives (7). These bounds are asymptotic to
$\Gamma(1+\frac{1}{r})nd^{-\frac{1}{r}}$ as $d\rightarrow\infty$, where
$\Gamma$ here is the well-known gamma function that extends factorial function
to complex numbers. In this paper, we consider this algorithm in uniform
hypergraphs of large girth.

To define girth in hypergraph, we first need to define what is a cycle in
hypergraph. There are many different ways to define cycle in hypergraph–see,
e.g., a talk by Sárközy [11]. Here we chose to work with the Berge-cycle. For
$k\geq 3$, a Berge $k$-cycle is an $r$-uniform hypergraph with $k$ edges
$e_{1},e_{2},\dots,e_{k}$ such that there exist distinct vertices
$v_{1},v_{2},\dots,v_{k}$ such that $\\{v_{k},v_{1}\\}\in
e_{1},\\{v_{1},v_{2}\\}\in e_{2},\dots,\\{v_{k-1},v_{k}\\}\in e_{k}$. When
$k=2$, this corresponds to $v_{1},v_{2}\in e_{1}\cap e_{2}$. The girth of a
hypergraph containing a Berge cycle is the smallest $g$ such that the
hypergraph contains a Berge $g$-cycle. In particular, the girth of a non-
linear hypergraph is 2. Ajtai, Komlós, Pintz, Spencer and Szemerédi [1]
established the following lower bound for $(r+1)$-uniform hypergraphs with
girth $g\geq 5$, which improves (7) by a factor of order $(\log
d)^{\frac{1}{r}}$.

######  Theorem 3.

For integer $r\geq 1$, real number $d$ sufficiently large and integer $n$
sufficiently large, let $G$ be an $n$-vertex $(r+1)$-uniform hypergraphs with
average degree $d$ and girth at least $5$, then

$\alpha(G)\geq 0.36\cdot
10^{-\frac{5}{r}}\left(\frac{\log{d}}{rd}\right)^{\frac{1}{r}}n.$ (9)

Based on this theorem, Duke, Lefmann and Rödl [6] showed that the same
bound(with different constant) holds for linear hypergraphs.

###  1.3 Main Theorem

In this paper, we extend the ideas of Gamarnik and Goldberg [8] to
hypergraphs. First, it is convenient to define the following: Let $u(d,r)$ be
the only positive real number that satisfies the following equation:

$\sum_{n\geq 0}\binom{n+d-2}{d-2}\frac{u(d,r)^{rn+1}}{rn+1}=1.$ (10)

Define

$\epsilon=\epsilon(g,d,r)=\frac{d(d-1)^{\lfloor\frac{g-3}{2}\rfloor}}{r\sum_{k=1}^{\lfloor\frac{g-1}{2}\rfloor}(k+\frac{1}{r})}.$
(11)

Our main theorem is as follows:

######  Theorem 4.

For any integers $r\geq 1$, $d\geq 2$ and $g\geq 4$, let $G$ be an
$(r+1)$-uniform $d$-regular hypergraph with $n$ vertices and girth $g$, let
$\mathcal{I}$ be the independent set of $G$ generated by the greedy algorithm.
Let

$f(d,r)=u(d,r)-\frac{u(d,r)^{r+1}}{r+1}.$ (12)

Then

$(f(d,r)-\epsilon)n\leq\mathbb{E}[|\mathcal{I}|]\leq(f(d,r)+\epsilon)n,$ (13)

In particular, due to the form of the quantity $\epsilon=\epsilon(g,d,r)$,
this theorem is effective for fixed $d$ and large $g$, and shows

$\alpha(G)\geq(f(d,r)-\epsilon)n.$ (14)

For $r=1$, this coincides with Theorem 2. We prove in Appendix A that as
$d\rightarrow\infty$,

$f(d,r)\sim\Bigl{(}\frac{\log d}{rd}\Bigr{)}^{\frac{1}{r}},$ (15)

and so if $g$ is large enough relative to $d$, then this slightly improves the
constant in (9) asymptotically as $d\rightarrow\infty$.

Our second result shows that the size of the independent set generated by the
greedy algorithm concentrate around its mean asymptotically almost surely for
linear hypergraphs with bounded degree (i.e. hypergraphs that are not
necessarily regular):

######  Theorem 5.

For any integers $r\geq 1$ and $d\geq 2$, let $G$ be an $(r+1)$-uniform linear
hypergraph with maximum degree $d$ on $n$ vertices, $\mathcal{I}(G)$ be the
independent set generated by the greedy algorithm, then for any positive
function $b(n)$ with $b(n)\rightarrow\infty$ as $n\rightarrow\infty$, we have

$\mathbb{P}[||\mathcal{I}(G)|-\mathbb{E}[|\mathcal{I}(G)|]|>\sqrt{n}b(n)]\rightarrow
0,\ as\ n\rightarrow\infty.$

The rest of this paper is structured as follows. In Section 2, we introduce
influence-blocking hypergraphs and bonus function of hypergraphs. They are
originally notions for graphs from Gamarnik and Goldberg [8], which are
generalized to notions for hypergraphs here. In Section 3, we prove Theorem 4
by using the property of influence-blocking hypergraphs to reduce the problem
of estimating $\mathbb{E}[|\mathcal{I}(G)|]$ to a local problem on a rooted
hypertree, and then using the bonus function of hypergraphs to establish a
differential equation. In Section 4, we use second moment method to prove
Theorem 5. In the appendix, we present the asymptotic analysis of the quantity
$f(d,r)$ from Theorem 4.

##  2 Preliminaries

Gamarnik and Goldberg [8] introduce two notions for graphs, the influence-
blocking subgraph and bonus function. In this section, we generalize these
notions to hypergraphs and discuss their properties. A hypertree is a linear
hypergraph with no Berge cycle, and a rooted hypertree is a hypertree in which
a special vertex called the root is singled out. In summary, we show that the
performance of the greedy algorithm on hypergraphs with large girth is locally
similar to its performance on a rooted hypertree – note that if a hypergraph
has high girth, then for each vertex, its neighbourhood within finite distance
looks like a hypertree. Hence, if we can show that the event of a vertex being
selected into the independent set is mostly dependent on its neighbourhood
within finite distance, then we can simplify the analysis of each vertex into
the analysis of the root of a rooted tree. Then we analyze the probability of
the root of a rooted hypertree being selected by the randomized greedy
algorithm. For ease of analysis, we consider an equivalent way to do the
randomized greedy algorithm as follows:

  1. 1.

Equip each vertex with i.i.d. weight from the uniform distribution on $[0,1]$.
Then with probability 1, all vertices will have distinct weights.

  2. 2.

Iteratively select the vertex with largest weight from all remaining vertices
of $G$, and add it to the independent set so far, and then delete all
remaining vertices that form an edge with the selected vertices, and repeat
until no vertices remain.

The strategy is to analyze the probability of each vertex being selected into
the independent set.

###  2.1 Influence-blocking hypergraphs

Garmarnik and Goldberg [8] introduce influence-blocking subgraphs; here we
extend this notion to hypergraphs. Suppose we already applied the first step
of the greedy algorithm on $G$. That is, the vertices of $G$ are now equipped
with distinct weights. Let $v$ be a vertex of $G$, $e$ be an edge of $G$ such
that $e$ contains $v$. We say $v$ defeats $e$ if there is another vertex
$v^{\prime}$ in $e$ such that the weight of $v^{\prime}$ is smaller than the
weight of $v$. That is, $v$ is not the smallest weighted vertex in $e$.
Observe that if $v$ defeats all the edges that contains it, then $v$ must be
selected into $\mathcal{I}(G)$, since it cannot be deleted according to the
rule of the algorithm. In this case, the weight of any other vertex that is
not in the neighbourhood of $v$ will not influence the behaviour of $v$. This
phenomenon can be generalized to sub-hypergraphs, which gives us the following
definition:

######  Definition 1.

Let $G$ be a hypergraph whose vertices are equipped with distinct weights. An
induced sub-hypergraph $H$ of $G$ is called an influence-blocking hypergraph
if for every vertex $v\in V(H)$, and $e\in E(G)\backslash E(H)$ with $v\in e$,
$v$ is not the vertex in $e$ with smallest weight.

If $G$ is a hypergraph whose vertices are already equipped with distinct
weights, then we also let $\mathcal{I}(G)$ denote the independent set of $G$
generated by applying the second step of the greedy algorithm to $G$. Let $v$
be a vertex of $G$, such that $v\not\in\mathcal{I}(G)$. If $e$ is an edge of
$G$, such that $v\in e$ and $e\subset v\cup\mathcal{I}(G)$, then we say $v$ is
deleted by $e$. The first property of influence-blocking hypergraphs is that
the performance of the greedy algorithm inside this sub-hypergraph is not
dependent on the performance of the algorithm outside this sub-hypergraph.
This phenomenon is described by the following lemma, which is a
straightforward modification of Lemma $5$ in [8]:

######  Lemma 6.

Let $G$ be a hypergraph whose vertices are equipped with distinct weights. Let
$H$ be an influence-blocking hypergraph of $G$. Then
$\mathcal{I}(H)=\mathcal{I}(G)\cap V(H)$.

###### Proof.

Let $V(H)=\\{v_{1},v_{2},\dots,v_{m}\\}$, such that $v_{1}>v_{2}>\dots>v_{m}$
(where $v_{i}>v_{j}$ means the weight of $v_{i}$ is larger than the weight of
$v_{j}$). To prove the lemma, it suffices to show that
$v_{i}\in\mathcal{I}(H)$ if and only if $v_{i}\in\mathcal{I}(G)$, for all $i$
such that $1\leq i\leq m$. We do that by induction. First, for $i=1$, we have
$v_{1}\in\mathcal{I}(H)$. By the definition of influence-blocking hypergraph,
$v_{1}$ cannot be deleted by edges not in $H$. Since $v_{1}$ has the largest
weight among all vertices of $H$, so it cannot be deleted by edges in $H$
either. Hence, we also have $v_{1}\in\mathcal{I}(G)$. This completes the base
case. Now suppose $1<i\leq m$, and the argument holds for all integer less
than $i$. If $v_{i}\not\in\mathcal{I}(H)$, then $v_{i}$ must be deleted by an
edge $e\in E(H)$ such that $e\backslash v_{i}$ consists of vertices whose
weights are larger than the weight of $v_{i}$. Then by the inductive
assumption, $v_{i}$ must be deleted by the same edge in the algorithm for $G$.
Hence, we have $v_{i}\not\in\mathcal{I}(G)$. If $v_{i}\in\mathcal{I}(H)$, then
$v_{i}$ cannot form an edge in $H$ with vertices whose weights are larger than
the weight of $v_{i}$. Hence, by inductive assumption, $v_{i}$ cannot be
deleted by edges in $H$. Also, by the definition of influence-blocking
hypergraph, $v_{i}$ cannot be deleted by edges not in $H$ either. Therefore,
we have $v_{i}\in\mathcal{I}(G)$. This completes the inductive step, and hence
the proof of the lemma. ∎

The second property of the influence-blocking hypergraphs is that any subset
of vertices can be extended to a unique minimal influence-blocking hypergraph,
which is presented by the following lemma, which is a straightforward
modification of Lemma $3$ in [8]:

######  Lemma 7.

Let $G$ be a hypergraph whose vertices are equipped with distinct weights. Let
$A$ be such that $A\subset V(G)$, then there exist a unique minimal influence-
blocking hypergraph $\mathcal{B}_{G}(A)$ of $G$ such that $A\subset
V(\mathcal{B}_{G}(A))$. It can be simplified as $\mathcal{B}(A)$ if there is
no ambiguity.

###### Proof.

Pick a set of vertices $V_{A}$ as following. First, put all vertices of $A$
into $V_{A}$. Then, we iteratively take edges that are not in $A$ but whose
smallest-weighted vertex is in $A$, and put all the vertices of such edges
into $V_{A}$, and then repeat until no edge like this remains. Let
$\mathcal{B}(A)$ be the sub-hypergraph of $G$ induced by $V_{A}$. By
definition, $\mathcal{B}(A)$ is an influence-blocking hypergraph of $G$, and
is contained in any influence-blocking hypergraph of $G$ that contains $A$.
Hence, it is minimal. Also, by the process that it is generated, we can see
that it is unique. ∎

######  Definition 2.

For any integers $r,l\geq 1$, an $(r+1)$-uniform path of length $l$ connecting
$v_{0}$ to $v_{lr}$ is a hypergraph with vertices
$\\{v_{0},v_{1},\dots,v_{lr}\\}$ and edges
$e_{k}=\\{v_{kr},v_{kr+1},\dots,v_{(k+1)r}\\}$ for ${0\leq k\leq l-1}$. If the
vertices of a path are weighted and the smallest-weighted vertex in edge
$e_{k}$ is $v_{kr}$ for all $0\leq k\leq l-1$, then we say the weighted path
is increasing from $v_{0}$ to $v_{lr}$.

Note that the definition of path here is different from the definition of a
Berge path, which is defined in a similar way as the Berge cycle.

The following lemma evaluate the probability that a path in a hypergraph is
increasing when given a random total order:

######  Lemma 8.

For any integers $r,l\geq 1$, the number of ways to assign
$\\{0,1,\dots,lr\\}$ as distinct weights to the vertices of an $(r+1)$-uniform
paths of length $l$ from $v_{0}$ to $v_{lr}$ so that it is increasing is

$\frac{(lr+1)!}{\prod_{k=1}^{l}(kr+1)}.$

Hence, for an $(r+1)$-uniform path $P$ of length $l$, if each vertex is
equipped with i.i.d. weight from the uniform distribution on $[0,1]$, then

$\mathbb{P}[\text{$P$ is increasing from $v_{0}$ to
$v_{lr}$}]=\frac{1}{\prod_{k=1}^{l}(kr+1)}.$ (16)

###### Proof.

For simplicity, we only prove this for $r=2$. In this case, we want to show
that the number of proper weight assignments for paths of length $l$ is
$(2l)!!=\prod_{k=1}^{l}(2k)$. The idea of the proof for general case is
exactly the same. Let $a_{l}$ be the number of proper weight assignments for
$3$-uniform paths of length $l$ with distinct weights from
$\\{0,1,\dots,2l\\}$. Let $W_{i}$ be the weight of $v_{i}$. We prove
$a_{l}=(2l)!!$ by induction. First, for $l=1$, $W_{0}$ has to be $0$, $W_{2}$
can be either $1$ or $2$. So $a_{1}=2=2!!$. Now for $l\geq 2$, suppose the
lemma is true for $l-1$. Then again, $W_{0}$ has to be $0$. $W_{2}$ is less
than all $W_{i}$ with $i>2$, so $W_{2}$ is at least the third smallest weight.
As a result, $W_{2}=1$ or $2$. When $W_{2}=1$, $W_{1}$ can be any number in
$\\{2,3,\dots,2l\\}$, and all the other vertices form a $3$-uniform increasing
path of length $l-1$. So the number of proper weight assignments of this kind
is $(2l-1)a_{l-1}$. When $W_{2}=2$, $W_{1}$ has to be 1, and all the other
vertices form a $3$-uniform increasing path of length $l-1$, the number of
proper weight assignments of this kind is $a_{l-1}$. Hence, by inductive
assumption, we have $a_{l}=2la_{l-1}=2l\cdot(2l-2)!!=(2l)!!$. This completes
the proof for $r=2$. ∎

For any vertex $v$ and any integer $h\geq 1$, let $N_{h}(v)$ be the set of
vertices $w$ such that there exist a path, as defined in Definition 2,
connecting $v$ to $w$, whose length is less or equal than $h$. When $h=0$, let
$N_{0}(v)={v}$. The following lemma, which is a modification of Lemma $6$ in
[8], show that for any vertex $v$, the probability that the minimal influence-
blocking hypergraph containing $v$ is not a sub-hypergraph of $N_{h}(v)$
converges to $0$ as $h\rightarrow\infty$.

######  Lemma 9.

For any integers $r\geq 1$ and $d\geq 2$, let $G$ be any $(r+1)$-uniform
linear hypergraph of maximum degree $d$, and suppose that the vertices are
equipped with i.i.d. weights from the uniform distribution on $[0,1]$. Then
for any vertex $v$ and any $h\geq 0$,

$\mathbb{P}[\mathcal{B}(v)\not\subset
N_{h}(v)]\leq\frac{d(d-1)^{h}}{r\prod_{k=1}^{h+1}(k+\frac{1}{r})}.$

###### Proof.

For any vertex $v$ there exist at most $d(d-1)^{h}r^{h}$ distinct paths of
length $h+1$ that connecting $v$ to some vertex in $N_{h+1}(i)\backslash
N_{h}(i)$. By definition, $\mathcal{B}(v)\not\subset N_{h}(v)$ if and only if
at least one of these path is increasing. So by applying a union bound and
equation (16), we have

$\mathbb{P}[\mathcal{B}(v)\not\subset
N_{h}(v)]\leq\frac{d(d-1)^{h}r^{h}}{\prod_{k=1}^{h+1}(kr+1)}=\frac{d(d-1)^{h}}{r\prod_{k=1}^{h+1}(k+\frac{1}{r})}.$

∎

###  2.2 Bonus function of hypergraphs

To analyze the probability of the root of a rooted hypertree being selected
into the independent set, we use the following notion to establish a recursive
equation, and hence by some analysis, a differential equation.

Consider the following bonus function of hypergraphs, which is extended from
the bonus function of graphs introduced by Garmarnik and Goldberg [8]:

######  Definition 3.

Let $T$ be a rooted hypertree, whose vertices are equipped with distinct
positive weights. Let $W_{v}$ be the weight of a vertex $v$, $DE(v)$ be the
set of descending edges of $v$ and $I$ be the indicator function. Then the
bonus function of hypergraphs $S_{T}:V(T)\rightarrow\mathbb{R}$ is defined by

$S_{T}(v)=\left\\{\begin{aligned} &W_{v},&&\text{v is leaf,}\\\
&W_{v}\prod_{e\in DE(v)}I(W_{v}>\min_{u\in e,u\not=v}\\{S_{T}(u)\\}),\
&&\text{otherwise.}\end{aligned}\right.$

Given a weighted rooted tree, the bonus function value of the root is exactly
the weight of the root if the root is selected by the greedy algorithm, and is
$0$ if the the root is not selected, as shown by the following lemma:

######  Lemma 10.

Let $T$ be a rooted hypertree, whose vertices are equipped with distinct
positive weights. Let $\gamma$ be the root of $T$, $W_{\gamma}$ be the weight
of $\gamma$, then we have

$S_{T}(\gamma)=W_{\gamma}I(\gamma\in\mathcal{I}(T)).$

###### Proof.

We prove by induction on the height of the tree. When the height is $0$, this
lemma is true. Now suppose $T$ has height $h>0$, and this lemma holds for all
trees with height less than $h$. Let $e_{k},\ 1\leq k\leq d$, be all
descending edges of the root $\gamma$. Then by definition of the bonus
function, we have

$S_{T}(\gamma)=W_{\gamma}\prod_{k=1}^{d}I(W_{\gamma}>\min_{v\in
e_{k},v\not=\gamma}\\{S_{T}(v)\\}).$

So it suffices to show that

$\prod_{k=1}^{d}I(W_{\gamma}>\min_{v\in
e_{k},v\not=\gamma}\\{S_{T}(v)\\})=I(\gamma\in\mathcal{I}(T)).$

Let $T_{v}$ be the subtree of $T$ with root $v$, such that $T_{v}$ contains
only the edges descending from $v$. If $W_{\gamma}>\min_{v\in
e_{k},v\not=\gamma}\\{S_{T}(v)\\}$ for all $k$ such that $1\leq k\leq d$. For
an arbitrary $k$, pick $v\in e_{k}$, $v\not=\gamma$, such that
$W_{\gamma}>S_{T}(v)$, then there are two cases. Firstly, if
$W_{\gamma}<W_{v}$, then we have $S_{T}(v)=0$. By inductive assumption, this
implies $v\not\in\mathcal{I}(T_{v})$. Then by Lemma 6, since $T_{v}$ is an
influence-blocking hypergraph of $T$, we have $v\not\in\mathcal{I}(T)$. This
means that $\gamma$ will not be deleted by $e_{k}$. Secondly, if
$W_{\gamma}>W_{v}$. This also means that $\gamma$ will not be deleted by
$e_{k}$. This argument works for all $1\leq k\leq d$. Therefore,
$\gamma\in\mathcal{I}(T)$.

On the other hand, if $W_{\gamma}<\min_{v\in
e_{k},v\not=\gamma}\\{S_{T}(v)\\}$ for some $k$, then $W_{\gamma}$ must be the
smallest-weighted vertex in $e_{k}$ and $v\in\mathcal{I}(T_{v})$ for all $v\in
e_{k}$, $v\not=\gamma$. Since $T_{v}$ is an influence-blocking hypergraph of
$T$, by Lemma 6 we have $v\in\mathcal{I}(T)$ for all $v\in e_{k}$,
$v\not=\gamma$. This implies that $\gamma$ will be deleted by $e_{k}$.
Therefore, $\gamma\not\in\mathcal{I}(T)$. ∎

Let $T(d,h)$ be the $(r+1)$-uniform rooted hypertree such that all non-leaf
vertices have $d$ descending edges, and all leaves have depth $h$. Let
$\tilde{T}(d,h)$ be the $(r+1)$-uniform rooted hypertree such that the root
has $d$ descending edges while all other non-leaf vertices have $d-1$
descending edges, and all leaves have depth $h$.

Let $\gamma$ be the root of $T(d,h)$. Apply the first step of the greedy
algorithm to $T(d,h)$, that is, randomly assign weights to $T(d,h)$. Let
$F_{d,h}$ be the distribution function of $S_{T(d,h)}(\gamma)$. That is,
$F_{d,h}(x)=\mathbb{P}[S_{T(d,h)}(\gamma)\leq x]$. Similarly, let
$\tilde{F}_{d,h}$ be the distribution function of
$S_{\tilde{T}(d,h)}(\gamma)$. That is,
$\tilde{F}_{d,h}(x)=\mathbb{P}[S_{\tilde{T}(d,h)}(\gamma)\leq x]$. Note that
by Lemma 10, we have

$\displaystyle 1-F_{d,h}(0)=\mathbb{P}[\gamma\in\mathcal{I}(T(d,h)]$ (17)
$\displaystyle
1-\tilde{F}_{d,h}(0)=\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h)]$ (18)

Also by definition of the bonus function of hypergraphs, $F_{d,h}$ and
$\tilde{F}_{d,h}$ satisfy the following recursive equations for all
$x\in[0,1]$:

$F_{d,h}(x)=1-\int^{1}_{x}\mathbb{P}[S_{T(d,h)}(\gamma)=W_{\gamma}|W_{\gamma}=t]dt=1-\int^{1}_{x}[1-(1-F_{d,h-1}(t))^{r}]^{d}dt$
(19)
$\tilde{F}_{d,h}(x)=1-\int^{1}_{x}\mathbb{P}[S_{\tilde{T}(d,h)}(\gamma)=W_{\gamma}|W_{\gamma}=t]dt=1-\int^{1}_{x}[1-(1-F_{d-1,h-1}(t))^{r}]^{d}dt$
(20)

In order to get a differential equation, we need to show that $F_{d,h}$ and
$\tilde{F}_{d,h}$ converge as $h\rightarrow\infty$. We make use of the
following lemma:

######  Lemma 11.

For any $x\in\mathbb{R}$ and integer $h\geq 0$, the following inequalities
hold:

$(-1)^{h}F_{d,h}(x)\leq(-1)^{h}F_{d,h+1}(x)$ (21)
$(-1)^{h}F_{d,h}(x)\leq(-1)^{h}F_{d,h+2}(x)$ (22)

###### Proof.

We prove inequality (21) by induction. First, when $h=0$, by definition we
have $F_{d,0}(x)\leq F_{d,1}(x)$. Now for $h\geq 1$, suppose inequality (21)
holds for $h-1$. Replace $h$ by $h+1$ in equality (19) and consider its
difference with the original equality, we have

$F_{d,h+1}(x)-F_{d,h}(x)=\int^{1}_{x}\left(\left(1-(1-F_{d,h-1}(t))^{r}\right)^{d}-\left(1-(1-F_{d,h}(t))^{r}\right)^{d}\right)dt$

Using this equation, we can check that when $F_{d,h}(x)\geq F_{d,h-1}(x)$, we
have $F_{d,h+1}(x)\leq F_{d,h}(x)$; and when $F_{d,h}(x)\leq F_{d,h-1}(x)$, we
have $F_{d,h+1}(x)\geq F_{d,h}(x)$. Hence, by inductive assumption, we have
$(-1)^{h}F_{d,h}(x)\leq(-1)^{h}F_{d,h+1}(x)$. This completes the proof for
inequality (21). Same reasoning gives the proof for inequality (22). ∎

######  Corollary 12.

There exist functions $F_{d,even}(x):\mathbb{R}\rightarrow[0,1]$ and
$F_{d,odd}(x):\mathbb{R}\rightarrow[0,1]$ such that the sequence of functions
$\\{F_{d,2k}(x)\\}_{k\geq 0}$ converges pointwise to $F_{d,even}(x)$ and the
sequence of functions $\\{F_{d,2k+1}(x)\\}_{k\geq 0}$ converges pointwise to
$F_{d,odd}(x)$, and $F_{d,even}(x)\leq F_{d,odd}(x)$ for all $x\in\mathbb{R}$.

###### Proof.

As a result of inequality (22), for any $x\in\mathbb{R}$, the sequence
$\\{F_{d,2k}(x)\\}_{k\geq 0}$ is increasing and the sequence
$\\{F_{d,2k+1}(x)\\}_{k\geq 0}$ is decreasing. Also, by inequality (21), both
sequences are bounded. Hence, by the Monotone Convergence Theorem [10], they
must converge, which implies the existence of $F_{d,even}(x)$ and
$F_{d,odd}(x)$. The inequality can be obtained by considering the inequality
(21) with $h=2k$ and $k\rightarrow\infty$. ∎

Similar results as Lemma 11 and Corollary 12 for $\tilde{F}_{d,h}$ can also be
obtained using the same idea, and we omit the details.

##  3 Proof of Theorem 4

The following lemma, which is a modification of Theorem $7$ in [8], provide an
upper bound for the difference between the probability that a vertex $v$ in a
hypergraph $G$ is selected and the probability that the root $\gamma$ of a
rooted hypertree is selected by the greedy algorithm, showing that the
performance of the greedy algorithm on $G$ is locally similar to that on a
hypertree.

######  Lemma 13.

For any integers $r\geq 1$, $d\geq 2$ and $g\geq 4$, let $G$ be an
$(r+1)$-uniform $d$-regular hypergraph with girth $g$. Let
$h_{0}=\lfloor\frac{g-3}{2}\rfloor$, $T=\tilde{T}(d,h)$ with $h\geq h_{0}+1$,
let $\gamma$ be the root of $T$. Then for every vertex $v\in V(G)$,

$|\mathbb{P}[v\in\mathcal{I}(G)]-\mathbb{P}[\gamma\in\mathcal{I}(T)]|\leq\frac{d(d-1)^{h_{0}}}{r\prod_{k=1}^{h_{0}+1}(k+\frac{1}{r})}.$
(23)

###### Proof.

We apply the first step of greedy algorithm on $G$ and $T$ in the following
way. We first give vertices of $G$ i.i.d. weights from the uniform
distribution on $[0,1]$. Observe that $N_{h_{0}+1}(v)$ is a
$\tilde{T}(d,h_{0}+1)$ hypertree, so we can find an isomorphism $f$ that maps
$N_{h_{0}+1}(v)$ to $N_{h_{0}+1}(\gamma)$. Then we give the vertices in
$N_{h_{0}+1}(\gamma)$ the same weight as their coimage in $N_{h_{0}+1}(v)$.
Finally we give all remaining vertices in $T$ i.i.d. weights from the uniform
distribution on $[0,1]$. Then we apply the second step of greedy algorithm on
both $G$ and $T$ to get $\mathcal{I}(G)$ and $\mathcal{I}(T)$. In this
setting, we have the following estimate:

$\displaystyle\mathbb{P}[v\in\mathcal{I}(G)]=$
$\displaystyle\mathbb{P}[v\in\mathcal{I}(G),\mathcal{B}_{G}(v)\subset
N_{h_{0}}(v)]+\mathbb{P}[v\in\mathcal{I}(G),\mathcal{B}_{G}(v)\not\subset
N_{h_{0}}(v)]$ $\displaystyle=$
$\displaystyle\mathbb{P}[\gamma\in\mathcal{I}(T),\mathcal{B}_{T}(\gamma)\subset
N_{h_{0}}(\gamma)]+\mathbb{P}[v\in\mathcal{I}(G),\mathcal{B}_{G}(v)\not\subset
N_{h_{0}}(v)]$ (Lemma 6) $\displaystyle\leq$
$\displaystyle\mathbb{P}[\gamma\in\mathcal{I}(T)]+\mathbb{P}[\mathcal{B}_{G}(v)\not\subset
N_{h_{0}}(v)].$

This implies that

$\displaystyle\mathbb{P}[v\in\mathcal{I}(G)]-\mathbb{P}[\gamma\in\mathcal{I}(T)]$
$\displaystyle\leq\mathbb{P}[\mathcal{B}_{G}(v)\not\subset N_{h_{0}}(v)]$
$\displaystyle\leq\frac{d(d-1)^{h_{0}}}{r\prod_{k=1}^{h_{0}+1}(k+\frac{1}{r})}.$
(Lemma 9)

We complete the proof by repeating the reasoning above with the roles of
$\mathbb{P}[v\in\mathcal{I}(G)]$ and $\mathbb{P}[\gamma\in\mathcal{I}(T)]$
reversed. ∎

Using similar idea as in the proof above, we can also show that the following
limits exist:

######  Lemma 14.

For any fixed integer $d$, the limits
$\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}({T}(d,h))]}$ and
$\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]}$
exist, where $\gamma$ denote the root of the rooted hypertrees.

###### Proof.

We only present the proof of the existence of
$\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]}$.
The proof of the existence of
$\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}({T}(d,h))]}$ is
similar and we omit the details. Let $h$, $h^{\prime}$ be positive integers
with $h^{\prime}>h$. Using the same idea as in the proof of Lemma 13, we can
show that

$|\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]-\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h^{\prime}))]|\leq\frac{d(d-1)^{h-1}}{r\prod_{k=1}^{h}(k+\frac{1}{r})}\rightarrow
0\ \text{as $h\rightarrow\infty$}.$

So we conclude that the sequence
$\\{\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]\\}_{h\geq 1}$ is a Cauchy
sequence and therefore has a limit. ∎

Now we are ready to show that $F_{d,h}(x)$ and $\tilde{F}_{d,h}(x)$ converge,
and hence get the differential equations we need:

######  Lemma 15.

there exist functions $F_{d}(x)$ and $\tilde{F}_{d}(x)$such that $F_{d,h}(x)$
converges pointwise to $F_{d}(x)$ and $\tilde{F}_{d,h}(x)$ converges pointwise
to $\tilde{F}_{d}(x)$ as $h\rightarrow\infty$. $F_{d}(x)$ and
$\tilde{F}_{d}(x)$ satisfy the following equations:

$F_{d}(x)=1-\int^{1}_{x}[1-(1-F_{d}(t))^{r}]^{d}dt,$ (24)
$\tilde{F}_{d}(x)=1-\int^{1}_{x}[1-(1-F_{d-1}(t))^{r}]^{d}dt.$ (25)

###### Proof.

We only present the proof of the existence of $F_{d}$ here. The proof of the
existence of $\tilde{F}_{d}$ is similar and we omit the details. By Corollary
12, there exist $F_{d,even}(x)$ and $F_{d,odd}(x)$ such that $F_{d,2k}(x)$
converges pointwise to $F_{d,even}(x)$ and $F_{d,2k+1}(x)$ converges pointwise
to $F_{d,odd}(x)$ as $k\rightarrow\infty$. Hence, to prove the existence of
$F_{d}$, it suffices to show that $F_{d,even}(x)=F_{d,odd}(x)$ for all
$x\in\mathbb{R}$. By Lemma 14,
$\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}(T(d,h))]}$ exists.
Since $F_{d,h}(0)=1-\mathbb{P}[\gamma\in\mathcal{I}(T(d,h))]$, this implies
that $\lim_{h\rightarrow\infty}{F_{d,h}(0)}$ exists. So we have

$F_{d,even}(0)=\lim_{h\rightarrow\infty}{F_{d,h}(0)}=F_{d,odd}(0).$

Now consider equation (19) with $h=2k$, and let $k$ go to infinity on both
sides, and then use the Dominated Convergence Theorem [10], we have

$F_{d,even}(x)=1-\int^{1}_{x}[1-(1-F_{d,odd}(t))^{r}]^{d}dt.$

Similarly, we also have

$F_{d,odd}(x)=1-\int^{1}_{x}[1-(1-F_{d,even}(t))^{r}]^{d}dt.$

Take the derivative on both sides and then take the difference of these two
equations, we have

$F^{\prime}_{d,even}(x)-F^{\prime}_{d,odd}(x)=[1-(1-F_{d,odd}(x))^{r}]^{d}-[1-(1-F_{d,even}(x))^{r}]^{d}\geq
0,$

where the inequality comes from the fact that $F_{d,even}\leq F_{d,odd}$ by
Corollary 12. So for any fixed $x\in[0,1]$,

$F_{d,even}(x)=F_{d,even}(0)+\int^{x}_{0}F^{\prime}_{d,even}(t)dt\geq
F_{d,odd}(0)+\int^{x}_{0}F^{\prime}_{d,odd}(t)dt=F_{d,odd}(x).$

This combined with the inequality $F_{d,even}\leq F_{d,odd}$, implies
$F_{d,even}=F_{d,odd}$. This completes the proof of the existence of
$F_{d}(x)$. Now consider equations (19) and (20), let $h\rightarrow\infty$ and
then use the Dominated Convergence Theorem [10], we get the desired
differential equations. ∎

######  Lemma 16.

For any integer $d\geq 3$, let $G_{d}(x)=1-F_{d-1}(x)$, then $G_{d}(x)$
satisfies the following equation:

$1-\sum_{n\geq 0}\binom{n+d-2}{d-2}\frac{G_{d}(x)^{rn+1}}{rn+1}=x.$ (26)

###### Proof.

By equation (24), we have

$G_{d}(x)=\int_{x}^{1}(1-G_{d}(t)^{r})^{d-1}dt.$

Taking derivatives on both sides, we have

$G_{d}^{\prime}(x)=-(1-G_{d}(x)^{r})^{d-1}.$

Let $H_{d}(x)=\sum_{n\geq 0}\binom{n+d-2}{d-2}\frac{x^{rn+1}}{rn+1}$, it is
not hard to check that $H_{d}^{\prime}(x)=\frac{1}{(1-x^{r})^{d-1}}$. So the
equation above is equivalent to

$\left(H_{d}\left(G_{d}(x)\right)\right)^{\prime}=-1.$

Solving this equation, we obtain

$\sum_{n\geq 0}\binom{n+d-2}{d-2}\frac{G_{d}(x)^{rn+1}}{rn+1}=-x+C$

Let $x=1$, we have $0=-1+C$, which implies $C=1$. This completes the proof. ∎

######  Lemma 17.

For any integer $d\geq 3$, let $\tilde{G}_{d}(x)=1-\tilde{F}_{d}(x)$, then we
have the following equation:

$\tilde{G}_{d}(x)=G_{d}(x)-\frac{G_{d}(x)^{r+1}}{r+1}$ (27)

###### Proof.

By equation (25),

$\tilde{G}_{d}(x)=\int^{1}_{x}(1-G_{d}(t)^{r})^{d}dt$

Consider changing the variable in the integral by letting $u=G_{d}(t)$. By
equation (24), not hard to see $dt=-\frac{du}{(1-u^{r})^{d-1}}$. Hence,

$\tilde{G}_{d}(x)=-\int^{G_{d}(1)}_{G_{d}(x)}(1-u^{r})du=G_{d}(x)-\frac{G_{d}(x)^{r+1}}{r+1}$

∎

Now we are ready to prove Theorem 4.

###### Proof of Theorem 4.

Applying inequality (23), we have

$\displaystyle|\frac{\mathbb{E}[|\mathcal{I}(G)|]}{n}-\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]|$
$\displaystyle\leq\frac{1}{n}\sum_{v\in
V(G)}|\mathbb{P}[v\in\mathcal{I}(G)]-\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]|$
$\displaystyle\leq\frac{d(d-1)^{h_{0}}}{r\prod_{k=1}^{h_{0}+1}(k+\frac{1}{r})}$

Note that this inequality holds for all $h\geq h_{0}+1$. Let
$h\rightarrow\infty$, we have

$|\frac{\mathbb{E}[|\mathcal{I}(G)|]}{n}-\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]}|\leq\frac{d(d-1)^{h_{0}}}{r\prod_{k=1}^{h_{0}+1}(k+\frac{1}{r})}.$

Let
$f(d,r)=\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}(\tilde{T}(d,h))]}=\tilde{G}_{d}(0)$,
then we have the required inequality (13). Let
$u(d,r)=\lim_{h\rightarrow\infty}{\mathbb{P}[\gamma\in\mathcal{I}({T}(d-1,h))]}=G_{d}(0)$.
By Lemma 16, we know that $u(d,r)$ satisfy equation (10). By Lemma 17, we have

$f(d,r)=\tilde{G}_{d}(0)=G_{d}(0)-\frac{G_{d}(0)^{r+1}}{r+1}=u(d,r)-\frac{u(d,r)^{r+1}}{r+1}.$

This completes the proof. ∎

##  4 Proof of Theorem 5

In section 2, we notice that vertices that are far away from each other are
very likely “independent”. More accurately, if two vertices $u$,$v$ are far
away from each other, then the indicator of the event that $u$ is selected and
the indicator of the event that $v$ is selected by the greedy algorithm have
small covariance. This phenomenon can also be used to give an upper bound for
the variance of the algorithm.

######  Lemma 18.

For any integers $r\geq 1$ and $d\geq 2$, let $G$ be an $(r+1)$-uniform linear
hypergraph on $n$ vertices with maximum degree $d$, then the variance
satisfies:

$\mathrm{Var}[{\mathcal{I}(G)}]\leq{3d^{2}r^{2}e^{r^{2}(d-1)^{3}}}n.$ (28)

###### Proof.

Let $V(G)=\\{v_{1},v_{2},\dots,v_{n}\\}$, $X_{i}=I(v_{i}\in\mathcal{I}(G))$.
Then

$\displaystyle\mathrm{Var}(\mathcal{I}(G))$
$\displaystyle=\mathrm{Var}(\sum_{i=1}^{n}X_{i})$
$\displaystyle=\sum_{i=1}^{n}(\mathbb{E}[X_{i}^{2}]-\mathbb{E}[X_{i}]^{2})+\sum_{1\leq
i\not=j\leq n}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])$
$\displaystyle\leq n+\sum_{1\leq i\leq n}\sum_{\delta\geq 1}\sum_{v_{j}\in
N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}]),$

where the inequality uses the bound
$(\mathbb{E}[X_{i}^{2}]-\mathbb{E}[X_{i}]^{2})\leq 1$. For any $1\leq i\leq
n$, we consider the sum

$\sum_{\delta\geq 1}\sum_{v_{j}\in N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])$

First, for any $\delta\geq 3$, let $h=\lfloor\frac{\delta-3}{2}\rfloor$, and
let $A_{i,h}$ denote the event $\\{\mathcal{B}(v_{i})\not\subset
N_{h}(v_{i})\\}$, $A_{i,h}^{c}$ denote the complement of the event $A_{i,h}$,
that is $\\{\mathcal{B}(v_{i})\subset N_{h}(v_{i})\\}$. This event is only
determined by the weights of vertices in $N_{h+1}(v_{i})$. Notice that for
every $v_{j}\in N_{\delta}(v_{i})\backslash N_{\delta-1}(v_{i})$,
$N_{h+1}(v_{i})\cap N_{h+1}(v_{j})=\emptyset$. So $A_{i,h}^{c}$ and
$A_{j,h}^{c}$ are independent. Then we have,

$\displaystyle\mathbb{E}[X_{i}X_{j}]$
$\displaystyle=\mathbb{P}[v_{i}\in\mathcal{I}(G),v_{j}\in\mathcal{I}(G)]$
$\displaystyle=\mathbb{P}[v_{i}\in\mathcal{I}(G),v_{j}\in\mathcal{I}(G),A_{i,h}^{c}\cap
A_{j,h}^{c}]+\mathbb{P}[v_{i}\in\mathcal{I}(G),v_{j}\in\mathcal{I}(G),A_{i,h}\cup
A_{j,h}].$

By Lemma 6 and the independence between $A_{i,h}^{c}$ and $A_{j,h}^{c}$, we
have

$\displaystyle\mathbb{P}[v_{i}\in\mathcal{I}(G),v_{j}\in\mathcal{I}(G),A_{i,h}^{c}\cap
A_{j,h}^{c}]$
$\displaystyle=\mathbb{P}[v_{i}\in\mathcal{I}(\mathcal{B}(v_{i})),v_{j}\in\mathcal{I}(\mathcal{B}(v_{j})),A_{i,h}^{c}\cap
A_{j,h}^{c}]$
$\displaystyle=\mathbb{P}[v_{i}\in\mathcal{I}(\mathcal{B}(v_{i})),A_{i,h}^{c}]\mathbb{P}[v_{j}\in\mathcal{I}(\mathcal{B}(v_{j})),A_{j,h}^{c}]$
$\displaystyle\leq\mathbb{E}[X_{i}]\mathbb{E}[X_{j}].$

On the other hand, by Lemma 9

$\displaystyle\mathbb{P}[v_{i}\in\mathcal{I}(G),v_{j}\in\mathcal{I}(G),A_{i,h}\cup
A_{j,h}]$ $\displaystyle\leq\mathbb{P}[A_{i,h}]+\mathbb{P}[A_{j,h}]$
$\displaystyle\leq\frac{2d(d-1)^{h}}{r\prod_{k=1}^{h+1}(k+\frac{1}{r})}$

Hence,

$\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}]\leq\frac{2d(d-1)^{h}}{r\prod_{k=1}^{h+1}(k+\frac{1}{r})}$

Since $G$ has maximum degree $d$, we have $|N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})|\leq d(d-1)^{\delta-1}r^{\delta}$.
In particular, for odd integer $\delta\geq 3$, we have $\delta=2h+3$. So the
sum

$\displaystyle\sum_{odd\ \delta\geq 3}\sum_{v_{j}\in
N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])$
$\displaystyle\leq\sum_{h\geq
0}d(d-1)^{2h+2}r^{2h+3}\frac{2d(d-1)^{h}}{r(h+1)!}$
$\displaystyle=\frac{2d^{2}}{d-1}\sum_{h\geq 1}\frac{r^{2h}(d-1)^{3h}}{h!}$
$\displaystyle\leq 2d^{2}\sum_{h\geq 1}\frac{r^{2h}(d-1)^{3h}}{h!}$

For even integer $\delta\geq 3$, we have $\delta=2h+4$. So the sum

$\displaystyle\sum_{even\ \delta\geq 3}\sum_{v_{j}\in
N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])$
$\displaystyle\leq\sum_{h\geq
0}d(d-1)^{2h+3}r^{2h+4}\frac{2d(d-1)^{h}}{r(h+1)!}$
$\displaystyle=2d^{2}r\sum_{h\geq 1}\frac{r^{2h}(d-1)^{3h}}{h!}$

For $1\leq\delta\leq 2$, use the bound
$\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}]\leq 1$, we have

$\sum_{1\leq\delta\leq 2}\sum_{v_{j}\in N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])\leq
2d^{2}r^{2}$

Combine the three inequalities above, we have

$\sum_{\delta\geq 1}\sum_{v_{j}\in N_{\delta}(v_{i})\backslash
N_{\delta-1}(v_{i})}(\mathbb{E}[X_{i}X_{j}]-\mathbb{E}[X_{i}]\mathbb{E}[X_{j}])\leq
2d^{2}r^{2}e^{r^{2}(d-1)^{3}}$

So the variance

$\mathrm{Var}(\mathcal{I}(G))\leq n+2d^{2}r^{2}e^{r^{2}(d-1)^{3}}n\leq
3d^{2}r^{2}e^{r^{2}(d-1)^{3}}n$

∎

###### Proof of Theorem 5.

By Lemma 18, we know that for fix $d$ and $r$, there exist a constant $c$ such
that $\mathrm{Var}(\mathcal{I}(G))<cn$. Hence, by Chebyshev’s Inequality we
have

$\mathbb{P}[||\mathcal{I}(G)|-\mathbb{E}[|\mathcal{I}(G)|]|>\sqrt{n}b(n)]\leq\frac{\mathrm{Var}(|\mathcal{I}(G)|)}{b(n)^{2}n}\rightarrow
0,\ \text{as $n\rightarrow\infty$}.$

∎

## Appendix A

We first collect some real number inequalities:

######  Proposition 19.

Let $n,r,d$ be positive integers. Then

$1$. |  For $x\geq 0$,  $\int_{0}^{x}e^{t^{r}}dt=\sum_{n\geq 0}\frac{x^{rn+1}}{n!(rn+1)}$ (29)
---|---
$2$. |  For $n\leq\sqrt{d}$,  $\Bigl{(}1+\frac{n}{d}\Bigr{)}^{n}<e^{\frac{n^{2}}{d}}<e$ (30)
$3$. |  For $y\geq 0$,  $\Bigl{(}\frac{y}{n}\Bigr{)}^{n}\leq e^{\frac{y}{e}}$ (31)

Let
$u_{d}=\lim_{h\rightarrow\infty}\mathbb{P}[\gamma\in\mathcal{I}(T(d,h))]=u(d+1,r)$.
Note that $u_{d}$ can be viewed as the probability of the root of
$T(d,\infty)$ being selected by the greedy algorithm, while $f(d,r)$ can be
viewed as the probability of the root of $\tilde{T}(d,\infty)$ being selected
by the greedy algorithm.

######  Proposition 20.

$f(d,r)\sim(\frac{\log d}{rd})^{\frac{1}{r}}$ as $d\rightarrow\infty$.

###### Proof.

Let $g(d,u)=\sum_{n\geq 0}\binom{n+d-1}{n}\frac{u^{rn+1}}{rn+1}$. It is not
hard to see that $g$ is increasing with respect to $u$. By Lemma 16, we have
$g(d,u_{d})=1$. Now for any $\epsilon>0$, let
$u=((\frac{1}{r})^{\frac{1}{r}}+\epsilon)(\frac{\log d}{d})^{\frac{1}{r}}$, we
have

$\displaystyle g(d,u)$ $\displaystyle\geq\sum_{n\geq
0}\frac{d^{n}}{n!}\frac{u^{rn+1}}{rn+1}$
$\displaystyle=d^{-\frac{1}{r}}\sum_{n\geq
0}\frac{(ud^{\frac{1}{r}})^{rn+1}}{n!(rn+1)}$
$\displaystyle=d^{-\frac{1}{r}}\int_{0}^{ud^{\frac{1}{r}}}e^{t^{r}}dt$ (by 29)
$\displaystyle>d^{-\frac{1}{r}}\int_{(\log
d)^{\frac{1}{r}}(\frac{1}{r})^{\frac{1}{r}}}^{(\log
d)^{\frac{1}{r}}[(\frac{1}{r})^{\frac{1}{r}}+\epsilon]}e^{t^{r}}dt$
$\displaystyle>d^{-\frac{1}{r}}(\epsilon(\log d)^{\frac{1}{r}})e^{\frac{\log
d}{r}}$ $\displaystyle=\epsilon(\log d)^{\frac{1}{r}}.$

This means that $g(d,u)\rightarrow\infty$ as $d\rightarrow\infty$, hence
$u_{d}<[(\frac{1}{r})^{\frac{1}{r}}+\epsilon](\frac{\log d}{d})^{\frac{1}{r}}$
when $d$ is large enough.
On the other hand, for any $\epsilon>0$, let $u=c(\frac{\log
d}{d})^{\frac{1}{r}}$, where $c=(\frac{1}{r}-\epsilon)^{\frac{1}{r}}$, we have

$\displaystyle g(d,u)$ $\displaystyle\leq\sum_{n\geq
0}\left(\frac{e(n+d)}{n}\right)^{n}\frac{u^{rn+1}}{rn+1}$
$\displaystyle=\sum_{n\geq
0}\frac{u}{rn+1}\left(\frac{e}{n}+\frac{e}{d}\right)^{n}(c^{r}\log d)^{n}$

When $n\geq 4c^{r}e\log d$, and $d$ is large enough, we have

$\displaystyle\sum_{n\geq 4c^{r}e\log
d}\frac{u}{rn+1}\left(\frac{e}{n}+\frac{e}{d}\right)^{n}(c^{r}\log d)^{n}$
$\displaystyle\leq u\sum_{n\geq 4c^{r}e\log d}\left(\frac{2e}{4c^{r}e\log
d}\right)^{n}(c^{r}\log d)^{n}$ $\displaystyle=u\sum_{n\geq 4c^{r}e\log
d}\left(\frac{1}{2}\right)^{n}$ $\displaystyle<c\left(\frac{\log
d}{d}\right)^{\frac{1}{r}}\rightarrow 0\ as\ d\rightarrow\infty.$

When $n<4c^{r}e\log d$, and $d$ is large enough, we have

$\displaystyle\sum_{n<4c^{r}e\log
d}\frac{u}{rn+1}\left(\frac{e}{n}+\frac{e}{d}\right)^{n}(c^{r}\log d)^{n}$
$\displaystyle<u\sum_{n<4c^{r}e\log
d}\left(1+\frac{n}{d}\right)^{n}\left(\frac{c^{r}e\log d}{n}\right)^{n}$
$\displaystyle<ue\sum_{n<4c^{r}e\log d}\left(\frac{c^{r}e\log
d}{n}\right)^{n}$ (by 30) $\displaystyle<c\left(\frac{\log
d}{d}\right)^{\frac{1}{r}}e(4c^{r}e\log d)e^{c^{r}\log d}$ (by 31)
$\displaystyle=4e^{2}c^{r+1}(\log d)^{\frac{r+1}{r}}d^{-\epsilon}\rightarrow
0\ as\ d\rightarrow\infty.$

This means that $g(d,u)\rightarrow 0$ as $d\rightarrow\infty$, hence
$u_{d}>(\frac{1}{r}-\epsilon)^{\frac{1}{r}}(\frac{\log d}{d})^{\frac{1}{r}}$
when $d$ is large enough.
These estimates imply that $u_{d}\sim(\frac{\log d}{rd})^{\frac{1}{r}}$, hence
$u_{d}\rightarrow 0$ as $d\rightarrow\infty$. Recall that by Theorem 4,

$f(d,r)=u(d,r)-\frac{u(d,r)^{r+1}}{r+1}=u_{d-1}-\frac{u_{d-1}^{r+1}}{r+1}$

Therefore, $f(d,r)\sim(\frac{\log d}{rd})^{\frac{1}{r}}$ as
$d\rightarrow\infty$. ∎

##  5 Acknowledgements

We would like to thank Patrick Bennett and Deepak Bal for some helpful
comments on simplifying the formulation of the main theorem. We would also
like to thank the anonymous referees for their careful reading of the paper
and useful suggestions.

## References

  * [1] M. Ajtai, J. Komlós, J. Pintz, J. Spencer, E. Szemerédi, Extremal uncrowded hypergraphs. J. Combin. Theory Ser. A, 32, 321-335, (1982)
  * [2] M. Ajtai, J. Komlós and E. Szemerédi, A note on Ramsey numbers. J. Combin. Theory Ser. A, 29, 354-360, (1980)
  * [3] N. Alon and J. H. Spencer, The probabilistic method. John Wiley & Sons, (2016)
  * [4] Y. Caro, New results on the independence number. Technical Report, Tel Aviv University, (1979)
  * [5] Y. Caro and Z. Tuza, Improved lower bounds on k-independence. J. Graph Theory, 15: 99-107, (1991)
  * [6] R. A. Duke, H. Lefmann, and V. Rödl, On uncrowded hypergraphs. Random Structures & Algorithms 6, 2-3, 209–212, (1995)
  * [7] K. Dutta, D. Mubayi, C. R. Subramanian, New lower bounds for the independence number of sparse graphs and hypergraphs. SIAM J. Discrete Math., vol. 26, no. 3, 1134-1147, Aug. (2012)
  * [8] D. Gamarnik and D. Goldberg, Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections. Combinatorics, Probability and Computing, v.19 n.1, 61-85, January (2010)
  * [9] J. Lauer and N. C.Wormald, Large independent sets in regular graphs of large girth. J. Comb. Theory, Ser. B 97 999-1009, (2007)
  * [10] W. Rudin, Principles of mathematical analysis. McGraw-Hill, (1976)
  * [11] G. N. Sárközy, Cycles in Hypergraphs. https://web.cs.wpi.edu/ gsarkozy/Cikkek/Rio08.pdf
  * [12] J. B. Shearer, A note on the independence number of triangle-free graphs. Discrete Math., 46, 83-87, (1983)
  * [13] J. B. Shearer, A note on the independence number of triangle-free graphs II. J. Combinatorial Theory (Series B) 53, 300-307, (1991)
  * [14] P. Turán, On an extremal problem in graph theory. Matematikai és Fizikai Lapok, 48, 436-452, (1941)
  * [15] V.K. Wei, A lower bound on the stability number of a simple graph. Bell Laboratories Technical Memorandum, 81-11217-9, (1981)