Generating functions for the Bernstein polynomials: A unified approach to
deriving identities for the Bernstein basis functions

Yilmaz Simsek

Department of Mathematics, Faculty of Science University of Akdeniz TR-07058
Antalya, Turkey

E-mail<EMAIL_ADDRESS>

Abstract

> The main aim of this paper is to provide a unified approach to deriving
> identities for the Bernstein polynomials using a novel generating function.
> We derive various functional equations and differential equations using this
> generating function. Using these equations, we give new proofs both for a
> recursive definition of the Bernstein basis functions and for derivatives of
> the $n$th degree Bernstein polynomials. We also find some new identities and
> properties for the Bernstein basis functions. Furthermore, we discuss
> analytic representations for the generalized Bernstein polynomials through
> the binomial or Newton distribution and Poisson distribution with mean and
> variance. Using this novel generating function, we also derive an identity
> which represents a pointwise orthogonality relation for the Bernstein basis
> functions. Finally, by using the mean and the variance, we generalize Szasz-
> Mirakjan type basis functions.

2010 Mathematics Subject Classification. 14F10, 12D10, 26C05, 26C10, 30B40,
30C15.

Key Words and Phrases. Bernstein polynomials; generating function; Szasz-
Mirakjan basis functions; Bezier curves; Binomial distribution; Poisson
distribution.

##  1\. Introduction and main definition

The Bernstein polynomials have many applications in approximations of
functions, in statistics, in numerical analysis, in $p$-adic analysis and in
the solution of differential equations. It is also well-known that in Computer
Aided Geometric Design polynomials are often expressed in terms of the
Bernstein basis functions.

Many of the known identities for the Bernstein basis functions are currently
derived in an ad hoc fashion, using either the binomial theorem, the binomial
distribution, tricky algebraic manipulations or blossoming. The main purpose
of this work is to construct novel generating functions for the Bernstein
polynomials. Using these novel generating functions, we develop a unify
approach both to standard and to new identities for the Bernstein polynomials.

The following definition gives us generating functions for the Bernstein basis
functions:

######  Definition 1.

Let $a$ and $b$ be nonnegative real parameters with $a\neq b$. Let $m$ a be
positive integer and let $x\in\left[a,b\right]$. Then the Bernstein basis
functions $\mathbb{Y}_{k}^{n}(x;a,b,m)$ are defined by means of the following
generating function:

$\displaystyle f_{\mathbb{Y},k}(x,t;a,b,m)$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{\infty}\sum_{l=0}^{k}\left(\begin{array}[]{c}j+m-1\\\
j\end{array}\right)(-1)^{k-l}\frac{t^{k}x^{l}a^{j+k-l}b^{-m-j}e^{(b-x)t}}{l!(k-l)!}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!},$

where $t\in\mathbb{C}$ and $0^{j}=\left\\{\begin{array}[]{cc}0&\text{if }j\neq
0,\\\ 1&\text{if }j=0.\end{array}\right.$

The remainder of this study is organized as follows:

Section 2: We find many functional equations and differential equations of
this novel generating function. Using these equations, many properties of the
Bernstein basis functions can be determined. For instance, we give new proofs
of the recursive definition of the Bernstein basis functions as well as a
novel derivation for the two term formula for the derivatives of the $n$th
degree Bernstein basis functions. We also prove many other properties of the
Bernstein basis functions via functional equations.

Jetter and Stöckler [9] proved an identity for multivariate Bernstein
polynomials on a simplex, which is considered a pointwise orthogonality
relation. The integral version of this identity provides a new representation
for the polynomial basis dual to the Bernstein basis. An identity for the
reproducing kernel is used to define quasi-interpolants of arbitrary order. As
an application of the identity of Jetter and Stöckler, Abel and Li [1] gave
Proposition 1, in Section 3. Their method is based on generating functions,
which reveals the general structure of the identity. As an applications of
Proposition 1 they derive generating functions for the Baskakov basis
functions and the Szasz-Mirakjan basis functions. Using Eq-(2.7) in Section 2,
they exhibit a special case of the identity of Jetter and Stöckler for the
Bernstein basis functions. In Section 3; we give relations between the
Bernstein basis functions, the binomial distribution and the Poisson
distribution. Using the Poisson distribution, we give generating functions for
the Szasz-Mirakjan type basis functions. By using Abel and Li’s [1] method,
and applying our generating functions to Proposition 1, we derive identities
which give pointwise orthogonality relations for the Bernstein polynomials and
the Szasz-Mirakjan type basis functions.

##  2\. Unified approach to deriving new proofs of the identities and
properties for the Bernstein polynomials

The Bernstein polynomials and related polynomials have been studied and
defined in many different ways, for examples by $q$-series, complex functions,
$p$-adic Volkenborn integrals and many algorithms.

In this section, we provide fundamental properties of the Bernstein basis
functions and their generating functions. We introduce some functional
equations and differential equations of the novel generating functions for the
Bernstein basis functions. We also give new proofs of some well known
properties of the Bernstein basis functions via functional equations and
differential equations.

###  2.1. Generating Functions

We now modify (1) as follows:

By the negative binomial theorem, we have

$\frac{1}{b^{m}(1-\frac{a}{b})^{m}}=\frac{1}{b^{m}}\sum_{j=0}^{\infty}\left(\begin{array}[]{c}j+m-1\\\
j\end{array}\right)a^{j}b^{-m-j}.$ (2.1)

Substituting (2.1) into (1), we get

$\displaystyle f_{\mathbb{Y},k}(x,t;a,b,m)$ $\displaystyle=$
$\displaystyle\frac{t^{k}e^{(b-x)t}}{(b-a)^{m}k!}\sum_{l=0}^{k}\left(\begin{array}[]{c}k\\\
l\end{array}\right)(-1)^{k-l}x^{l}a^{k-l}$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!}.$

Thus we obtain the following novel generating function, which is a
modification of (1):

$\displaystyle f_{\mathbb{Y},k}(x,t;a,b,m)$ $\displaystyle=$
$\displaystyle\frac{t^{k}\left(x-a\right)^{k}e^{(b-x)t}}{(b-a)^{m}k!}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!}.$

######  Remark 1.

If we set $a=0$ and $b=1$ in (2.1), we obtain a result given by Simsek and
Acikgoz [13] and Acikgoz and Arici [2]:

$\frac{(xt)^{k}}{k!}e^{(1-x)t}=\sum_{n=0}^{\infty}B_{k}^{n}(x)\frac{t^{n}}{n!},$

so that, obviously;

$\mathbb{Y}_{k}^{n}(x;0,1,m)=B_{k}^{n}(x),$

where $B_{k}^{n}(x)$ denote the Bernstein polynomials.

By using the Taylor series for $e^{(b-x)t}$ in (2.1), we get

$\frac{(x-a)^{k}}{(b-a)^{m}k!}\sum_{n=0}^{\infty}\mathbb{(}b-x\mathbb{)}^{n}\frac{t^{n+k}}{n!}=\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!}.$

Comparing the coefficients of $t^{k}$ on the both sides of the above equation,
we arrive at the following theorem:

######  Theorem 1.

Let $a$ and $b$ be nonnegative real parameters with $a\neq b$. Let $m$ be a
positive integer and let $x\in\left[a,b\right]$. Let $k$ and $n$ be non-
negative integers with $n\geq k$. Then

$\mathbb{Y}_{k}^{n}(x;a,b,m)=\left(\begin{array}[]{c}n\\\
k\end{array}\right)\frac{\left(x-a\right)^{k}(b-x)^{n-k}}{(b-a)^{m}},$ (2.4)

where $k=0$, $1$,$\cdots$, $n$, and $\left(\begin{array}[]{c}n\\\
k\end{array}\right)=\frac{n!}{k!(n-k)!}$.

######  Remark 2.

For $m=n$, the Bernstein basis functions of degree $n$ are defined by (2.4).

######  Remark 3.

In the special case when $m=n$, Theorem 1 immediately yields the corresponding
well known results concerning the Bernstein basis functions $B_{k}^{n}(x)$
that appears for example in Goldman [5, p. 384, Eq.(24.6)] and cf. [3]:

$\mathbb{Y}_{k}^{n}(x;a,b,n)=B_{k}^{n}(x;a,b)=\left(\begin{array}[]{c}n\\\
k\end{array}\right)\frac{\left(x-a\right)^{k}(b-x)^{n-k}}{(b-a)^{n}},$

where $k=0$, $1$,$\cdots$, $n$ and $x\in[a,b]$. One can easily see that

$B_{k}^{n}(x)=\left(\begin{array}[]{c}n\\\
k\end{array}\right)x^{k}(1-x)^{n-k},$ (2.5)

where $k=0,1,\cdots,n$ and $x\in[0,1]$ cf. [1]-[13]. In [5], Goldman gives
many properties of the Bernstein polynomials $B_{k}^{n}(x,a,b)$. The functions
$B_{0}^{n}(x,a,b),\cdots,B_{n}^{n}(x,a,b)$ are called the Bernstein basis
functions. Goldman [5], in Chapter 26, shows that the Bernstein basis
functions form a basis for the polynomials of degree $n$. The Bezier curve
$B(t)$ with control points $P_{0}$,$\cdots$, $P_{n}$ is defined as follows:

$B(t)=\sum_{k=0}^{n}P_{k}B_{k}^{n}(x,a,b)\text{ cf.
\cite[cite]{[\@@bibref{}{GoldmanBOOK}{}{}]}.}$

######  Remark 4.

By using (2.4), we have

$\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!}=\sum_{n=0}^{\infty}\left(\begin{array}[]{c}n\\\
k\end{array}\right)\frac{\left(x-a\right)^{k}(b-x)^{n-k}}{(b-a)^{m}}\frac{t^{n}}{n!}.$

From this equation, we obtain

$\sum_{n=0}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n}}{n!}=\frac{\left(x-a\right)^{k}t^{k}}{k!(b-a)^{m}}\sum_{n=k}^{\infty}(b-x)^{n-k}\frac{t^{n-k}}{\left(n-k\right)!}.$

The series on the right hand side is the Taylor series for $e^{(b-x)t}$; thus
we arrive at (2.1).

Substituting $m=n$ in (2.4), we now give another well-known generating
function for the Bernstein basis functions:

$\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\mathbb{Y}_{k}^{n}(x;a,b,n)t^{k}\right)\frac{z^{n}}{n!}=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\left(\begin{array}[]{c}n\\\
k\end{array}\right)t^{k}\left(\frac{x-a}{b-a}\right)^{k}\left(\frac{b-x}{b-a}\right)^{n-k}\right)\frac{z^{n}}{n!}.$

By using the Cauchy product in the above equation, we have

$\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\mathbb{Y}_{k}^{n}(x;a,b,n)t^{k}\right)\frac{z^{n}}{n!}=\sum_{n=0}^{\infty}\left(t\frac{x-a}{b-a}\right)\frac{z^{n}}{n!}\sum_{n=0}^{\infty}\left(\frac{b-x}{b-a}\right)\frac{z^{n}}{n!}.$

From this equation, we find that

$\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\mathbb{Y}_{k}^{n}(x;a,b,n)t^{k}\right)\frac{z^{n}}{n!}=e^{z\left(\frac{b-x}{b-a}+t\frac{x-a}{b-a}\right)}.$

After some elementary calculations in the above relation, we arrive at the
following generating function for the Bernstein basis functions:

$\sum_{k=0}^{n}\mathbb{Y}_{k}^{n}(x;a,b,n)t^{k}=\left(\frac{b-x}{b-a}+t\frac{x-a}{b-a}\right)^{n}.$
(2.6)

######  Remark 5.

If we set $a=0$, $b=1$ and $m=n$ in (2.6), then we have

$\sum_{k=0}^{n}B_{k}^{n}(x)t^{k}=\left(\left(1-x\right)+tx\right)^{n}.$ (2.7)

This generating functions is given by Goldman [7]-[6, Chapter 5, pages
299-306]. Goldman [7]-[6, Chapter 5, pages 299-306] also constructs the
following generating functions the univariate and bivariate Bernstein basis
functions:

$\sum_{k=0}^{n}B_{k}^{n}(x)e^{ky}=\left(\left(1-x\right)+te^{y}\right)^{n},$
$\sum_{i+j+k=n}B_{i,j,k}^{n}(s,t)x^{i}y^{j}=\left(\left(1-s-t\right)+sx+ty\right)^{n},$

where

$B_{i,j,k}^{n}(s,t)=\left(\begin{array}[]{c}n\\\
ijk\end{array}\right)s^{i}t^{j}\left(1-s-t\right)^{k}\text{ and
}\left(\begin{array}[]{c}n\\\ ijk\end{array}\right)=\frac{n!}{i!j!k!}$

and

$\sum_{i+j+k=n}B_{i,j,k}^{n}(s,t)e^{ix}e^{jy}=\left(\left(1-s-t\right)+se^{x}+te^{y}\right)^{n}.$

Below are some well-known properties of the Bernstein basis functions:

Non-negative property:

$\mathbb{Y}_{k}^{n}(x;a,b,m)\geq 0\text{, for }0\leq a\leq x\leq b.$ (2.8)

Symmetry property:

$\mathbb{Y}_{k}^{n}(x;a,b,m)=\mathbb{Y}_{n-k}^{n}(b+a-x;a,b,m).$ (2.9)

Corner values:

$\mathbb{Y}_{k}^{n}(a;a,b,m)=\left\\{\begin{array}[]{cc}0&\text{if }k\neq
0,\\\ 1&\text{if }k=0,\end{array}\right.$ (2.10)

and

$\mathbb{Y}_{k}^{n}(b;a,b,m)=\left\\{\begin{array}[]{cc}0&\text{if }k\neq
n,\\\ 1&\text{if }k=n.\end{array}\right.$ (2.11)

Alternating sum:

Substituting $m=n$ in (2.4), we get

$\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}(-1)^{k}\mathbb{Y}_{k}^{n}(x;a,b,n)\right)\frac{t^{n}}{n!}=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}\frac{\left(\frac{a-x}{b-a}\right)^{k}\left(\frac{b-x}{b-a}\right)^{n-k}}{k!(n-k)!}\right)t^{n}.$

By using the Cauchy product in the above equation, we have

$\sum_{n=0}^{\infty}\left(\sum_{k=0}^{n}(-1)^{k}\mathbb{Y}_{k}^{n}(x;a,b,n)\right)\frac{t^{n}}{n!}=e^{\left(\frac{a+b-2x}{b-a}\right)t}.$

From this relation, we arrive at the following formula for the alternating
sum.

$\sum_{k=0}^{n}(-1)^{k}\mathbb{Y}_{k}^{n}(x;a,b,n)=\left(\frac{a+b-2x}{b-a}\right)^{n}.$
(2.12)

######  Remark 6.

If we set $a=0$, $b=1$ and $m=n$, then Eq-(2.8)-Eq-(2.12) reduce to Goldman’s
results [7]-[6, Chapter 5, pages 299-306]. In [7] and [6, Chapter 5, pages
299-306], Goldman also gives many identities and properties for the univariate
and bivariate Bernstein basis functions, for example boundary values, maximum
values, partitions of unity, representation of monomials, representation in
terms of monomials, conversion to monomial form, linear independence,
Descartes’ law of sign, discrete convolution, unimodality, subdivision,
directional derivatives, integrals, Marsden identities, De Boor-Fix formulas,
and the other properties.

A Bernstein polynomial $\mathcal{P}(x,a,b,m)$ is a polynomial represented in
the Bernstein basis functions:

$\mathcal{P}(x,a,b,m)=\sum_{k=0}^{n}c_{k}^{n}\mathbb{Y}_{k}^{n}(x;a,b,m).$
(2.13)

######  Remark 7.

If we set $a=0$, $b=1$ and $m=n$ (2.13), then we have

$P(x)=\sum_{k=0}^{n}c_{k}^{n}B_{k}^{n}(x)$

cf. [4].

By using (2.1), we obtain the following functional equation:

$f_{\mathbb{Y},k_{1}}(x,t;a,b,m_{1})f_{\mathbb{Y},k_{2}}(x,t;a,b,m_{2})=\frac{\left(\begin{array}[]{c}k_{1}+k_{2}\\\
k_{1}\end{array}\right)}{2^{k_{1}+k_{2}}}f_{\mathbb{Y},k_{1}+k_{2}}(x,2t;a,b,m_{1}+m_{2}),$

where

$\left(\begin{array}[]{c}k_{1}+k_{2}\\\
k_{1}\end{array}\right)=\left(\begin{array}[]{c}k_{1}+k_{2}\\\
k_{2}\end{array}\right)=\frac{\left(k_{1}+k_{2}\right)!}{k_{1}!k_{2}!}.$

By using the definition of the novel generating function
$f_{\mathbb{Y},k}(x,t;a,b,m)$ in the preceding equation, we get

$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k_{1}}^{n}(x;a,b,m_{1})\frac{t^{n}}{n!}\sum_{n=0}^{\infty}\mathbb{Y}_{k_{2}}^{n}(x;a,b,m_{2})\frac{t^{n}}{n!}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k_{1}+k_{2}}^{n}(x;a,b,m_{1}+m_{2})\frac{2^{n-k_{1}-k_{2}}\left(k_{1}+k_{2}\right)!t^{n}}{n!k_{1}!k_{2}!}.$

And using the Cauchy product in this equation, we have

$\displaystyle\sum_{n=0}^{\infty}\left(\mathop{\displaystyle\sum}\limits_{j=0}^{n}\left(\begin{array}[]{c}n\\\
j\end{array}\right)\mathbb{Y}_{k_{1}}^{j}(x;a,b,m_{1})\mathbb{Y}_{k_{2}}^{n-j}(x;a,b,m_{2})\right)\frac{t^{n}}{n!}$
$\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}\mathbb{Y}_{k_{1}+k_{2}}^{n}(x;a,b,m_{1}+m_{2})\frac{2^{n-k_{1}-k_{2}}\left(k_{1}+k_{2}\right)!t^{n}}{n!k_{1}!k_{2}!}.$

Comparing the coefficients of $\frac{t^{n}}{n!}$ on the both sides of the
above equation, we arrive at the following theorem:

######  Theorem 2.

Let $m_{1}$ and $m_{2}$ be integers. Then the following identity holds:

$\mathbb{Y}_{k_{1}+k_{2}}^{n}(x;a,b,m_{1}+m_{2})=\frac{2^{k_{1}+k_{2}-n}k_{1}!k_{2}!}{\left(k_{1}+k_{2}\right)!}\mathop{\displaystyle\sum}\limits_{j=0}^{n}\left(\begin{array}[]{c}n\\\
j\end{array}\right)\mathbb{Y}_{k_{1}}^{j}(x;a,b,m_{1})\mathbb{Y}_{k_{2}}^{n-j}(x;a,b,m_{2}).$

Observe that if we set $a=0$ and $b=1$, then we have

$B_{k_{1}+k_{2}}^{n}(x)=\frac{2^{k_{1}+k_{2}-n}k_{1}!k_{2}!}{\left(k_{1}+k_{2}\right)!}\mathop{\displaystyle\sum}\limits_{j=0}^{n}\left(\begin{array}[]{c}n\\\
j\end{array}\right)B_{k_{1}}^{j}(x)B_{k_{2}}^{n-j}(x).$

Note that many new identities can be found via functional equations for the
novel generating functions of the Bernstein basis functions. We derive some
functional equations and identities related to the generating functions and
the Bernstein basis functions in the remainder of this section.

###  2.2. Subdivision property

The following functional equation of the novel generating functions is
fundamental to driving the subdivision property for the Bernstein basis
functions.

Let we us define

$f_{\mathbb{Y},j}(xy,t;a,b,n)=f_{\mathbb{Y},j}\left(x,t\left(\frac{y-a}{b-a}\right);a,b,n\right)e^{t\left(\frac{b-y}{b-a}\right)}.$
(2.15)

From this generating function, we have the following theorem:

######  Theorem 3.

Let $a\leq yx\leq b$. Then the following identity holds:

$\mathbb{Y}_{j}^{n}(xy;a,b,n)=\mathop{\displaystyle\sum}\limits_{k=j}^{n}\mathbb{Y}_{j}^{k}(x;a,b,k)\mathbb{Y}_{k}^{n}(y;a,b,n-k).$

###### Proof.

By equations (2.1) and (2.15), we obtain

$\displaystyle\sum_{n=j}^{\infty}\mathbb{Y}_{j}^{n}(xy;a,b,n)\frac{t^{n}}{n!}$
$\displaystyle=$
$\displaystyle\left(\sum_{n=0}^{\infty}\mathbb{Y}_{j}^{n}(x;a,b,n)\left(\frac{y-a}{b-a}\right)^{n}\frac{t^{n}}{n!}\right)\left(\sum_{n=0}^{\infty}\frac{\left(\frac{b-y}{b-a}\right)^{n}t^{n}}{n!}\right).$

Using the Cauchy product in this equation, we get

$\sum_{n=j}^{\infty}\mathbb{Y}_{j}^{n}(xy;a,b,m)\frac{t^{n}}{n!}=\sum_{n=j}^{\infty}\left(\mathop{\displaystyle\sum}\limits_{k=j}^{n}\mathbb{Y}_{j}^{n}(x;a,b,k)\frac{\left(\frac{y-a}{b-a}\right)^{k}\left(\frac{b-y}{b-a}\right)^{n-k}}{k!\left(n-k\right)!}\right)t^{n}.$

Substituting (2.4) into the above equation then after some elementary
manipulations, we arrive at the desired result.

######  Remark 8.

Substituting $a=0$, $b=1$ and $m=n$ into Theorem 3, we have

$B_{j}^{n}(xy)=\mathop{\displaystyle\sum}\limits_{k=j}^{n}B_{j}^{k}(x)B_{k}^{n}(y).$
(2.16)

The above identity is essentially the subdivision property for the Bernstein
basis functions. This identity is a bit tricky to prove with algebraic
manipulations.

######  Remark 9.

Goldman [7]-[6, Chapter 5, pages 299-306] proves equation (2.16) with
algebraic manipulations. He also proves the following subdivision properties:

$B_{j}^{n}(\left(1-y\right)x+y)=\mathop{\displaystyle\sum}\limits_{k=0}^{j}B_{j-k}^{n-k}(x)B_{k}^{n}(y),$

and

$B_{j}^{n}(\left(1-y\right)x+yz)=\mathop{\displaystyle\sum}\limits_{k=0}^{n}\left(\mathop{\displaystyle\sum}\limits_{p+q=j}B_{p}^{n-k}(x)B_{q}^{k}(z)\right)B_{k}^{n}(y)$

for the others see cf. [7]-[6, Chapter 5, pages 299-306].

###  2.3. Differentiating the generating function

In this section we give higher order derivatives of the Bernstein basis
functions by differentiating the generating function in (2.1) with respect to
$x$. Using Leibnitz’s formula for the $l$th derivative, with respect to $x$,
of the product $f_{\mathbb{Y},k}(x,t;a,b,m)$ of two functions
$g(t,x;a,b)=\frac{t^{k}\left(x-a\right)^{k}}{(b-a)^{m}k!}$ with $a\neq b$ and
$h(t,x;b)=e^{(b-x)t}$, we obtain the following higher order partial derivative
equation:

$\frac{\partial^{l}f_{\mathbb{Y},k}(x,t;a,b,m)}{\partial
x^{l}}=\mathop{\displaystyle\sum}\limits_{j=0}^{l}\left(\begin{array}[]{c}l\\\
j\end{array}\right)\left(\frac{\partial^{j}g(t,x;a,b)}{\partial
x^{j}}\right)\left(\frac{\partial^{l-j}h(t,x;b)}{\partial x^{l-j}}\right).$

From this equation, we arrive at the following theorem:

######  Theorem 4.

Let $l$ be a non-negative integer. Then

$\frac{\partial^{l}f_{\mathbb{Y},k}(x,t;a,b,m)}{\partial
x^{l}}=\mathop{\displaystyle\sum}\limits_{j=0}^{l}\left(\begin{array}[]{c}l\\\
j\end{array}\right)(-1)^{l-j}\frac{t^{l}}{(b-a)^{j}}f_{\mathbb{Y},k-j}(x,t;a,b,m-j).$

By using Theorem 4, we obtain higher order derivatives of the Bernstein basis
functions by the following theorem:

######  Theorem 5.

Let $a$ and $b$ be nonnegative real parameters with $a\neq b$. Let $m$ be a
positive integer and let $x\in\left[a,b\right]$. Let $k$, $l$ and $n$ be
nonnegative integers with $n\geq k$. Then

$\frac{d^{l}\mathbb{Y}_{k}^{n}(x;a,b,m)}{dx^{l}}=\mathop{\displaystyle\sum}\limits_{j=0}^{l}(-1)^{l-j}\left(\begin{array}[]{c}n\\\
n-l,l-j,j\end{array}\right)\frac{l!}{(b-a)^{j}}\mathbb{Y}_{k-j}^{n-l}(x;a,b,m-j),$

where

$\left(\begin{array}[]{c}n\\\ x,y,z\end{array}\right)=\frac{n!}{x!y!z!}\text{,
with }n=x+y+z.$

######  Remark 10.

Substituting $a=0$, $b=1$ and $m=n$ into Theorem 5, we have

$\frac{d^{l}B_{k}^{n}(x)}{dx^{l}}=\mathop{\displaystyle\sum}\limits_{j=0}^{l}(-1)^{l-j}\left(\begin{array}[]{c}n\\\
n-l,l-j,j\end{array}\right)l!B_{k-j}^{n-l}(x),$

or

$\frac{d^{l}B_{k}^{n}(x)}{dx^{l}}=\frac{n!}{(n-l)!}\mathop{\displaystyle\sum}\limits_{j=0}^{l}(-1)^{l-j}\left(\begin{array}[]{c}n\\\
j\end{array}\right)B_{k-j}^{n-l}(x),$

cf. ([7], [6, Chapter 5, pages 299-306]).

Substituting $l=1$ into Theorem 5, we arrive at the following corollary:

######  Corollary 1.

Let $a$ and $b$ be nonnegative real parameters with $a\neq b$. Let $m$ be a
positive integer and let $x\in\left[a,b\right]$. Let $k$ and $n$ be
nonnegative integers with $n\geq k$. Then

$\frac{d}{dx}\mathbb{Y}_{k}^{n}(x;a,b,m)=n\left(\frac{\mathbb{Y}_{k-1}^{n-1}(x;a,b,m-1)-\mathbb{Y}_{k}^{n-1}(x;a,b,m-1)}{b-a}\right).$

######  Remark 11.

By setting $m=n$ in Corollary 1, we arrive at the known known result recorded
by Goldman [5]:

$\frac{d}{dx}B_{k}^{n}(x;a,b)=n\left(\frac{B_{k-1}^{n-1}(x;a,b)-B_{k}^{n-1}(x;a,b)}{b-a}\right).$

######  Remark 12.

One can also see the following special case of Theorem 1 when $a=0$ and $b=1$:

$\frac{d}{dx}B_{k}^{n}(x)=n\left(B_{k-1}^{n-1}(x)-B_{k}^{n-1}(x)\right)$

cf. [1]-[13].

###  2.4. Recurrence Relation

In this section by using higher order derivatives of the novel generating
function with respect to $t$, we derive a partial differential equation. Using
this equation, we shall give a new proof of the recurrence relation for the
Bernstein basis functions.

Differentiating Eq-(1) with respect to $t$, we prove a recurrence relation for
the polynomials $\mathbb{Y}_{k}^{n}(x;a,b,m)$. This recurrence relation can
also be obtained from Eq-(2.4). By using Leibnitz’s formula for the $v$th
derivative, with respect to $t$, of the product $f_{\mathbb{Y},k}(x,t;a,b,m)$
of two function $g(t,x;a,b)=\frac{t^{k}\left(x-a\right)^{k}}{(b-a)^{m}k!}$
with $a\neq b$ and $h(t,x;b)=e^{(b-x)t}$, we obtain another higher order
partial differential equation as follows:

$\frac{\partial^{v}f_{\mathbb{Y},k}(x,t;a,b,m)}{\partial
t^{v}}=\mathop{\displaystyle\sum}\limits_{j=0}^{v}\left(\begin{array}[]{c}v\\\
j\end{array}\right)\left(\frac{\partial^{j}g(t,x;a,b)}{\partial
t^{j}}\right)\left(\frac{\partial^{v-j}h(t,x;b)}{\partial t^{v-j}}\right).$

From the above equation, we have the following theorem:

######  Theorem 6.

Let $v$ be an integer number. Then

$\frac{\partial^{v}f_{\mathbb{Y},k}(x,t;a,b,m)}{\partial
t^{v}}=\mathop{\displaystyle\sum}\limits_{j=0}^{v}(b-a)^{v-j}\mathbb{Y}_{j}^{v}(x;a,b,v)f_{\mathbb{Y},k-j}(x,t;a,b,m-j),$

where $f_{\mathbb{Y},k}(x,t;a,b,m)$ and $\mathbb{Y}_{j}^{v}(x;a,b,v)$ are
defined in (2.1) and (2.4), respectively.

Using definition (2.1) and (2.4) in Theorem 6, we obtain a recurrence relation
for the Bernstein basis functions by the following theorem:

######  Theorem 7.

Let $a$ and $b$ be nonnegative real parameters with $a\neq b$. Let $m$ be a
positive integer and let $x\in\left[a,b\right]$. Let $k$, $v$ and $n$ be
nonnegative integers with $n\geq k$. Then

$\mathbb{Y}_{k}^{n}(x;a,b,m)=\mathop{\displaystyle\sum}\limits_{j=0}^{v}(b-a)^{v-j}\mathbb{Y}_{j}^{v}(x;a,b,v)\mathbb{Y}_{k-j}^{n-v}(x;a,b,m-j).$

######  Remark 13.

Substituting $a=0$ and $b=1$ into Theorem 7, we obtain the following result:

$B_{k}^{n}(x)=\mathop{\displaystyle\sum}\limits_{j=0}^{v}B_{j}^{v}(x)B_{k-j}^{n-v}(x).$

Substituting $v=1$ into Theorem 7, we arrive at the following corollary:

######  Corollary 2.

(Recurrence Relation) Let $a$ and $b$ be nonnegative real parameters with
$a\neq b$. Let $m$ be a positive integer and let $x\in\left[a,b\right]$. Let
$k$ and $n$ be nonnegative integers with $n\geq k$. Then

$\displaystyle\mathbb{Y}_{k}^{n}(x;a,b,m)$ $\displaystyle=$
$\displaystyle\frac{x-a}{b-a}\mathbb{Y}_{k-1}^{n-1}(x;a,b,m-1)$
$\displaystyle+\frac{b-x}{b-a}\mathbb{Y}_{k}^{n-1}(x;a,b,m-1).$

######  Remark 14.

Differentiating equation (1) with respect to $t$, we also get

$\displaystyle\frac{x-a}{b-a}f_{\mathbb{Y},k-1}(x,t;a,b,m-1)+\frac{b-x}{b-a}f_{\mathbb{Y},k}(x,t;a,b,m-1)$
$\displaystyle=$
$\displaystyle\sum_{n=1}^{\infty}\mathbb{Y}_{k}^{n}(x;a,b,m)\frac{t^{n-1}}{\left(n-1\right)!}.$

From this equation, one can also obtain Corollary 2.

######  Remark 15.

By setting $a=0$ and $b=1$ in (2), one obtains the following relation:

$B_{k}^{n}(x)=(1-x)B_{k}^{n-1}(x)+xB_{k-1}^{n-1}(x).$

###  2.5. Multiplication and division by powers of $(\frac{x-a}{b-a})^{d}$ and
$(\frac{b-x}{b-a})^{d}$

In [4], Buse and Goldman present much background material on computations with
Bernstein polynomials. They provide formulas for multiplication and division
of Bernstein polynomials by powers of $x$ and $1-x$ and for degree elevation
of Bernstein polynomials. Our method is similar to that of Buse and Goldman’s
[4]. In this section we find two functional equations. Using these equations,
we also give new proofs of both the multiplication and division properties for
the Bernstein polynomials.

By using the generating function in (1), we provide formulas for multiplying
Bernstein polynomials by powers of $(\frac{x-a}{b-a})^{d}$ and
$(\frac{b-x}{b-a})^{d}$ and for degree elevation of the Bernstein polynomials.

Using (2.1), we obtain the following functional equation:

$(\frac{x-a}{b-a})^{d}f_{\mathbb{Y},k}(x,t;a,b,n)=\frac{(k+d)!}{k!t^{d}}f_{\mathbb{Y},k}(x,t;a,b,n).$

After elementary manipulations in this equation, we get

$(\frac{x-a}{b-a})^{d}\mathbb{Y}_{k}^{n}(x;a,b,n)=\frac{n!(k+d)!}{k!(n+d)!}\mathbb{Y}_{k+d}^{n+d}(x;a,b,n+d).$
(2.18)

Substituting $d=1$, we have

$(\frac{x-a}{b-a})\mathbb{Y}_{k}^{n}(x;a,b,n)=\frac{k+1}{n+1}\mathbb{Y}_{k+1}^{n+1}(x;a,b,n+1).$
(2.19)

######  Remark 16.

Substituting $a=0$ and $b=1$ into (2.19), we have

$xB_{k}^{n}(x)=\frac{k+1}{n+1}B_{k+1}^{n+1}(x).$

The above relation can also be proved by (2.5) cf. [4].

Similarly, using (2.4), we obtain

$(\frac{b-x}{b-a})^{d}\mathbb{Y}_{k}^{n}(x;a,b,n)=\frac{n!(n+d-k)!}{\left(n+d\right)!(n-k)!}\mathbb{Y}_{k}^{n+d}(x;a,b,n+d).$

Substituting $d=1$ into the above equation, we have

$(\frac{b-x}{b-a})\mathbb{Y}_{k}^{n}(x;a,b,n)=\frac{n+1-k}{n+1}\mathbb{Y}_{k}^{n+1}(x;a,b,n+1).$
(2.20)

Consequently, by the same method as in [4], if we have (2.13), then

$(\frac{x-a}{b-a})^{d}\mathcal{P}(x,a,b)=\sum_{k=0}^{n}c_{k}^{n}\frac{n!(k+d)!}{k!(n+d)!}\mathbb{Y}_{k+d}^{n+d}(x;a,b,n+d),$
(2.21)

and

$(\frac{b-x}{b-a})^{d}\mathcal{P}(x,a,b)=\sum_{k=0}^{n}c_{k}^{n}\frac{n!(n+d-k)!}{\left(n+d\right)!(n-k)!}\mathbb{Y}_{k}^{n+d}(x;a,b,n+d).$
(2.22)

We now consider division properties. We assume that (2.13) holds and that we
are given an integer $j>0$. Since $(\frac{x-a}{b-a})^{j}$ divides
$\mathbb{Y}_{k}^{n}(x;a,b,n)$ for all $k\geq j$, it follows that
$(\frac{x-a}{b-a})^{j}$ divides $\mathcal{P}(x,a,b)$. Similarly, using (2.1),
we obtain the following functional equation:

$\frac{f_{\mathbb{Y},k}(x,t;a,b,n)}{(\frac{x-a}{b-a})^{j}}=\frac{(k-f)!t^{j}}{k!}f_{\mathbb{Y},k-j}(x,t;a,b,n-j).$

For $k\geq j$, from the above equation, we have

$\frac{\mathbb{Y}_{k}^{n}(x;a,b,n)}{(\frac{x-a}{b-a})^{j}}=\frac{n!(k-j)!}{k!(n-j)!}\mathbb{Y}_{k-j}^{n-j}(x;a,b,n-j).$

By a calculation similar to the calculation in [4], for $j\leq n-k$, we have

$\frac{\mathbb{Y}_{k}^{n}(x;a,b,n)}{(\frac{b-x}{b-a})^{j}}=\frac{n!(n-j-k)!}{\left(n-k\right)!(n-j)!}\mathbb{Y}_{k}^{n-j}(x;a,b,n-j).$

Therefore

$\frac{\mathcal{P}(x,a,b)}{(\frac{x-a}{b-a})^{j}}=\sum_{k=j}^{n}c_{k}^{n}\frac{n!(k-j)!}{k!(n-j)!}\mathbb{Y}_{k-j}^{n-j}(x;a,b,n-j),$
(2.23)

and

$\frac{\mathcal{P}(x,a,b)}{(\frac{b-x}{b-a})^{j}}=\sum_{k=0}^{n-j}c_{k}^{n}\frac{n!(n-j-k)!}{\left(n-k\right)!(n-j)!}\mathbb{Y}_{k}^{n-j}(x;a,b,n-j).$
(2.24)

###  2.6. Degree elevation

According to Buse and Goldman [4], given a polynomial represented in the
univariate Bernstein basis of degree $n$, degree elevation computes
representations of the same polynomial in the univariate Bernstein bases of
degree greater than $n$. Degree elevation allows us to add two or more
Bernstein polynomials which are not represented in the same degree Bernstein
basis functions.

Adding (2.19) and (2.20), we obtain the degree elevation formula for the
Bernstein basis functions:

$\mathbb{Y}_{k}^{n}(x;a,b,n)=\frac{k+1}{n+1}\mathbb{Y}_{k+1}^{n+1}(x;a,b,n+1)+\frac{n+1-k}{n+1}\mathbb{Y}_{k}^{n+1}(x;a,b,n+1).$

Substituting $d=1$ into (2.22), and adding these two equations gives the
following degree elevation formula for the Bernstein polynomials:

$\mathcal{P}(x,a,b)=\sum_{k=0}^{n}\left(\frac{k}{n+1}c_{k-1}^{n}+\frac{n+1-k}{\left(n+1\right)}c_{k}^{n}\right)\mathbb{Y}_{k}^{n+1}(x;a,b,n+1),$
(2.25)

where

$c_{k}^{n+1}=\frac{k}{n+1}c_{k-1}^{n}+\frac{n+1-k}{\left(n+1\right)}c_{k}^{n}.$

######  Remark 17.

If we set $a=0$ and $b=1$, then (2.25) reduces to Eq-(2.5) in [4, p. 853].

##  3\. Relation between the generating functions
$f_{\mathbb{Y},k}(x,t;a,b,m)$, Poisson distribution and Szasz-Mirakjan type
basis functions

The identity of Jetter and Stöckler represents a pointwise orthogonality
relation for the multivariate Bernstein polynomials on a simplex. This
identity give us a new representation for the dual basis which can be used to
construct general quasi-interpolant operators cf. (See, for details, [9],
[1]). As an application of the generating functions for the basis functions to
the identity of Jetter and Stöckler, Abel and Li [1] proved Proposition 1,
which is given in this section. Applying our generating functions to
Proposition 1, we give pointwise orthogonality relations for the Bernstein
polynomials and the Szasz-Mirakjan basis functions.

In this section, we give relations between the Bernstein basis functions, the
binomial distribution and the Poisson distribution. First we we consider the
generalized binomial or Newton distribution (probability function). Suppose
that $0\leq\frac{x-a}{b-a}\leq 1$ and $0\leq\frac{b-x}{b-a}\leq 1$. Set

$\mathbb{Y}_{k}^{n}(x;a,b,n)=\left(\begin{array}[]{c}n\\\
k\end{array}\right)\left(\frac{x-a}{b-a}\right)^{k}\left(\frac{b-x}{b-a}\right)^{n-k}.$
(3.1)

From the above definition, one can see that

$\sum_{k=0}^{n}\mathbb{Y}_{k}^{n}(x;a,b,n)=1.$

######  Remark 18.

If we set $a=0$ and $b=1$, then (3.1) reduces to

$\mathbb{Y}_{k}^{n}(x;0,1,n)=\left(\begin{array}[]{c}n\\\
k\end{array}\right)x^{k}(1-x)^{n-k}$

which is the binomial or Newton distribution (probabilities) function. If
$0\leq x\leq 1$ is the probability of an event $E$, then
$\mathbb{Y}_{k}^{n}(x;0,1,n)$ is the probability that $E$ will occur exactly
$k$ times in $n$ independent trials cf. [11].

Expected value or mean and variance of $\mathbb{Y}_{k}^{n}(x;a,b,n)$ are given
by

$\mu=\sum_{k=0}^{n}k\mathbb{Y}_{k}^{n}(x;a,b,n)=n\left(\frac{x-a}{b-a}\right),$

and

$\sigma^{2}=\sum_{k=0}^{n}k^{2}\mathbb{Y}_{k}^{n}(x;a,b,n)-\mu^{2}=\frac{n\left(x-a\right)\left(b-x\right)}{\left(b-a\right)^{2}}.$

If we let $n\rightarrow\infty$ in (3.1), then we arrive at the well-known
Poisson distribution function:

$\mathbb{Y}_{k}^{n}(\frac{b-a}{n}\mu+a;a,b,n)\rightarrow\frac{\mu^{k}e^{-\mu}}{k!}.$
(3.2)

The following proposition is proved by Abel and Li [1, p. 300, Proposition 3]:

######  Proposition 1.

Let the system $\\{f_{n}(x)\\}$ of functions be defined by the generating
function

$A_{t}(x)=\mathop{\displaystyle\sum}\limits_{n=0}^{\infty}f_{n}(x)t^{n}.$

If there exists a sequence $w_{k}=w_{k}(x)$ such that

$\mathop{\displaystyle\sum}\limits_{k=0}^{\infty}w_{k}\mathcal{D}^{k}A_{t}(x)\mathcal{D}^{k}A_{z}(x)=A_{tz}(x)$

with $\mathcal{D}=\frac{d}{dx}$, then for $i,j=0,1,\cdots$,

$\mathop{\displaystyle\sum}\limits_{k=0}^{\infty}w_{k}\mathcal{D}^{k}f_{i}(x)\mathcal{D}^{k}f_{j}(x)=\delta_{i,j}f_{i}(x).$

As an application of Proposition 1, Abel and Li [1] use the generating
function in Eq-(2.7) for the Bernstein basis functions. They also use
generating functions for the Szasz-Mirakjan basis functions and Baskakov basis
functions.

In this section, we apply our novel generating functions to Proposition 1,
which give pointwise orthogonality relations for the Bernstein polynomials and
the Szasz-Mirakjan type basis functions, respectively.

As applications of Proposition 1, we give the following examples:

######  Example 1.

For given $n$ and $k$, the Bernstein basis functions

$f_{i}(x,n;a,b)=\mathbb{Y}_{i}^{n}(x;a,b,n)=\left(\begin{array}[]{c}n\\\
i\end{array}\right)\left(\frac{x-a}{b-a}\right)^{k}(\frac{b-x}{b-a})^{n-k}$

are generated by the function in (2.1), that is

$A_{t}(x)=\frac{t^{k}\left(x-a\right)^{k}e^{(b-x)t}}{(b-a)^{n}k!}=\mathop{\displaystyle\sum}\limits_{i=0}^{\infty}\frac{f_{i}(x,n;a,b)}{i!}t^{i}.$

It is easy to check that Proposition 1 holds with
$w_{k}=w_{k}(x)=\mathbb{Y}_{k}^{n}(x;a,b,n)$.

######  Example 2.

Using (3.2), for $i\geq 0$, we generalize the Szasz-Mirakjan type basis
functions as follows

$f_{i}(x,n;a,b)=\frac{(n\frac{x-a}{b-a})^{i}e^{-n\frac{x-a}{b-a}}}{i!},$

where $a$ and $b$ are nonnegative real parameters with $a\neq b$, $n$ is a
positive integer and $x\in\left[a,b\right]$. The functions $f_{i}(x,n;a,b)$
are generated by

$A_{t}(x)=\exp\left((t-1)n\left(\frac{x-a}{b-a}\right)\right)=\mathop{\displaystyle\sum}\limits_{i=0}^{\infty}f_{i}(x,n;a,b)t^{i},$

where $\exp(x)=e^{x}$. In this case, Proposition 1 holds with
$w_{k}=w_{k}(x)=\frac{\left(\frac{x-a}{b-a}\right)^{k}}{n^{k}k!}$. Therefore,
we have

$\mathop{\displaystyle\sum}\limits_{k=0}^{\infty}\frac{\left(\frac{x-a}{b-a}\right)^{k}}{n^{k}k!}\mathcal{D}^{k}f_{i}(x,n;a,b)\mathcal{D}^{k}f_{i}(x,n;a,b)=\delta_{i,j}f_{i}(x,n;a,b).$

######  Remark 19.

If $a=0$ and $b=1$ in Example 2, then we arrive at the Szasz-Mirakjan basis
functions which are given in [1, p. 300, Example 2].

######  Acknowledgement 1.

The author would like to thank Professor Ronald Goldman (Rice University,
Houston, USA) for his very valuable comments, criticisms and for his very
useful suggestions on this present paper.

The present investigation was supported by the Scientific Research Project
Administration of Akdeniz University.

## References

  * [1] U. Abel and Z. Li, A new proof of an identity of Jetter and Stöckler for multivariate Bernstein polynomials, Computer Aided Geometric Design, 23(3) (2006), 297-301.
  * [2] M. Acikgoz and S. Araci, On generating function of the Bernstein polynomials, Numerical Analysis and Applied Mathematics, Amer. Inst. Phys. Conf. Proc. CP1281, (2010) 1141-1143.
  * [3] S. N. Bernstein, Démonstration du théorème de Weierstrass fondée sur la calcul des probabilités. Comm. Soc. Math. Charkow Sér. 2 t. 13, 1-2 (1912-1913).
  * [4] L. Busé and R. Goldman, Division algorithms for Bernstein polynomials, Computer Aided Geometric Design, 25(9) (2008), 850-865.
  * [5] R. Goldman, An Integrated Introduction to Computer Graphics and Geometric Modeling, CRC Press, Taylor and Francis, New York, 2009.
  * [6] R. Goldman, Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling, Morgan Kaufmann Publishers, Academic Press, San Diego, 2002.
  * [7] R. Goldman, Identities for the Univariate and Bivariate Bernstein Basis Functions, Graphics Gems V, edited by Alan Paeth, Academic Press, (1995), 149-162.
  * [8] L. C. Jang, W.-J. Kim and Y. Simsek, A study on the $p$-adic integral representation on $\mathbb{Z}p$ associated with Bernstein and Bernoulli polynomials, Advances in Difference Equations 2010 (2010), Article ID 163217, 6pp.
  * [9] K. Jetter and J. Stöckler, An identity for multivariate Bernstein poynomials, Computer Aided Geometric Design, 20 (2003), 563-577.
  * [10] M. S. Kim, D. Kim, and T. Kim, On the $q$-Euler numbers related to modified $q$-Bernstein polynomials, Abstr. Appl. Anal. 2010, Art. ID 952384, 15 pages, doi:10.1155/2010/952384, arXiv:1007.3317v1.
  * [11] G. G. Lorentz, Bernstein Polynomials, Chelsea Pub. Comp. New York, N. Y. 1986.
  * [12] G. M. Phillips, Interpolation and approximation by polynomials, CMS Books in Mathematics/ Ouvrages de Mathématiques de la SMC, 14. Springer-Verlag, New York, (2003).
  * [13] Y. Simsek and M. Acikgoz, A new generating function of ($q$-) Bernstein-type polynomials and their interpolation function, Abstract and Applied Analysis, vol. 2010, Article ID 769095, 12 pages, 2010. doi:10.1155/2010/769095.


# Spanning trees in pseudorandom graphs via sorting networks

Joseph Hyde Department of Mathematics and Statistics, University of Victoria,
3800 Finnerty Road, Victoria, BC V8P 5C2, Canada. Email<EMAIL_ADDRESS>Natasha Morrison Research supported by NSERC Discovery Grant RGPIN-2021-02511
and NSERC Early Career Supplement DGECR-2021-00047. Department of Mathematics
and Statistics, University of Victoria, 3800 Finnerty Road, Victoria, BC V8P
5C2, Canada. Email<EMAIL_ADDRESS>Alp Müyesser Department of Mathematics,
University College London, WC1E 6BT, UK. Email<EMAIL_ADDRESS>Matías Pavez-Signé Supported by ANID Basal Grant CMM FB210005 and by the
European Research Council (ERC) under the European Union Horizon 2020 research
and innovation programme (grant agreement No. 947978) while the author was
affiliated to the University of Warwick. Centro de Modelamiento Matemático
(CNRS IRL2807), Universidad de Chile, Santiago, Chile. Email:
<EMAIL_ADDRESS>
###### Abstract

We show that $(n,d,\lambda)$-graphs with $\lambda=O(d/\log^{3}n)$ are
universal with respect to all bounded degree spanning trees. This
significantly improves upon the previous best bound due to Han and Yang of the
form $\lambda=d/\exp{(O(\sqrt{\log n}))}$, and makes progress towards a
problem of Alon, Krivelevich, and Sudakov from 2007.

Our proof relies on the existence of sorting networks of logarithmic depth, as
given by a celebrated construction of Ajtai, Komlós and Szemerédi. Using this
construction, we show that the classical vertex-disjoint paths problem can be
solved for a set of vertices fixed in advance.

##  1 Introduction

How pseudorandom does a graph need to be before it contains a certain spanning
subgraph? This problem is not very well understood, especially in comparison
to its purely random analogue concerning “thresholds” in $\mathbb{G}(n,p)$
(see, e.g. [4]). For example, the best possible condition that forces an
$(n,d,\lambda)$-graph to contain a Hamilton cycle is not known, where an
$(n,d,\lambda)$-graph is an $n$-vertex $d$-regular graph such that the second
largest eigenvalue (in absolute value) of the adjacency matrix is bounded
above by $\lambda$. The well-known expander mixing lemma states that the
smaller $\lambda$ is, the more pseudorandom an $(n,d,\lambda)$-graph becomes,
in the sense that the edges are more evenly distributed across the graph (we
refer the reader to [14] for a thorough exposition). Intuitively, the more
pseudorandom a graph is, the easier it becomes to find a target subgraph.
However, finding optimal conditions that force $(n,d,\lambda)$-graphs to
contain certain spanning subgraphs is notoriously difficult as, for instance,
the only cases that are fully understood are perfect matchings [14] and
triangle-factors [20].

Our main motivation in this paper is the following problem of Alon,
Krivelevich, and Sudakov [2] from 2007.

######  Question 1.1.

Is it true that for any $\Delta\in\mathbb{N}$, there exists a constant
$C=C(\Delta)$ such that any $(n,d,\lambda)$-graph with $\lambda\leq d/C$
contains every tree on $n$ vertices with maximum degree at most $\Delta$?

At the moment, a positive answer to this question seems to be out of reach.
Indeed, the best known bound on $\lambda$ that guarantees a Hamilton path is
$\lambda\leq d/O(\log^{1/3}n)$ due to a recent result of Glock, Munhá Correia,
and Sudakov [6] (see also [13]). In the regime of Question 1.1 (when
$\lambda\simeq o(d)$), we only have results for restricted classes of trees.
Indeed, a recent result of the fourth author [22] shows that if $G$ is an
$(n,d,\lambda)$-graph with $\lambda\leq d/C$ for some large constant $C$, then
$G$ contains all $n$-vertex bounded degree trees with linearly many leaves.
For general bounded degree trees, Han and Yang [8] made some progress towards
a full answer to Question 1.1 by showing that the condition $\lambda\leq
d/\Delta^{O(\sqrt{\log n})}$ is sufficient. From now on, we say that a graph
is $\mathcal{T}(n,\Delta)$-universal if it contains every $n$-vertex tree with
maximum degree at most $\Delta$.

In this paper, we make another step towards a positive answer to Question 1.1.

######  Theorem 1.2.

For all $\Delta\in\mathbb{N}$, there exists a positive constant $C$ such that
the following holds. Every $(n,d,\lambda)$-graph with $\lambda\leq
d/C\log^{3}n$ is $\mathcal{T}(n,\Delta)$-universal.

Note that, up to polylogarithmic terms, our bound matches the best known bound
on $\lambda$ for guaranteeing the existence of Hamilton paths. Furthermore, as
with the result of Han and Yang, this result confirms the existence of
$\mathcal{T}(n,\Delta)$-universal graphs with arbitrarily large girth, thereby
addressing a problem of Johannsen, Krivelevich, and Samotij [10] (we refer the
reader to [8] for further details).

When proving a statement such as Theorem 1.2, the usual strategy is to combine
methods for embedding an almost-spanning tree with methods for turning an
almost spanning tree into a spanning tree. For example, if the tree has many
leaves, one can embed all of the tree except the leaves in some convenient
way, and then use Hall’s theorem in order to find a matching between the image
of the parents of leaves and the leftover vertices in the host graph to
complete the embedding. When the tree has few leaves, one typically uses
instead its (necessarily existing) path-like substructures to finish the
embedding. To achieve this, one needs to find a way to connect a given
collection of $\Theta(\frac{\lambda n}{d})$ pairs of vertices with vertex-
disjoint paths of length $O(\frac{d}{\lambda})$, while partitioning some
target set in the process. In his breakthrough work establishing the threshold
for the random graph $\mathbb{G}(n,p)$ to be
$\mathcal{T}(n,\Delta)$-universal, Montgomery [18] developed what became known
as the distributive absorption method in order to solve a suitable version of
this vertex-disjoint paths problem. Since then, this method has found numerous
applications for embedding spanning subgraphs (see, e.g. [19, 20]) and,
notably, Han and Yang [8] rely on this method to prove their aforementioned
result.

Our proof, on the other hand, does not rely on any absorption technique.
Instead, we take a new approach to address this problem in sparse pseudorandom
graphs, by carefully constructing a special graph which is based on the
existence of optimal sorting networks (as given by the celebrated result by
Ajtai, Komlós, and Szemerédi [1]) in combination with the rollback method to
embed trees into sparse expanders (which is based on an idea of Johannsen
[3]). This allows us to show that the vertex-disjoint paths problem (see [3])
in sparse expanders can be solved with a set of vertices fixed in advance (see
Lemma 2.3). We believe that this construction might be of independent
interest, and we include another application in Section 6 showing that sparse
pseudorandom graphs can be factorised111Given graphs $F$ and $G$, an
$F$-factor in $G$ is a collection of vertex-disjoint copies of $F$ covering
every vertex in $G$. into cycles of polylogarithmic length.

##  2 Proof overview

Our starting point is the above mentioned result due to the fourth author,
which states that if $\lambda\leq d/C$, for some large constant $C$, then an
$(n,d,\lambda)$-graph contains every bounded degree tree with
$\Omega(\frac{\lambda n}{d})$ leaves.

######  Theorem 2.1 ([22, Theorem 4.2]).

For all $\Delta\in\mathbb{N}$, there exist positive constants $C$ and $K$ such
that the following holds for all sufficiently large $d\in\mathbb{N}$. If $G$
is an $(n,d,\lambda)$-graph with $\lambda\leq d/C$, then $G$ contains a copy
of every $n$-vertex tree with maximum degree at most $\Delta$ and at least
$\frac{K\lambda n}{d}$ leaves.

For a graph $H$, say that a path $P\subset H$ is a bare path if all vertices
in $P$ have degree $2$ in $H$. The following well-known result of Krivelevich
[12] implies that trees with few leaves contain many bare paths.

######  Lemma 2.2.

Let $n,k,\ell\in\mathbb{N}$ and let $T$ be an $n$-vertex tree with at most
$\ell$ leaves. Then $T$ contains a collection of at least
$\frac{n}{k+1}-(2\ell-2)$ vertex-disjoint bare paths, each of length $k$.

Then, combining Theorem 2.1 and Lemma 2.2, we see that when proving Theorem
1.2 we need only concern ourselves with trees $T$ containing
$\Omega(n/\log^{3}n)$ bare paths, each of length $O(\log^{3}n)$ (see the proof
of Theorem 1.2 for the formal calculation). Once the internal vertices of the
bare paths are removed from $T$, the resulting forest, say $F$, is not
spanning anymore, in which case there are well-known results (see [5, 9]) that
allow us to find, in an expander graph, a copy of every almost spanning forest
with maximum degree at most $\Delta$. To complete the embedding of $T$, we
thus only need to find a collection of vertex-disjoint paths of length
$O(\log^{3}n)$ joining the image of the endpoints of the bare paths we just
removed from $T$, and moreover, while doing so, using all the leftover
vertices in $G$. What we would like to do is sequentially find perfect
matchings between $O(\log^{3}n)$ consecutive pairs of sets, each of size
$\Theta(n/\log^{3}n)$ (setting aside some random sets in the beginning and
using Lemma 3.6 can achieve this, for example). The union of these matchings
would then form a path-factor which corresponds to the desired collection of
bare paths. The problem with this argument is that the bare paths we need to
embed have designated endpoints, since we have already committed to an
embedding of the tree with the internal vertices of the bare paths removed.
That is, how can we be sure in the very small amount of our
$(n,d,\lambda)$-graph we have at the end of our embedding process that the
exact path-factor corresponding to the remaining bare paths exists? The next
lemma is designed to handle this complication (we refer the reader to Section
3 for the definitions of $m$-joined, $(D,m)$-extendable and $I(X)$).

######  Lemma 2.3.

There is an absolute constant
$C_{\ref{lemma:find_sorting_network_in_expander}}$ with the following
property. Let $1/n\ll 1/K\ll
1/C_{\ref{lemma:find_sorting_network_in_expander}}$, and let
$D,m\in\mathbb{N}$ satisfy $m\leq n/100D$ and $D\geq 100$. Let $G$ be an
$m$-joined graph on $n$ vertices which contains disjoint subsets
$V_{1},V_{2}\subseteq V(G)$ with $|V_{1}|=|V_{2}|\leq n/K\log^{3}n$, and set
$\ell:=\lfloor
C_{\ref{lemma:find_sorting_network_in_expander}}\log^{3}n\rfloor$. Suppose
that $I(V_{1}\cup V_{2})$ is $(D,m)$-extendable in $G$.

Then, there exists a $(D,m)$-extendable subgraph $S_{res}\subseteq G$ such
that for any bijection $\phi\colon V_{1}\to V_{2}$, there exists a
$P_{\ell}$-factor of $S_{res}$ where each copy of $P_{\ell}$ has as its
endpoints some $v\in V_{1}$ and $\phi(v)\in V_{2}$.

We remark that Lemma 2.3 can be used in $(n,d,\lambda)$ graphs with
$\lambda/d=O(1)$, and thus might have applications beyond those which we
consider in the current paper. We will return to this aspect in the concluding
remarks.

To prove Theorem 1.2, we proceed (roughly) as follows. We first use Lemma 2.3,
where $V_{1}$ and $V_{2}$ are two random subsets of size
$\Theta(n/\log^{3}n)$, getting a subgraph $S_{res}$ which we will use at the
end of the proof in order to complete the embedding of $T$. We then find a
copy of the forest $F$ (using Lemma 3.9) in $G\setminus V(S_{res})$. The next
step is to find a collection of consecutive matchings between $O(\log^{3}n)$
sets of size $\Theta(n/\log^{3}n)$, starting from the image of the endpoints
of the bare paths and ending at $V_{1}$ and $V_{2}$, respectively. We achieve
this by first picking pairwise disjoint random subsets
$V^{\prime}_{1},\ldots,V^{\prime}_{t}$, with $t=O(\log^{3}n)$ and
$|V^{\prime}_{i}|=\Theta(n/\log^{3}n)$ for all $i\in[t]$, so that every vertex
in the graph has many neighbours into each of those sets. Then, after $F$ is
embedded, we distribute all the leftover vertices into $\bigcup
V^{\prime}_{i}$ so that each $V_{i}^{\prime}$ has the same size. Using that
every vertex has good degree into each $V^{\prime}_{i}$, combined with the
expansion properties of $(n,d,\lambda)$-graphs, we can find a perfect matching
between $V^{\prime}_{i}$ and $V^{\prime}_{i+1}$ for each $1\leq i<t$ (see
Lemma 3.6). The union of these matchings will then give us a collection of
paths connecting, in some order, the image of the endpoints of the bare paths
we have previously removed with $V_{1}$ and $V_{2}$. Finally, we use the
property of $S_{res}$ to partition $V(S_{res})$ into paths of the same length,
connecting the vertices of $V_{1}$ and $V_{2}$ in whatever order we need to
finish the embedding of $T$.

Let us emphasise that the strength of Lemma 2.3 comes from the fact that
$S_{res}$ is fixed with respect to $V_{1}$ and $V_{2}$ only, and does not
depend on the choice of the bijection $\phi:V_{1}\to V_{2}$. It is worth
comparing Lemma 2.3 with [3, Theorem 2] due to Draganić, Krivelevich and
Nenadov, which has a similar statement, but the order of $S_{res}$ and $\phi$
is reversed in the quantification, making their statement weaker. On the other
hand, the result from [3] is quantitatively stronger than Lemma 2.3, in the
sense that it works for sets $V_{1}$ and $V_{2}$ of size as large as
$\Theta(n/\log n)$ (which is optimal as typically we cannot expect to find
paths of length much shorter than $\log n$ in sparse expanders). Getting
similar quantitative improvements for Lemma 2.3 would be interesting, as it
would immediately translate to improvements in the bounds we are obtaining for
Theorem 1.2. The $\log^{3}n$ factor in our bound comes from $S_{res}$ being
constructed from a sorting network of depth $O(\log n)$ where the comparison
gadgets are replaced with subgraphs of size $O(\log^{2}n)$ coming from Lemma
4.3.

Pushing our methods further to show that Theorem 1.2 holds under the weaker
hypothesis that $\lambda\leq d/\log^{1+o(1)}n$ seems challenging, but
possible. Going beyond this, on the other hand, would possibly require
entirely new ideas.

##  3 Preliminaries

###  3.1 Notation

For a graph $G$, let $V(G)$ and $E(G)$ denote the vertex set and edge set of
$G$, respectively, and write $|G|:=|V(G)|$. For a vertex $v\in V(G)$, let
$N(v)$ denote the neighbourhood of $v$ and, for a subset $U\subset V(G)$, let
$N(v,U):=N(v)\cap U$. We let $d(v):=|N(v)|$ denote the degree of $v$ and write
$d(v,U):=|N(v,U)|$ for the degree of $v$ into a subset $U\subset V(G)$. The
minimum degree of $G$ is denoted by $\delta(G)$, and we write $\Delta(G)$ for
the maximum degree of $G$. For $U\subset V(G)$, let $\Gamma(U):=\bigcup_{u\in
U}N(u)$ denote the neighbourhood of $U$ and let $N(U):=\Gamma(U)\setminus U$
be the external neighbourhood of $U$. If necessary, we will add subscripts to
denote which graph we are working with. For a subset $S\subseteq V(G)$, let
$G[S]$ denote the graph induced by $S$ and, given a subset $S^{\prime}\subset
V(G)\setminus S$, let $G[S,S^{\prime}]$ denote the bipartite graph with
bipartition $S\cup S^{\prime}$ and edges of the form $ss^{\prime}\in E(G)$
with $s\in S$ and $s^{\prime}\in S^{\prime}$, further letting
$e(S,S^{\prime})$ denote the number of edges in $G[S,S^{\prime}]$. We write
$I(S)$ for the edgeless subgraph with vertex set $S$, and
$G-S:=G[V(G)\setminus S]$.

A path $P$ in $G$ is a sequence of distinct vertices $P=v_{1}\ldots v_{t}$
such that $v_{i}v_{i+1}\in E(G)$ for each $1\leq i<t$, in which case we say
that $v_{1}$ and $v_{t}$ are the endpoints of $P$ and $v_{2},\ldots,v_{t-1}$
are the internal vertices of $P$. The length of $P$ is equal to its number of
edges. Given two distinct vertices $u,v\in V(G)$, a $(u,v)$-path is a path
whose endpoints are precisely $u$ and $v$. For a subgraph $H\subset G$ and an
edge $e\in E(G)$, we let $H+e$ denote the graph with edge set $E(H)\cup e$.
Moreover, if $P=v_{1}\ldots v_{t}$ is a path and we denote $P_{i}=v_{1}\ldots
v_{i}$ for $1\leq i\leq t$, then we define
$H+P_{i}:=(H+P_{i-1})+v_{i-1}v_{i}$.

For a positive integer $n$, we let $[n]=\\{1,\ldots,n\\}$ denote the set of
the first $n$ positive integers. Given real numbers $a,b,c$, we write $a=b\pm
c$ to denote that $b-c\leq a\leq b+c$. We use standard notation for
“hierarchies” of constants, writing $x\ll y$ to mean that there is a non-
decreasing function $f:(0,1]\rightarrow(0,1]$ such that all relevant
subsequent statements hold for $x\leq f(y)$. Hierarchies with multiple
constants are defined similarly. We omit rounding signs where they are not
crucial.

###  3.2 Concentration bounds

We need the following concentration bound, which is a simple corollary of a
result of McDiarmid (stated as Lemma 6.1 in [16]).

######  Lemma 3.1.

Let $n$ be sufficiently large and let $G$ be an $n$-vertex graph with
$\delta(G)\geq\log^{6}n$. Let $R$ be a uniformly random subset of $V(G)$ of
size $k\geq n/\log^{4}n$, and let $v\in V(G)$. Then,

$\mathbb{P}\left(d(v,R)=(1\pm 1/10)d(v)\cdot\tfrac{k}{n}\right)\geq
1-1/n^{2}.$

###  3.3 Properties of $(n,d,\lambda)$-graphs

The next three results are standard properties of $(n,d,\lambda)$-graphs (see
[14]).

######  Lemma 3.2.

Every $(n,d,\lambda)$-graph satisfies
$\lambda\geq\sqrt{d\cdot\frac{n-d}{n-1}}$.

######  Lemma 3.3 (Expander Mixing Lemma).

Let $G$ be an $(n,d,\lambda)$-graph. Then, for every pair of (not necessarily
disjoint) sets $A,B\subset V(G)$, we have

$\left|e(A,B)-\tfrac{d}{n}|A||B|\right|<\lambda\sqrt{|A||B|}.$

We say a graph $G$ is $m$-joined if $e(A,B)\geq 1$ for any disjoint sets
$A,B\subseteq V(G)$ with $|A|,|B|\geq m$.

######  Lemma 3.4.

Every $(n,d,\lambda)$-graph is $\frac{\lambda n}{d}$-joined.

The following result, which is a simple corollary of the expander mixing
lemma, will allow us to translate minimum degree conditions into an expansion
property for small sets.

######  Lemma 3.5.

Let $\mu,C,D,z>0$ and $n\in\mathbb{N}$ such that $\mu Cz>4D$, and let
$d\in\mathbb{N}$ and $\lambda>0$ satisfy $d/\lambda\geq C\log^{3}n$. Suppose
$G$ is an $(n,d,\lambda)$-graph which contains subsets $X,Y\subset V(G)$ such
that for every $v\in X$, $d(v,Y)\geq\mu dz/\log^{3}n$. Then, every subset
$S\subset X$ of size $|S|\leq\lambda n/d$ satisfies $|N(S)\cap Y|\geq D|S|$.

###### Proof.

Suppose that there exists a subset $S\subset X$ of size
$1\leq|S|\leq\frac{\lambda n}{d}$ such that $|N(S)\cap Y|<D|S|$. Let
$Z=N(S)\cap Y$. Lemma 3.3 implies that

$\frac{\mu dz}{\log^{3}n}|S|\leq
e(S,Z)\leq\frac{d}{n}|S||Z|+\lambda\sqrt{|S||Z|}\leq\lambda
D|S|+\lambda|S|\sqrt{D}.$

Then we have

$\frac{\mu dz}{\log^{3}n}\leq\lambda D+\lambda\sqrt{D}\leq 4\lambda D,$

which contradicts that $d/\lambda\geq C\log^{3}n$, as $\mu Cz>4D$. ∎

The last result that we need gives a sufficient condition to find perfect
matchings between small subsets of $(n,d,\lambda)$-graphs.

######  Lemma 3.6.

Let $1/C\ll\varepsilon\ll 1$ and let $n,d\in\mathbb{N}$, $n\geq 3$ and
$\lambda>0$ satisfy $d/\lambda\geq C\log^{3}n$. Suppose $G$ is an
$(n,d,\lambda)$-graph that contains disjoint subsets $A,B\subset V(G)$ with
$|A|=|B|$ such that $\delta(G[A,B])\geq\varepsilon d/2\log^{3}n$. Then,
$G[A,B]$ contains a perfect matching.

###### Proof.

As $\delta(G[A,B])\geq\varepsilon d/2\log^{3}n$ and $1/C\ll\varepsilon$, using
Lemma 3.5, with $z_{\ref{lemma:expansion2}}=1$, $D=2$, and
$\mu=\varepsilon/2$, we may add the following expansion properties:

  * •

for every subset $S\subset A$ with $|S|\leq\frac{\lambda n}{d}$, $|N(S)\cap
B|\geq 2|S|$, and

  * •

for every subset $S\subset B$ with $|S|\leq\frac{\lambda n}{d}$, $|N(S)\cap
A|\geq 2|S|$.

We will show that Hall’s matching criterion holds. For contradiction, suppose
that there exists a subset $S\subset A$ with $|N(S)\cap B|<|S|$. Clearly, we
have $|S|>\frac{\lambda n}{d}$. Then, by Lemma 3.4, $G[A,B]$ is $\frac{\lambda
n}{d}$-joined and thus

$|S|>|N(S)\cap B|\geq|B|-\tfrac{\lambda n}{d}.$ (1)

Letting $X=A\setminus S$ and $Y=B\setminus N(S)$, we have that
$|X|\leq|Y|\leq\frac{\lambda n}{d}$. Then using the expansion properties we
see that $|X|\geq|N(Y)\cap A|\geq 2|Y|$, a contradiction. Then, $G[A,B]$
satisfies Hall’s matching criterion and therefore $G[A,B]$ has a perfect
matching. ∎

###  3.4 The extendability/rollback method

All the results we cite below can be found in [18]. The first four are
typically described as the Friedman-Pippenger tree embedding technique,
subsequently developed by Haxell [9]. The basic idea is that a cleverly
defined inductive hypothesis (Definition 3.7) can be maintained while
extending an embedding by the addition of a leaf.

An idea that can be traced back to Johannsen states that this process is in
fact reversible, meaning that $(D,m)$-extendability – defined below – can also
be maintained by the removal of leaves (this is called a ‘rollback’ in [3]).
Using this idea, one can efficiently find paths between prescribed vertices in
an extendable subgraph, by iteratively exploring the neighbourhoods of the
respective vertices until we find an overlap, and then rolling back by
removing all the unused vertices in the process (see Lemma 3.10 for the
precise statement).

######  Definition 3.7.

Let $D,m\in\mathbb{N}$ with $D\geq 3$. Let $G$ be a graph and let $S\subset G$
be a subgraph with $\Delta(S)\leq D$. We say that $S$ is $(D,m)$-extendable if
for all $U\subset V(G)$ with $1\leq|U|\leq 2m$ we have

$|\Gamma_{G}(U)\setminus V(S)|\geq(D-1)|U|-\sum_{u\in U\cap
V(S)}(d_{S}(u)-1).$ (2)

The following result says that it is enough to control the external
neighbourhood of small sets in order to verify extendability.

######  Proposition 3.8.

Let $D,m\in\mathbb{N}$ with $D\geq 3$. Let $G$ be a graph and let $S\subset G$
be a subgraph with $\Delta(S)\leq D$. If for all $U\subset V(G)$ with
$1\leq|U|\leq 2m$ we have

$|N_{G}(U)\setminus V(S)|\geq D|U|,$

then $S$ is $(D,m)$-extendable in $G$.

The following result states that we can embed nearly spanning trees in an
extendable way.

######  Lemma 3.9 ([18, Corollary 3.7]).

Let $D,m\in\mathbb{N}$ with $D\geq 3$, and let $G$ be an $m$-joined graph. Let
$T$ be a tree with $\Delta(T)\leq D/2$ and let $H$ be a $(D,m)$-extendable
subgraph of $G$ with maximum degree at most $D/2$.

If $|H|+|T|\leq|G|-(2D+3)m$, then for every vertex $t\in V(T)$ and $v\in
V(H)$, there is a copy $S$ of $T$ in $G-V(H-v)$ in which $t$ is copied to $v$
and, moreover, $S\cup H$ is a $(D,m)$-extendable subgraph of $G$.

The following is a key result, proved by using the rollback idea of Johannsen
described earlier.

######  Lemma 3.10 ([18, Corollary 3.12]).

Let $D,m\in\mathbb{N}$ with $D\geq 3$, and let
$k=\lceil\log(2m)/\log(D-1)\rceil$. Let $\ell\in\mathbb{N}$ satisfy $\ell\geq
2k+1$ and let $G$ be an $m$-joined graph which contains a $(D,m)$-extendable
subgraph $S$ of size $|S|\leq|G|-10Dm-(\ell-2k-1)$.

Suppose that $a$ and $b$ are two distinct vertices in $S$ with
$d_{S}(a),d_{S}(b)\leq D/2$. Then, there exists an $a,b$-path $P$ of length
$\ell$ such that (i) all internal vertices of $P$ lie outside $S$, and (ii)
$S+P$ is $(D,m)$-extendable.

##  4 Sorting networks

A parallel comparison network is a pair $(R,\mathcal{C})$ which consists of a
set $R:=\\{r_{1},r_{2},\ldots,r_{n}\\}$ of $n$ registers, and a sequence of
sets $\mathcal{C}=C_{1},C_{2},C_{3},\ldots$, where each $C_{i}$ is a
collection of disjoint pairs of registers $(r_{i},r_{j})$ with $i<j$, i.e.,
for any $(r_{i_{1}},r_{i_{2}}),(r_{i_{3}},r_{i_{4}})\in C_{i}$ we have that
$i_{1},i_{2},i_{3},i_{4}$ are all distinct. The depth of such a network is
defined to be the length of the sequence $\mathcal{C}$.

Let $\rho_{0}\colon R\to[n]$ be a bijection assigning values to each register.
For some $1\leq i\leq\ell$, suppose, inductively, that we have defined
bijections $\rho_{0}$, $\rho_{1}$, $\ldots$ , $\rho_{i-1}:R\to[n]$, and let us
define $\rho_{i}\colon R\to[n]$ as follows. For distinct indices
$j_{1},j_{2}\in[n]$, we let $\rho_{i}(r_{j_{1}})=\rho_{i-1}(r_{j_{2}})$ and
$\rho_{i}(r_{j_{2}})=\rho_{i-1}(r_{j_{1}})$ if both $(r_{j_{1}},r_{j_{2}})\in
C_{i}$ and $\rho_{i-1}(r_{j_{1}})>\rho_{i-1}(r_{j_{2}})$, and, otherwise,
$\rho_{i}(r_{j_{1}})=\rho_{i-1}(r_{j_{1}})$ and
$\rho_{i}(r_{j_{2}})=\rho_{i-1}(r_{j_{2}})$. Further, if there exists any
$j\in[n]$ such that $r_{j}\notin(r_{j_{1}},r_{j_{2}})$ for any
$(r_{j_{1}},r_{j_{2}})\in C_{i}$, then we have
$\rho_{i}(r_{j})=\rho_{i-1}(r_{j})$. That is, $\rho_{i}$ swaps the values in
registers $r_{j_{1}}$ and $r_{j_{2}}$ given by $\rho_{i-1}$ if we have both
that this pair of registers was in $C_{i}$ and the values given to them by
$\rho_{i-1}$ decrease from $r_{j_{1}}$ to $r_{j_{2}}$. Otherwise, $\rho_{i}$
does not change the values.

We say that a parallel comparison network $(R,\mathcal{C})$ with depth $\ell$
is a parallel sorting network with depth $\ell$ if for _any_ initial
assignment $\rho_{0}\colon R\to[n]$, we have that $\rho_{\ell}=I$ where
$I:R\to[n]$ is defined as $I(r_{i})=i$ for all $i\in[n]$.

We need the following result of Ajtai, Komlós and Szemerédi [1] that gives a
parallel sorting network with depth logarithmic in the number of registers.

######  Theorem 4.1 (Ajtai-Komlós-Szemerédi [1]).

There exists an absolute constant $C_{\ref{thm:AKS_sorting}}$ such that the
following holds. For every $n$, there exists a parallel sorting network
$(R,\mathcal{C})$ with $n$ registers and depth at most
$C_{\ref{thm:AKS_sorting}}\log n$.

The earliest use of this result in extremal graph theory, that the authors are
aware of, is by Kühn, Lapinskas, Osthus and Patel [15]. This result has also
been recently used in a group theoretic setting in [21]. The key challenge
here, compared to [15] and [21], is that the underlying host graphs we are
working with are quite sparse.

The next lemma gives a construction which provides a graph theoretic analogue
of the comparison operation in a sorting network. The key feature is that the
graph constructed has arbitrarily large girth, and can be found inside a
sparse expander graph. In particular, the graph will be path-constructible.

######  Definition 4.2.

Let $G$ be a graph and let $A\subseteq V(G)$. We say that $G$ is $A$-path-
constructible if there exists a sequence of edge-disjoint paths
$P_{1},\ldots,P_{t}$ in $G$ with the following properties.

  1. (i)

$E(G)=\bigcup_{j\in[t]}E(P_{j})$.

  2. (ii)

For each $i\in[t]$, the internal vertices of $P_{i}$ are disjoint from
$A\cup\bigcup_{j\in[i-1]}V(P_{j})$.

  3. (iii)

For each $i\in[t]$, at least one of the endpoints of $P_{i}$ belongs to
$A\cup\bigcup_{j\in[i-1]}V(P_{j})$.

Figure 1: A depiction of a parallel comparison network with $4$ registers and
depth $4$. This is in fact a parallel sorting network. To see this, note that
after the first $3$ levels, the value $1$ will always be at $r_{1}$, and the
value $4$ will always be at $r_{4}$, and the final level sorts the middle two
layers.

######  Lemma 4.3.

For every $k\in\mathbb{N}$ with $k\equiv 2\mod 4$, there exists a graph
$G_{k}$, with distinct vertices
$v^{\text{in}}_{1},v^{\text{in}}_{2},v^{\text{out}}_{1},v^{\text{out}}_{2}$
and paths $P_{1},P_{2},Q_{1},Q_{2}\subset G_{k}$, such that the following
properties hold.

  1. (i)

$|G_{k}|=2k(k-1)$.

  2. (ii)

$\Delta(G_{k})=3$.

  3. (iii)

For each $z\in\\{v^{\text{in}}_{1},v^{\text{in}}_{2}\\}$, $G_{k}$ is
$\\{z\\}$-path-constructible with paths of length between $k$ and $2k+1$.

  4. (iv)

$P_{1}$ is a $v^{\text{in}}_{1},v^{\text{out}}_{2}$-path, $Q_{1}$ is a
$v^{\text{in}}_{2},v^{\text{out}}_{1}$-path, $P_{2}$ is a
$v^{\text{in}}_{1},v^{\text{out}}_{1}$-path and $Q_{2}$ is a
$v^{\text{in}}_{2},v^{\text{out}}_{2}$-path.

  5. (v)

For each $i\in[2]$, $V(G_{k})=V(P_{i})\ \dot{\cup}\ V(Q_{i})$, i.e. the vertex
set of $G_{k}$ is partitioned by $V(P_{i})$ and $V(Q_{i})$.

  6. (vi)

$|V(P_{1})|=|V(P_{2})|=|V(Q_{1})|=|V(Q_{2})|=k(k-1)$.

###### Proof.

We will construct $G_{k}$ from a cycle $C$ of length $2k$, by adding paths
$P(ab)$ between specific pairs of vertices $a,b\in V(C)$. Let
$U=\\{u_{1},\ldots,u_{k}\\}$ and $V=\\{v_{1},\ldots,v_{k}\\}$ be disjoint sets
of vertices, and let $C$ be the cycle on $U\cup V$ obtained by adding the
edges $u_{1}v_{2},u_{k}v_{k-1}$; $u_{i}u_{i+1}$ and $v_{i}v_{i+1}$, for every
odd $i\in[k-1]$; $u_{i}v_{i+2}$, for every even $i\in[k-2]$; and
$u_{i}v_{i-2}$ for every odd $i$ with $3\leq i\leq k$. For example, when
$k=2$, we have the $4$-cycle $C=u_{1}u_{2}v_{1}v_{2}u_{1}$, and, when $k=6$,
we have $C=u_{1}u_{2}v_{4}v_{3}u_{5}u_{6}v_{5}v_{6}u_{4}u_{3}v_{1}v_{2}u_{1}$.

Setting $S:=\\{(u_{i},u_{i+1}):i\in[k-2],i\text{
even}\\}\cup\\{(v_{i},v_{i+1}):i\in[k-2],i\text{ even}\\}$, $G_{k}$ is
obtained from $C$ by adding a path $P(ab)$ between $a$ and $b$, using $2k$ new
vertices, for each pair $(a,b)\in S$. For each $(a,b)\in S$, let $P(ba)$ be
the path $P(ab)$ traversed in the opposite direction, that is, it is a path
beginning with vertex $b$ and ending at $a$. Set $v^{\text{in}}_{1}:=u_{1}$,
$v^{\text{in}}_{2}:=v_{1}$, $v^{\text{out}}_{1}:=u_{k}$ and
$v^{\text{out}}_{2}:=v_{k}$. Now define

$\begin{array}[]{lll}P_{1}&:=&u_{1}P(v_{2}v_{3})P(u_{5}u_{4})\ldots
P(v_{k-4}v_{k-3})P(u_{k-1}u_{k-2})v_{k},\vspace{.2cm}\\\
Q_{1}&:=&v_{1}P(u_{3}u_{2})P(v_{4}v_{5})\ldots
P(u_{k-3}u_{k-4})P(v_{k-2}v_{k-1})u_{k},\vspace{.2cm}\\\
P_{2}&:=&u_{1}P(u_{2}u_{3})P(u_{4}u_{5})\ldots
P(u_{k-2}u_{k-1})u_{k},\vspace{.2cm}\\\
Q_{2}&:=&v_{1}P(v_{2}v_{3})P(v_{4}v_{5})\ldots
P(v_{k-2}v_{k-1})v_{k}.\end{array}$

We now check that $G_{k}$ has the desired properties. Observe that Properties
(i), (ii) and (iv) follow by construction. To verify (iii), let
$P_{1}^{\prime}$ and $P_{2}^{\prime}$ be edge-disjoint paths of length $k$,
with the same endpoints, such that $P_{1}^{\prime}\cup P_{2}^{\prime}=C$, and
$z$ is one of the endpoints of $P_{1}^{\prime}$. Also, let paths
$P_{j}^{\prime}$, $j\geq 3$, correspond to the paths $P(ab)$ in an arbitrary
order. By construction, the edge set of $\bigcup_{j\geq 1}P_{i}^{\prime}$ is
equal to $E(G)$, and each path $P_{j}^{\prime}$ in the sequence meets the
vertices of the previous paths $P^{\prime}_{j^{\prime}}$, $j^{\prime}<j$, only
at the endpoints of $P^{\prime}_{j}$, if they intersect. Hence $G$ is
{z}-path-constructible. For (v), observe that, for each even $i$,
$P(u_{i}u_{i+1})$ appears in $P_{2}$ and $P(u_{i+1}u_{i})$ appears in
$P_{1}\cup Q_{1}$. Similarly, for each even $i$, we have that
$P(v_{i}v_{i+1})$ appears in $Q_{2}$ and $P(v_{i}v_{i+1})$ appears in
$P_{1}\cup Q_{1}$. As all vertices in
$G_{k}\setminus\\{u_{1},v_{1},u_{k},v_{k}\\}$ appear in some $P(ab)$, we
clearly have that (v) holds. Finally, (vi) holds as every $P(ab)$ contains
$2k+2$ vertices, $\frac{k}{2}-1$ of these paths appear in each of
$P_{1},Q_{1},P_{2},Q_{2}$ and there are $4$ ‘end’ vertices
$u_{1},v_{1},u_{k},v_{k}$.∎

Figure 2: The graph $G_{6}$, as given by Lemma 4.3. The path in red is $P_{1}$
and the path in blue is $Q_{1}$. The dotted lines correspond to the added
$P(ab)$ paths and the full lines form a copy of $C_{12}$. The top vertices
represent $U$ and the bottom vertices represent $V$.

Using an optimal sorting network as a template, we will ‘glue together’ copies
of the graph $G_{k}$ from Lemma 4.3 to obtain the following result.

######  Proposition 4.4.

There exists a constant $C_{\ref{prop:sorting_network_template}}$ such that
for every $n$ and $k$ and every $\ell\geq\lfloor
C_{\ref{prop:sorting_network_template}}k^{2}\log n\rfloor$, there exists a
graph $G$, with $\Delta(G)=4$, which contains disjoint subsets $A,B\subseteq
V(G)$ with $|A|=|B|=n$, such that the following properties hold.

  1. (i)

$G$ is $A\cup B$-path-constructible with paths of length between $k$ and $4k$
(recall Definition 4.2).

  2. (ii)

For any bijection $\phi\colon A\to B$, there exists a $P_{\ell}$-factor in $G$
such that each path has as endpoints some $a\in A$ and $\phi(a)\in B$.

###### Proof.

In what follows, whenever we add a structure during our construction, which
will be either a copy of $G_{k}$ or a path, the only intersection with the
previously existing vertices and edges will be that explicitly mentioned.
Also, we will construct $G$ for some $\ell=O(k^{2}\log n)$ as this implies the
existence of a constant $C_{4.4}$ and some graph $G^{\prime}$ with
$\ell^{\prime}$ exactly equal to any value above $\lfloor
C_{\ref{prop:sorting_network_template}}k^{2}\log n\rfloor$ by adding
additional paths of length between $k$ and $4k$ to extend the
$P_{\ell}$-factor in $G$.

By Theorem 4.1, there exists a parallel sorting network $(R,\mathcal{C})$ with
$n$ registers and depth $\ell^{\prime}\leq C_{\ref{thm:AKS_sorting}}\log n$.
Since we are only constructing $G$ for some $\ell=O(k^{2}\log n)$, we may
without loss of generality (and without relabelling) increase the value of $k$
by at most $3$, if necessary, so that $k\equiv 2$ (mod $4$). Let $G_{k}$ be
the graph given by Lemma 4.3. Firstly, we define $A^{\text{out}}_{0}:=A$ and
$A^{\text{in}}_{\ell^{\prime}+1}:=B$, and, for $i\in[\ell^{\prime}]$, we let
$A^{\text{in}}_{i}$ and $A^{\text{out}}_{i}$ be sets of size $n$, all disjoint
from each other. For each $1\leq i\leq\ell^{\prime}+1$, we label the vertices
of the sets as
$A^{\text{in}}_{i}=:\\{v^{\text{in}}_{i,1},\ldots,v^{\text{in}}_{i,n}\\}$ and
for each $0\leq i\leq\ell^{\prime}$ we label
$A^{\text{out}}_{i}=:\\{v^{\text{out}}_{i,1},\ldots,v^{\text{out}}_{i,n}\\}$.

We now define the graph $G$. For each $i\in[\ell^{\prime}]$ and each pair of
registers $(r_{j_{1}},r_{j_{2}})\in C_{i}$, we add a graph
$G_{i,r_{j_{1}},r_{j_{2}}}$ that is a copy of $G_{k}$, where
$v^{\text{in}}_{i,j_{1}}$ and $v^{\text{out}}_{i,j_{1}}$ correspond to
$v_{1}^{\text{in}}$ and $v_{1}^{\text{out}}$, respectively, and
$v^{\text{in}}_{i,j_{2}}$ and $v^{\text{out}}_{i,j_{2}}$ correspond to
$v_{2}^{\text{in}}$ and $v_{2}^{\text{out}}$, respectively. Secondly, given
$C_{i}\in\mathcal{C}$, for each register $r_{j}$ that is not included in any
pair of registers from $C_{i}$, we add a
$v_{i,j}^{\text{in}},v_{i,j}^{\text{out}}$-path $P_{i,j}$ with $k(k-1)$
vertices. Finally, for each $0\leq i\leq\ell^{\prime}$ and $j\in[n]$, we add a
$v_{i,j}^{\text{out}},v_{i+1,j}^{\text{in}}$-path $Q_{i,j}$ of length $k$.

To check (i), we need to provide a sequence $\mathcal{S}$ of subpaths with the
desired properties. We build $\mathcal{S}$ inductively. Order $C_{1}$
arbitrarily, and for each pair $(r_{j_{1}},r_{j_{2}})\in C_{1}$ (recall, by
definition $j_{1}<j_{2}$) add the path $Q_{0,j_{1}}$ to $\mathcal{S}$, noting
that each of these paths has one endpoint in $A$. Afterwards, for each graph
$G_{1,r_{j_{1}},r_{j_{2}}}$, consider the sequence guaranteed by Lemma
4.3(iii) with $z=v_{1}^{\text{in}}$, and append this sequence to
$\mathcal{S}$. Now add to $\mathcal{S}$ each path $Q_{0,j^{\prime}}$ not
already added, followed by each path $P_{1,j}$ on $k(k-1)$ vertices, observing
that each path when added intersects with $A_{0}^{\text{out}}$ or
$A_{1}^{\text{out}}$ in at least one end vertex. We can proceed similarly for
$i\geq 2$ to obtain the desired path sequence $\mathcal{S}$.

Observe that, for each register $r_{j}$ and each level $i\in[\ell^{\prime}]$,
we have two vertices, an in-vertex and an out-vertex, contained in either a
copy of $G_{k}$ or a path $P_{i,j}$, and thus, for all $i\in[\ell^{\prime}]$
and $j\in[n]$ there is a $v_{i,j}^{\text{in}},v_{i,j}^{\text{out}}$-path with
$k(k-1)$ vertices. Therefore, taking into account the paths $Q_{i,j}$ as well,
the number of vertices in $G$ is

$n\cdot(\ell^{\prime}k(k-1)+(\ell^{\prime}+1)k)=O(nk^{2}\log n).$

It remains to confirm (ii) holds. Towards that goal, for a given bijection
$\phi\colon A\to B$, we define a spanning subgraph $G_{\phi}\subseteq G$ that
is a $P_{\ell}$-factor satisfying (ii), where $\ell:=(|G|/n)-1=O(k^{2}\log
n)$. We include in $G_{\phi}$ every edge from $G$ that belongs to one of the
paths $Q_{i,j}$, for $0\leq i\leq\ell^{\prime}$ and $j\in[n]$, and also
include all edges belonging to any paths $P_{i^{\prime},j^{\prime}}$ that
exist, for any $i^{\prime}$ and $j^{\prime}$. For each
$G_{i,r_{j_{1}},r_{j_{2}}}$, recall that $(r_{j_{1}},r_{j_{2}})\in C_{i}$, and
so the values in registers $r_{j_{1}}$ and $r_{j_{2}}$ are either swapped or
remain the same. Reflecting this, if $C_{i}$ swaps the values in the registers
we take the paths of the copy of $G_{i,r_{j_{1}},r_{j_{2}}}$ corresponding to
$P_{1}$ and $Q_{1}$ in the statement of Lemma 4.3, otherwise we take the paths
corresponding to $P_{2}$ and $Q_{2}$.

Figure 3: The graph $G$ obtained from the sorting network in Figure 1 by
replacing each pair of registers with a copy of $G_{2}$, the cycle of length
$4$. For the bijection $\phi$ mapping $1\to 4$, $2\to 1$, $3\to 2$, and $4\to
3$, the subgraph $G_{\phi}$ corresponds to the coloured paths.

It is easy to see that $G_{\phi}$ is a $P_{\ell}$-factor with all endpoints in
$A$ and $B$. Furthermore, the pair of paths that correspond to swapping
values, and the pairs of paths that correspond to maintaining the same values
in the registers exactly mimic the operation of the parallel sorting network
$(R,\mathcal{C})$ on $\phi$. This guarantees that for each $a\in A$, there
exists a path in the $P_{\ell}$-factor with endpoints $a\in A$ and $\phi(a)\in
B$, as desired. ∎

###  4.1 Proof of the sorting network lemma

The remaining task is to show that the graph described in Proposition 4.4 can
be found inside a sparse expander.

###### Proof of Lemma 2.3.

Let
$C_{\ref{lemma:find_sorting_network_in_expander}}=C_{\ref{prop:sorting_network_template}}$
and select $K$ so that $1/K\ll
1/C_{\ref{lemma:find_sorting_network_in_expander}}$. Let $G^{\prime}$ be the
graph given by Proposition 4.4 with
$n_{\ref{prop:sorting_network_template}}=|V_{1}|$, $k=\log n$, and
$\ell=\lfloor
C_{\ref{lemma:find_sorting_network_in_expander}}\log^{3}n\rfloor$ (note
$\ell\geq C_{\ref{prop:sorting_network_template}}k^{2}\log|V_{1}|$). We claim
that $G^{\prime}$ can be embedded into $G$, with $A$ copied to $V_{1}$ and $B$
copied to $V_{2}$. Clearly, this would imply the lemma, as $G^{\prime}$
satisfies property (ii) from Proposition 4.4.

We will embed $G^{\prime}$ using property (i) from Proposition 4.4 and
repeatedly applying either of Lemmas 3.9 or 3.10, so that at each stage we
embed a path $P$ of length $q\in[\log n,4\log n]$ with all its internal
vertices disjoint from all the vertices embedded in previous stages. Let
$P_{1},\ldots,P_{t}$ be the sequence of subpaths guaranteed by Proposition
4.4.

Letting $P_{0}=I(A\cup B)$, at stage $i$ of the embedding, for $0\leq i\leq
t$, we will have a $(D,m)$-extendable subgraph $S_{i}\subset G$ such that
$S_{i}$ is a copy of $P_{0}\cup\ldots\cup P_{i}$, $V_{1}$ is copied to $A$,
and $V_{2}$ is copied to $B$. Let $S_{0}=I(V_{1}\cup V_{2})$, with $A$ copied
to $V_{1}$ and $B$ copied to $V_{2}$, and suppose that we have successfully
performed stage $i$ of the embedding, for some $0\leq i<t$, and let us
demonstrate how we continue the embedding in stage $i+1$. Recall that, by
property of the sequence, $P_{i+1}$ is a path which is internally disjoint
with $P_{0}\cup P_{1}\cup\ldots\cup P_{i}$ and at least one of the endpoints
of the path belongs to $P_{0}\cup P_{1}\cup\ldots\cup P_{i}$. Let
$x_{i+1},y_{i+1}$ be the endpoints of $P_{i+1}$. If both $x_{i+1}$ and
$y_{i+1}$ belong to $\bigcup_{j\in[i]}V(P_{j})$, we will use Lemma 3.10 to
find a copy $Q_{i+1}$ of $P_{i+1}$ connecting the image of $x_{i+1}$ and
$y_{i+1}$. If only one of the endpoints of $P_{i+1}$ is already embedded, say
$x_{i+1}$, then we will use Lemma 3.9 to find a copy $Q_{i+1}$ of $P_{i+1}$
starting from the image of $x_{i+1}$. In either case, we extend the embedding
by letting $S_{i+1}=S_{i}+Q_{i+1}$, which is a $(D,m)$-extendable subgraph of
$G$ where $A$ is copied to $V_{1}$ and $B$ is copied to $V_{2}$.

We now show that the conditions to apply Lemmas 3.9 and 3.10 are satisfied
when performing step $i+1$ of the embedding. Indeed, first note that $m\leq
n/100D$ and

$|S_{i}|+|P_{i+1}|\leq|G^{\prime}|\leq|V_{1}|\cdot
2C_{\ref{lemma:find_sorting_network_in_expander}}\log^{3}n\leq\frac{n}{10},$
(3)

where we used that $|V_{1}|\leq n/K\log^{3}n$ and $1/K\ll
1/C_{\ref{lemma:find_sorting_network_in_expander}}$. Moreover, note that we
are adding a path of length at least

$\log n\geq\log(2m)\geq\frac{6\log(2m)}{\log(D-1)},$

which implies that the length condition in Lemma 3.10 is satisfied. Therefore,
as $\Delta(S_{i})\leq 5\leq D/2$ and by (3), we can indeed use either Lemma
3.9 or Lemma 3.10 to perform the embedding in stage $i+1$.

Finally, let us observe that after $t$ stages we have found a
$(D,m)$-extendable subgraph $S_{t}\subset G$ which is a copy of
$P_{1}\cup\ldots\cup P_{t}=G^{\prime}$, where $A$ is copied to $V_{1}$ and $B$
is copied to $V_{2}$. Thus, letting $S_{res}=S_{t}$ finishes the proof. ∎

##  5 Proof of Theorem 1.2

The following result allows us to assume an upper bound on $d$ in the proof of
Theorem 1.2.

######  Theorem 5.1 (Komlós–Sárközy–Szemerédi [11]).

For every $\Delta\in\mathbb{N}$ and $\varepsilon>0$, there exists
$n_{0}\in\mathbb{N}$ such that the following holds for all $n\geq n_{0}$. If
$G$ is an $n$-vertex graph with $\delta(G)\geq(1+\varepsilon)\frac{n}{2}$,
then $G$ contains a copy of every $n$-vertex tree with maximum degree bounded
by $\Delta$.

We now give the proof of our main theorem, which follows closely the sketch
given in Section 2. However, there will be an additional complication in the
proof, where we will need to address the following technical issue. Once we
embed the tree with the internal vertices of the bare paths removed, we have
no control over how the graph expands into the image of the endpoints of the
bare paths (which is what we need afterwards in order to find the perfect
matchings). To overcome this problem, in Step 4 in the proof we will find a
collection of short paths starting from the endpoints of the bare paths and
ending at two random subsets that we set aside at the beginning of the proof,
after which we can sequentially find perfect matchings as described in Section
2.

###### Proof of Theorem 1.2.

We first choose constants from ‘right to left’ as follows.

$1/n\ll 1/C\ll\varepsilon\ll
1/K\ll\mu,1/C_{\ref{thm:manyleaves}},1/C_{\ref{lemma:find_sorting_network_in_expander}},1/C_{\ref{prop:sorting_network_template}},1/K_{\ref{thm:manyleaves}}\ll\alpha,1/\Delta.$

Let $d\in\mathbb{N}$ and $\lambda>0$ so that $d/\lambda\geq C\log^{3}n$. Let
$G$ be an $(n,d,\lambda)$-graph and note that, by Theorem 5.1, we may assume
$d\leq 0.6n$. Then, from Lemma 3.2, we have

$d\geq\tfrac{n-d}{n-1}\cdot\left(C\log^{3}n\right)^{2}\geq C\log^{6}n.$ (4)

Step 0: Find a large collection of long bare paths in $T$. We may assume that
$T$ contains less than $K_{\ref{thm:manyleaves}}\lambda n/d\leq\alpha
n/\log^{3}n$ leaves, as, otherwise, we can use Theorem 2.1 to find a copy of
$T$ in $G$. Then, Lemma 2.2 implies $T$ contains at least

$\frac{n}{1+2K\log^{3}n}-\frac{2\alpha
n}{\log^{3}n}+2\geq\frac{n}{4K\log^{3}n}$

vertex-disjoint bare paths of length $2K\log^{3}n$. Therefore, for
$k:=\lfloor\frac{\mu n}{K\log^{3}n}\rfloor$, we may take a collection
$P_{1},\ldots,P_{k}\subset T$ of bare paths in $T$, each of length
$\ell=K\log^{3}n$. Let $T^{\prime}$ be the forest obtained by removing the
edges of $P_{1}\cup\ldots\cup P_{k}$ from $T$. For clarity, $T^{\prime}$
includes both endpoints of each path $P_{i}$.

Step 1: Set aside some random sets. Pick four disjoint random subsets
$R_{1},R_{2},R_{3},R_{4}\subset V(G)$, each of size $k$, so that with high
probability we have that

  1. A1

$\frac{\mu d}{2K\log^{3}n}\leq d(v,R_{i})\leq\frac{2\mu d}{K\log^{3}n}$ for
all $v\in V(G)$ and $i\in[4]$,

and pick another random set $R_{0}$, disjoint from $R_{1},R_{2},R_{3},R_{4}$
and of size $\mu n/2$, so that with high probability we have

  1. A2

$\mu d\geq d(v,R_{0})\geq\mu d/4$ for every $v\in V(G)$.

Note that A1 and A2 both hold with high probability by Lemma 3.1 (and a union
bound) and (4). Set $m:=\ell-10\lfloor\log n\rfloor-
C_{\ref{lemma:find_sorting_network_in_expander}}\lfloor\log^{3}n\rfloor-1$ and
$R:=\bigcup_{0\leq i\leq 4}R_{i}$. Observe that $|R|\leq\mu n$ and $m\leq
K\log^{3}n$. Then, since $1/n_{0}\ll\varepsilon\ll 1/K$,
$0<\mu\leq\frac{1}{10}$ and $n\geq n_{0}$, we may use Lemma 3.1 to find
pairwise disjoint subsets $V_{1},\ldots,V_{m}\subset V(G)\setminus R$ such
that

  1. B1

$|V_{i}|=\frac{\varepsilon n}{\log^{3}n}$ for all $i\in[m]$,

  2. B2

$\frac{\varepsilon d}{2\log^{3}n}\leq d(v,V_{i})\leq\frac{2\varepsilon
d}{\log^{3}n}$ for all $v\in V(G)$ and $i\in[m]$, and

  3. B3

$d(v,V(G)\setminus(R\cup\bigcup_{i\in[m]}V_{i}))\geq\frac{2d}{3}$ for all
$v\in V(G)$.

Step 2: Set aside a sorting network. Set $t:=\lfloor
C_{\ref{lemma:find_sorting_network_in_expander}}\log^{3}k\rfloor$, noting
$t\leq\ell/100$, and let $R_{3}=:\\{x_{1},\ldots,x_{k}\\}$ and
$R_{4}=:\\{y_{1},\ldots,y_{k}\\}$.

######  Claim 5.2.

There is a subset $W\subset
V(G)\setminus\left(R\cup\bigcup_{i\in[m]}V_{i}\right)$ with $|W|=k(t-1)$ such
that the following holds.

  1. C

For every bijection $\varphi:[k]\to[k]$ there is a collection of vertex-
disjoint paths $D_{1},\ldots,D_{k}$ such that, for each $i\in[k]$, $D_{i}$ is
an $x_{i},y_{\varphi(i)}$-path of length $t$ whose interior vertices are in
$W$ (and thus partition $W$).

###### Proof.

Set $\hat{G}:=G-(R_{0}\cup R_{1}\cup R_{2}\cup\bigcup_{i\in[m]}V_{i})$.
Observe that $|\hat{G}|\geq n/2$, that $\lambda
n/d\leq|\hat{G}|/(100\log|\hat{G}|)$ since $d/\lambda\geq C\log^{3}n$ and $n$
is sufficiently large, and that $2\lambda n/d\leq
k\leq|\hat{G}|/K\log^{3}|\hat{G}|$ as $1/C\ll\mu,1/K$. We aim to apply Lemma
2.3 with the following parameters:
$G_{\ref{lemma:find_sorting_network_in_expander}}=\hat{G}$ ,
$m_{\ref{lemma:find_sorting_network_in_expander}}=:m^{\prime}=\lambda n/d$,
$D=\log n$, $V_{1}=R_{3}$ and $V_{2}=R_{4}$. Note that $\hat{G}$ is
$m^{\prime}$-joined as $G$ is $m^{\prime}$-joined, and also $D\geq 100$, so it
suffices to check that $I(R_{3}\cup R_{4})$ is $(D,m^{\prime})$-extendable in
$\hat{G}$. By A1, A2 and B3, every vertex of $\hat{G}$ has at least
$d/1000\gg\mu d/\log^{2}n$ neighbours in $\hat{G}-(R_{3}\cup R_{4})$, so by
Lemma 3.5, with $z_{\ref{lemma:expansion2}}=\log n$, and Proposition 3.8, we
verify the definition of $(D,m^{\prime})$-extendable for sets $U$ of size at
most $m^{\prime}$. For a set $U$ with $m^{\prime}\leq|U|\leq 2m^{\prime}$,
$(D,m^{\prime})$-extendability follows by $m^{\prime}$-joinedness. Indeed, we
have that $|N_{\hat{G}}(U)\setminus(R_{3}\cup
R_{4})|\geq|\hat{G}|-1-|R_{3}\cup R_{4}|-3m^{\prime}\geq n/100\geq
2Dm^{\prime}$, as needed.

Now, the conclusion of Lemma 2.3 corresponds exactly to C. ∎

Step 3: Embed $T^{\prime}$, an almost spanning forest. Let
$G^{\prime}=G-(W\cup R_{3}\cup R_{4}\cup\bigcup_{i\in[m]}V_{i})$ and note that

$|G^{\prime}|\overset{\ref{B:1}}{\geq}n-|W\cup R_{3}\cup
R_{4}|-m\cdot\frac{\varepsilon n}{\log^{3}n}\geq n-k\cdot(t+1)-K\varepsilon
n,$ (5)

where we have used that $\ell=K\log^{3}n$ and $m\leq\ell$.

For some $v\in V(G^{\prime})\setminus(R_{1}\cup R_{2})$ chosen arbitrarily,
define $S_{v}:=I(\\{v\\}\cup R_{1}\cup R_{2})$.

######  Claim 5.3.

$S_{v}$ is a $(10\Delta,\frac{\lambda n}{d})$-extendable subgraph of
$G^{\prime}$.

###### Proof.

Indeed, for a subset $X\subset V(G^{\prime})$ with $1\leq|X|\leq\frac{\lambda
n}{d}$, we have

$|N_{G^{\prime}}(X)\setminus V(S_{v})|\geq|N_{G}(X)\cap
R_{0}|{\geq}10\Delta|X|,$

where we have used A2 and Lemma 3.5, with $z_{\ref{lemma:expansion2}}=1$ in
the second inequality. If $\frac{\lambda n}{d}\leq|X|\leq\frac{2\lambda
n}{d}$, we use Lemma 3.4 and (5) to deduce that

$|N_{G^{\prime}}(X)\setminus V(S_{v})|\geq|G^{\prime}|-1-|R_{1}\cup
R_{2}|-\frac{3\lambda
n}{d}\overset{\eqref{eq:G':size}}{\geq}\frac{n}{2}-\frac{3\lambda n}{d}\geq
10\Delta|X|.$

Also, clearly $0=\Delta(S_{v})\leq 10\Delta$. Then, Proposition 3.8 implies
that $S_{v}$ is $(10\Delta,\frac{\lambda n}{d})$-extendable in $G^{\prime}$. ∎

Recall that $T^{\prime}$ is the forest obtained by removing the edges of the
bare paths $P_{1},\ldots,P_{k}$ from $T$. We may add dummy edges to
$T^{\prime}$ to think of it as a tree rather than a forest for the following
application. Use Lemma 3.9 to find a copy $S$ of $T^{\prime}$ in
$G^{\prime}-(R_{1}\cup R_{2})$ (the root $t$ to be embedded on $v$ can be
chosen arbitrarily) such that $S\cup S_{v}$ is $(10\Delta,\frac{\lambda
n}{d})$-extendable in $G^{\prime}$. This can be done as $G^{\prime}$ is
$\frac{\lambda n}{d}$-joined (trivially, since $G$ is $\frac{\lambda
n}{d}$-joined), $S_{v}$ is $(10\Delta,\frac{\lambda n}{d})$-extendable in
$G^{\prime}$ by Claim 5.3, $|S_{v}|\leq\frac{\mu n}{3}$, and

$|G^{\prime}|-(20\Delta+3)\lambda
n/d\overset{\eqref{eq:G':size}}{\geq}n-k\cdot(t+1)-K\varepsilon
n-(20\Delta+3)\lambda n/d\geq|T^{\prime}|+\frac{\mu n}{2},$ (6)

where we have used that $|T^{\prime}|\leq n-\frac{\mu n}{2})$, that
$k\cdot(t+1)\leq\frac{\mu n}{1000}$ since $C_{2.3}\ll K$, that
$\frac{(20\Delta+3)\lambda}{d}\leq\frac{20\Delta+3}{C\log^{3}n}\ll\mu$ and
that $K\varepsilon\ll\mu$.

Step 4: Connect the endpoints of $\bigcup P_{i}$ to $R_{1}$ and $R_{2}$. Let
$R_{1}=\\{a_{1},\ldots,a_{k}\\}$ and $R_{2}=\\{b_{1},\ldots,b_{k}\\}$. For
each $i\in[k]$, let $u_{i}$ and $v_{i}$ be the endpoints of the path $P_{i}$,
recalling that these vertices belong to $V(T^{\prime})$, hence copies of these
vertices are present in the embedding $S$ we produced earlier. We refer to the
copies of these vertices as $u_{i}$ and $v_{i}$, $i\in[k]$, as well.

We now find a collection of vertex-disjoint paths $Q_{1},\ldots,Q_{k}$ such
that

  1. D1

$\bigcup_{i\in[k]}Q_{i}$ is disjoint from $V(S)\cup R_{2}$,

  2. D2

$Q_{i}$ is a $u_{i},a_{i}$-path of length $t^{\prime}:=5\lfloor\log n\rfloor$
for each $i\in[k]$, and

  3. D3

$S\cup I(R_{1}\cup R_{2})\cup Q_{1}\cup\ldots\cup Q_{i-1}$ is
$(10\Delta,\frac{\lambda n}{d})$-extendable for each $i\in[k]$.

Indeed, setting $Q_{0}:=\emptyset$, we have that $S\cup I(\\{v\\}\cup
R_{1}\cup R_{2})\cup Q_{0}$ is $(10\Delta,\frac{\lambda n}{d})$-extendable in
$G^{\prime}$. Then, we can find $Q_{1},\ldots,Q_{k}$ using iteratively Lemma
3.10 while ensuring D3. This can be done as, by D3 for $i-1$, $S\cup
I(\\{v\\}\cup R_{1}\cup R_{2})\cup\bigcup_{j\in[i]}Q_{j-1}$ is
$(10\Delta,\frac{\lambda n}{d})$-extendable in $G^{\prime}$, has maximum
degree at most $\Delta(T)\leq\Delta$, we have $t^{\prime}\geq
2\frac{\log(\lambda n/d)}{\log(10\Delta+1)}+1$ and

$|G^{\prime}|-10D\lambda
n/d-(t^{\prime}-1)\overset{\eqref{eq:G':size}}{\geq}n-k\cdot(t+1)-K\varepsilon
n-100\Delta\lambda n/d-t^{\prime}\geq|S|+|R_{1}\cup
R_{2}|+|\cup_{i\in[k]}Q_{i}|,$

where the second inequality holds for essentially the same reasons the second
inequality of (6) holds. Let $F=S\cup I(\\{v\\}\cup R_{1}\cup
R_{2})\cup\bigcup_{i\in[k]}Q_{i}$. Then $F$ is $(10\Delta,\frac{\lambda
n}{d})$-extendable in $G^{\prime}$ by D3. Similarly as above, find a
collection of vertex-disjoint paths $Q_{1}^{\prime},\ldots,Q_{k}^{\prime}$
such that

  1. E1

$\bigcup_{i\in[k]}Q^{\prime}_{i}$ is disjoint from $V(F)$, and

  2. E2

$Q^{\prime}_{i}$ is a $v_{i},b_{i}$-path of length $t^{\prime}$ for each
$i\in[k]$.

Step 5: Connect $R_{1}$ to $R_{3}$ and $R_{2}$ to $R_{4}$. Note that up to
this point, we have embedded $T^{\prime}$ and the first and last
$t^{\prime}+1$ vertices of each path $P_{1},\ldots,P_{k}$. Let $S^{\prime}$ be
the current embedding.

######  Claim 5.4.

There are two permutations $\psi$ and $\psi^{\prime}$ of $[k]$ and a
collection of vertex-disjoint paths $L_{1},\ldots,L_{k}$,
$L^{\prime}_{1},\ldots,L^{\prime}_{k}$ in $G-W$ such that

  1. F1

the interior vertices of
$L_{1},\ldots,L_{k},L^{\prime}_{1},\ldots,L^{\prime}_{k}$ are disjoint from
$V(S^{\prime})$,

  2. F2

$L_{i}$ is an $a_{i},x_{\psi(i)}$-path of length $m+1$ for each $i\in[k]$, and

  3. F3

$L^{\prime}_{i}$ is an $b_{i},y_{\psi^{\prime}(i)}$-path of length $1$ for
each $i\in[k]$.

###### Proof.

To find $L_{i}^{\prime}$, we simply need to find a perfect matching between
$R_{4}$ and $R_{2}$, which is guaranteed by Lemma 3.6, as $|R_{2}|=|R_{4}|=k$
and A1 implies that $\delta(G[R_{2},R_{4}])\geq\varepsilon d/2\log^{3}n$. Note
that all but $mk$ vertices of $T$ are now embedded. Let $S^{\prime\prime}$ be
$S^{\prime}$ together with $L_{1}^{\prime}\ldots,L_{k}^{\prime}$, and
$T^{\prime\prime}$ be the subtree of $T$ isomorphic with $S^{\prime\prime}$.
Then, as $|V(G)\setminus(W\cup V(S^{\prime\prime}))|=mk$, we can partition
$V(G)\setminus(W\cup V(T^{\prime\prime}))=V_{1}^{\prime}\cup\ldots\cup
V_{m}^{\prime}$ so that $V_{i}\subseteq V_{i}^{\prime}$ for each $i\in[m]$ and
$|V_{1}^{\prime}|=\ldots=|V^{\prime}_{m}|=k$. Note that, by B2, we have
$\delta(G[V^{\prime}_{i},V^{\prime}_{i+1}])\geq\varepsilon d/2\log^{3}n$ for
each $1\leq i<m$, and, because of A1, we also have
$\delta(G[R_{1},V^{\prime}_{1}]),\delta(G[R_{3},V_{m}^{\prime}])\geq\varepsilon
d/2\log^{3}n$. Thus, invoking Lemma 3.6 iteratively, we can find perfect
matchings between $(R_{1},V_{1}^{\prime})$, $(V_{1}^{\prime},V_{2}^{\prime})$,
$\ldots$, $(V_{m-1}^{\prime},V_{m}^{\prime})$, and $(V_{m}^{\prime},R_{3})$.
The unions of these matchings give the desired collection $L_{1},\ldots,L_{k}$
of vertex-disjoint paths. ∎

Step 6: Use the sorting network. Finally, we can use C to embed the interior
$t-1$ vertices of each of the paths $P_{1},\ldots,P_{k}$, and thus complete
the embedding of $T$. Indeed, each $u_{i}$ and $v_{i}$ are connected via a
path to some element $a_{j_{i}}$ of $R_{2}$ and $b_{j_{i}^{\prime}}$ of
$R_{4}$, respectively, and it suffices to choose the bijection $\phi$ so that
it maps $a_{j_{i}}$ to $b_{j_{i}^{\prime}}$ for each $i\in[k]$. ∎

##  6 Concluding remarks

The results of Han and Yang [8] are formulated in the more general context of
$(n,d)$-expanders. The statement of Lemma 2.3 works also in this level of
generality, and so our methods imply universality results for
$(n,d)$-expanders as well, but we do not provide the formal details here.

In the proof of Theorem 1.2, $d$-regularity is not used in any essential way.
In particular, all degrees being in the range $(1\pm\gamma)d$ for some small
$\gamma>0$ would also have been sufficient. Hence, we expect that our methods
could show that $\mathbb{G}(n,p)$ is $\mathcal{T}(n,\Delta)$-universal
whenever $p\geq C_{\Delta}\log^{6}n/n$. However, this is not as strong as the
previously mentioned result of Montgomery [18] that $p\geq C_{\Delta}\log n/n$
is sufficient (see also his earlier work [17] showing that $p\geq
C_{\Delta}\log^{5}n/n$ is enough).

As another illustration of the use of Lemma 2.3, we sketch how to find cycle
factors in pseudorandom graphs (see [7] and the references therein for more
results in this direction).

######  Theorem 6.1.

There exist positive constants $K$ and $C$ such that the following holds for
all sufficiently large $n\in\mathbb{N}$. Let $k\in\mathbb{N}$ satisfy
$k=K\log^{3}n$ and $k\mid n$. Then, any $(n,d,\lambda)$-graph $G$ with
$\lambda\leq d/C\log^{3}n$ contains a $C_{k}$-factor.

###### Sketch of proof of Theorem 6.1.

Let $K$ be much larger than $C_{\ref{lemma:find_sorting_network_in_expander}}$
and let $C$ be large enough. Let $V_{1}$ and $V_{2}$ be two disjoint random
subsets of $G$ of size $n/k$. Set
$\ell=C_{\ref{lemma:find_sorting_network_in_expander}}\log^{3}(n/k)$ and
$t=k-\ell_{\ref{lemma:find_sorting_network_in_expander}}+1$. Take also
disjoint random sets $V_{i}$, for $3\leq i\leq t$, each of size $\lfloor
n/10k\rfloor$. Applying Lemma 2.3, with parameters $V_{1},V_{2}$ and
$G-\bigcup_{i\geq 3}V_{i}$, find a subgraph $S_{res}$, disjoint from
$\bigcup_{i\geq 3}V_{i}$, such that $S_{res}$ contains a $P_{\ell}$-factor
connecting $V_{1}$ with $V_{2}$ in any given ordering. Let
$V_{res}=V(S_{res})$ and, without relabelling, distribute all vertices of
$V(G)\setminus(V_{res}\cup\bigcup_{i\geq 1}V_{i})$ into $\bigcup_{i\geq
3}V_{i}$ so that $V_{i}=n/k$ for each $i\in[t]$. Then, find perfect matchings
(using Lemma 3.6) in $G[V_{t},V_{1}]$ and $G[V_{i},V_{i+1}]$, for $2\leq i<t$,
thus finding a $P_{t-1}$-factor $\mathcal{P}$ in $G\setminus V_{res}$ so that
each path in $\mathcal{P}$ has both endpoints in $V_{1}$ and $V_{2}$,
respectively. Labelling the vertices of $V_{1}$ and $V_{2}$ as
$\\{x_{1},\ldots,x_{n/k}\\}$ and $\\{y_{1},\ldots,y_{n/k}\\}$, respectively,
so that each path in $\mathcal{P}$ has as endpoints $x_{i}$ and $y_{i}$ for
some $i\in[n/k]$, we can simply invoke Lemma 2.3, with $\phi$ defined as
$\phi(x_{i})=y_{i}$ for each $1\leq i\leq n/k$, to obtain the desired
$C_{k}$-factor. ∎

Let us note that at the end of the above proof, we have a lot of flexibility
in the way we choose the bijection $\phi:V_{1}\to V_{2}$, which guarantees a
wider class of $2$-regular spanning subgraphs than claimed, including Hamilton
cycles. Also, up to the exponent of the logarithm, this matches the best known
condition on $\lambda$ that forces a Hamilton cycle [6, 13] and, notably, this
seems to be the first method that works in this regime which does not make use
of the Posá rotation-extension technique. By starting the proof with finding
some initial paths to ensure divisibility conditions, the same idea can be
used to show that $G$ contains all $2$-factors with sufficiently large girth,
but we do not provide details here.

Finally, let us remark that the condition $\lambda\leq d/C$ is sufficient to
apply Lemma 2.3 in the above proof. We use the stronger assumption that
$\lambda\leq d/C\log^{3}n$ only to find a path-factor in the leftover graph
with designated start and endpoints. There could be more efficient techniques
to perform this latter step, meaning that Lemma 2.3 could potentially be used
to attack the conjecture of Krivelevich and Sudakov [14] that $\lambda\leq
d/C$ is a sufficient condition for an $(n,d,\lambda)$-graph to be Hamiltonian.

## Acknowledgements

We would like to thank Richard Montgomery for organising a workshop at the
University of Warwick titled Spanning subgraphs in graphs and related
combinatorial problems where this work began in July 2023.

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi, _An ${O}(n\log n)$ sorting network_, Proceedings of the fifteenth annual ACM symposium on Theory of computing, 1983, pp. 1–9.
  * [2] N. Alon, M. Krivelevich, and B. Sudakov, _Embedding nearly-spanning bounded degree trees_ , Combinatorica 27 (2007), no. 6, 629–644.
  * [3] N. Draganić, M. Krivelevich, and R. Nenadov, _Rolling backwards can move you forward: on embedding problems in sparse expanders_ , Trans. Amer. Math. Soc. 375 (2022), no. 7, 5195–5216.
  * [4] Keith Frankston, Jeff Kahn, Bhargav Narayanan, and Jinyoung Park, _Thresholds versus fractional expectation-thresholds_ , Annals of Mathematics 194 (2021), no. 2, 475–495.
  * [5] J. Friedman and N. Pippenger, _Expanding graphs contain all small trees_ , Combinatorica 7 (1987), no. 1, 71–76.
  * [6] S. Glock, D. Munhá Correia, and B. Sudakov, _Hamilton cycles in pseudorandom graphs_ , 2023, arXiv:2303.05356.
  * [7] J. Han, Y. Kohayakawa, P. Morris, and Y. Person, _Finding any given 2-factor in sparse pseudorandom graphs efficiently_ , J. Graph Theory 96 (2021), no. 1, 87–108.
  * [8] J. Han and D. Yang, _Spanning trees in sparse expanders_ , 2022, arXiv:2211.04758.
  * [9] P. E. Haxell, _Tree embeddings_ , J. Graph Theory 36 (2001), no. 3, 121–130.
  * [10] D. Johannsen, M. Krivelevich, and W. Samotij, _Expanders are universal for the class of all spanning trees_ , Combin. Probab. Comput. 22 (2013), no. 2, 253–281.
  * [11] J. Komlós, G. N. Sárközy, and E. Szemerédi, _Proof of a packing conjecture of Bollobás_ , Combin. Probab. Comput. 4 (1995), no. 3, 241–255.
  * [12] M. Krivelevich, _Embedding spanning trees in random graphs_ , SIAM J. Discrete Math. 24 (2010), no. 4, 1495–1500.
  * [13] M. Krivelevich and B. Sudakov, _Sparse pseudo-random graphs are Hamiltonian_ , J. Graph Theory 42 (2003), no. 1, 17–33.
  * [14] , _Pseudo-random graphs_ , More sets, graphs and numbers, Bolyai Soc. Math. Stud., vol. 15, Springer, Berlin, 2006, pp. 199–262.
  * [15] D. Kühn, J. Lapinskas, D. Osthus, and V. Patel, _Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments_ , Proc. Lond. Math. Soc. (3) 109 (2014), no. 3, 733–762.
  * [16] A. Liebenau and N. Wormald, _Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph_ , 2023, J. Eur. Math. Soc.
  * [17] R. Montgomery, _Embedding bounded degree spanning trees in random graphs_ , 2014\.
  * [18] , _Spanning trees in random graphs_ , Adv. Math. 356 (2019), 106793, 92.
  * [19] R. Montgomery, A. Pokrovskiy, and B. Sudakov, _A proof of Ringel’s conjecture_ , Geom. Funct. Anal. 31 (2021), no. 3, 663–720.
  * [20] P. Morris, _Clique factors in pseudorandom graphs_ , 2023, to appear in J. Eur. Math. Soc.
  * [21] A. Müyesser and A. Pokrovskiy, _A random Hall-Paige conjecture_ , 2022, arXiv:2204.09666.
  * [22] M. Pavez-Signé, _Spanning trees in the square of pseudorandom graphs_ , 2023, arXiv:2307.00322.