<figure><img src="image_1.png" /></figure>

HAL
open science

AN IMPROVED LOWER BOUND FOR THE
EXPANSION OF RANDOM REGULAR GRAPHS
THROUGH π-LIFTS

Mohammad-Hossein Shojaedin, Amir Daneshgar

► To cite this version:

Mohammad-Hossein Shojaedin, Amir Daneshgar. AN IMPROVED LOWER BOUND FOR THE EXPANSION OF RANDOM REGULAR GRAPHS THROUGH π-LIFTS. 2023. hal-04012368

HAL Id: hal-04012368

https://hal.science/hal-04012368

Preprint submitted on 2 Mar 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
AN IMPROVED LOWER BOUND FOR THE EXPANSION OF RANDOM REGULAR
GRAPHS THROUGH π-LIFTS

AMIR DANESHGAR AND MOHAMMAD-HOSSEIN SHOJAEDIN

ABSTRACT.

In this article we introduce a new model for random regular graphs called the iterated π-lift model, as a counterpart to the well-known iterated 2-lift model. To show the effectiveness of the π-lift construction we show that applying a random π-lift construction to a graph coming from the configuration model will give rise to a model which is not only contiguous to the configuration model itself, but also it turns out to be an asymptotic generalization of the configuration model, providing a more flexible parametric structure through which one may find better expansion lower bounds for these models, and consequently, for the uniform model of random regular graphs. Our results are based on an analysis of the corresponding optimization problems as a sequel to contributions by B. Bollobás (1988) and N. Linial et.al. (2006) on the expansion lower bounds for the configuration and the 2-lift models of random regular graphs.

**Keywords:** Random regular graphs, expansion lower-bound, lifts, cylindrical constructions.

AMS subject classification-MSC2020: 05A16, 05C40, 05C80

# 1. INTRODUCTION

Our main objective in this article is to provide an improved lower bound for the expansion of random regular graphs in the uniform model through a modification of the celebrated configuration model (alias pairing model) of these random graphs. Although our study originated through a study of the iterated random π-lift model that will be introduced in what follows (see Sections 2 and 4), this article, as a first step to justify the importance of π-lift structure, is devoted to just show how this lift structure may give rise to an improvement of expansion lower bounds for the uniform model of random regular graphs as a sequel to what has already appeared in [3, 5, 16]. In particular, we explicitly show that just using a one-step π-lift transformation will provide strictly better expansion lower bounds for the uniform model of random d-regular graphs when d is an even number<fnref n="1" /> (see Table 1).

Our basic steps in this analysis are essentially along the same steps already taken in [3, 5] for the configuration and the 2-lift random regular graph models, while, intuitively, the modification may be described as a method to exclude a subset of low-expansion graphs (in this case of measure zero), which is mainly due to a better connectivity-preserving properties of the new lift structure (e.g. see Proposition 1). This, clearly, motivates a thorough study of the π-lift structure, as a counterpart for the well-studied 2-lifts (see Section 4 for more on these lift structures and some recent breakthroughs as [22]).

It turns out that in our modified π-lift model the corresponding optimization problems for the expansion lower bound seem to be harder and ask for more sophisticated methods to be

<footnote n="1">¹Applying more steps of the π-lift construction in an iterated scenario will actually give rise to models of random regular graphs with even better expansion lower bounds for both even and odd degrees, however our results in this regard will appear elsewhere (see Sections 2 and 4 for the definition of the iterated π-lift model).</footnote>
handled. As far as the model is concerned, our result strongly relies on the concept of a random $\pi$-lift construction [7, 8, 21], which is recalled in Section 2, as well as a contiguity result recalled in Theorem A. On the other hand, the main difficulties in our case is to handle the truncated binomial sums that naturally crop up throughout this analysis as well as to make a detour, helping to avoid asking for explicit solutions of the equations appearing as conditions in the corresponding optimization problems.

To do this, after introducing the random $\pi$-lift model and showing that the model is contig- uous to the well-known configuration model in Section 2, we go through our analysis by, firstly, using a method of B. Bollobás [5] to formalize the corresponding optimization problem for the expansion lower bound, where in a second step, we provide a real-relaxation of this optimiza- tion problem using degree-configuration vectors, that is more handy to be dealt with. To solve this relaxed optimization problem, we avoid the explicit solutions of the conditions by provid- ing some legitimate intervals which are guaranteed to contain the solutions of the equations and prove the necessary facts in a stronger setting for an arbitrary point within and outside of these intervals. The main challenge in our approach is to set the boundary points of these intervals in such a way that makes it possible to prove all we need for the points within and outside of the intervals for the rest of the proof. For this, it is instructive to note that, although we just in- troduce these intervals and prove their main properties, we have elaborated on adding remarks on how the boundary points of the intervals are justified by approximating the equations using Bernstein approximation schemes, and some asymptotic results of [5] and [20].

It is also instructive to note that, strictly speaking, our random $\pi$-lift model will turn out to be an asymptotic generalization of the configuration model with a larger set of parameters to be tuned for the optimal expansion lower bound problem, when on the other hand, it is more restricted than the configuration model as a set. This, in a way surprising, result showing a culmination of these two seemingly contradictory properties is one of the highlights of our analysis extracted through solving the corresponding optimization problems, while at the time of writing this article we are not aware of a combinatorial justification of this fact yet.

It is also interesting to note that our new random graph model and the corresponding op- timization problem for the expansion lower bound also gives rise to a setup as a generalized maximum entropy problem whose properties ought to be investigated in forthcoming research.

In the sequel, after going through our main setup in Section 2, we present our sequence of results in Section 3 leading to Theorem 2 describing an expansion lower bound which is used in a second step to provide our main result, explicitly stated for small degrees in Corollary 2. We have elaborated on going through the details of the proofs in an appendix to clarify the presentation. Also, we have dedicated the last section to a concise summary of our motivations and the relevant background leading to this study and some comments on different aspects of the iterated random $\pi$-lift model.

## 2. RANDOM REGULAR $\pi$-LIFTS AND THE CONFIGURATION MODEL

In this section we introduce the $\pi$-lift construction and its basic properties (see Section 4 for more on this). Our main fact in this section is Proposition 1 that paves the way to compare the random $\pi$-lift model to the configuration model of random regular graphs<fnref n="2" /> and apply the contiguity result of Theorem A.

<footnote n="2">²Although we do not concentrate on the *iterated* random $\pi$-lift model in this article, we just introduce the basics of the model in relation to Proposition 1 to make it possible to add some concluding remarks in this regard in Section 4.</footnote>
First, let us go through some definitions and fix our notations. In what follows, $|A|$, stands for the number of elements of the set $A$ and $f|_A$ indicates the restriction of a function $f$ to the subset $A$ of its domain. Also, we use the following notations:

$$ \forall i \leq d \quad [[d]]_i \stackrel{\text{def}}{=} \{i, i+1, \dots, d\}, $$

$$ A^{=2} \stackrel{\text{def}}{=} \{B \subseteq 2^A \mid |B| = 2\}, $$

$$ A^{\leq 2} \stackrel{\text{def}}{=} \{B \subseteq 2^A \mid |B| \leq 2\}. $$

In what follows, $S_2$ refers to the set of permutations on the set $\{1, 2\}$, in which $id \in S_2$ is the identity permutation and $\tau \in S_2$ is the transposition mapping 1 to 2 and vice versa.

In this article graphs are not directed but may have loops, multiple-edges or even half-edges. A formal definition follows.

**Definition 1. Half-edge graphs**

A *half-edge graph* (or hereafter a *graph* for short), as $H \stackrel{\text{def}}{=} (V, E_1, E_{1/2}, v_0, v_1)$, is the following structure,

(1) The set $V$ is a set of *vertices*.

(2) The set $E_1$ is a set of *edges*.

(3) The set $E_{1/2}$ is a set of *half-edges*.

(4) The map $v_0 : E_1 \to V^{\leq 2}$ that assigns to each edge its set of *terminals* or *end points*.

(5) The map $v_1 : E_{1/2} \to V$ that assigns to each half-edge its *head*.

Hence, for any undirected edge $e$ with the endpoints $u$ and $w$ we have $v_0(e) = \{u, w\}$, while for simplicity we may also refer to such an edge as $e = uw$ if there is no other multiple edge with these two endpoints or when we want to explicitly refer to the endpoints. Also, note that for any loop $e$ on a vertex $u$ we have $v_0(e) = \{u\}$. On the other hand, if for a half-edge $h$ we have $v_1(h) = \{u\}$, then we may refer to such a half-edge as *uh*.

Also, the *degree* of each vertex is defined to be the number of edges and half-edges which are joined to it, i.e. for all $u \in V$,

$$ \deg(u) \stackrel{\text{def}}{=} |\{h \in E_{1/2} \mid u \in v_1(e)\}| + \sum_{i=0}^{1} 2^i |\{e \in E_1 \mid u \in v_0(e) \ \& \ |v_0(e)| \mod 2 = i\}|. $$

A graph is said to be *simple* if it contains no loop, no multiple edge and no half-edge. Also, in the sequel, $H_1 \simeq H_2$ is used to refer to the *isomorphism* of graphs $H_1$ and $H_2$ that may be defined naturally based on the definitions (for more on this see e.g. [7]). ▲

**Example 1. Some special graphs**

Hereafter, $K_n$, is the complete graph on $n$ vertices. Also, $S_d^{1/2} \stackrel{\text{def}}{=} (V, E_1, E_{1/2}, v_0, v_1)$ refers to a *half-edge star* consisting of $d$ half-edges which are identified at their end vertex, i.e. $V = \{v\}$, $E_1 = \emptyset$ and $E_{1/2} = \{h_1, \dots, h_d\}$ with $v_1(h_k) = v$ for all $1 \leq k \leq d$ (see Figure 1). ♦
<figure><img src="image_3.png" /><figcaption>FIGURE 1. The half-edge star $S_d^{1/2}$.</figcaption></figure>

As another example, let us define the disjoint union of two graphs $H = (V, E_1, E_{1/2}, v_0, v_1)$ and $H' = (V, E'_1, E'_{1/2}, v'_0, v'_1)$ to be the graph

$$H + H' \stackrel{\text{def}}{=} (V, E_1 \cup E'_1, E_{1/2} \cup E'_{1/2}, v''_0, v''_1),$$

in which, $'+'$ is the disjoint union binary operation on sets and $v''_0, v''_1$ are the corresponding maps defined as

$$v''|_{E_1} \stackrel{\text{def}}{=} v_0, \quad v''|_{E'_1} \stackrel{\text{def}}{=} v'_0, \quad v''|_{E_{1/2}} \stackrel{\text{def}}{=} v_1 \quad \text{and} \quad v''|_{E'_{1/2}} \stackrel{\text{def}}{=} v'_1.$$

In what follows we may also talk about splitting an edge, say $e = uw$, into two half-edges $ue_u$ and $we_w$, or we may talk about joining two half-edges, say $uh_1$ and $wh_2$, to make an edge $h = uw$. Note that in this setting, by an abuse of notation, if we are actually talking about the new constructs, then we always assume that in the new structure as a graph, the sets of edges and half-edges are modified according to the new names assigned to the new edges and half-edges, respectively, however, we may also refer to an edge $e = uw$ along with its splitting as $\psi(e) \stackrel{\text{def}}{=} \{ue_u, we_w\}$ without actually considering the new graph in which this splitting has occurred (for the splitting construction see Definition 2). Also, we take it for granted that for any loop $e$ on a vertex $u$, the splitting procedure results in two different half-edges, say $ue_{u1}$ and $ue_{u2}$, i.e. $\psi(e) \stackrel{\text{def}}{=} \{ue_{u1}, ue_{u2}\}$.

Using this nomenclature, given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, we define the set $\tilde{E}_H$ to be the union of the sets $E_{1/2}$ and the set of all half-edges obtained by splitting edges existing in $E_1$, i.e.

$$\tilde{E}_H \stackrel{\text{def}}{=} E_{1/2} \cup \bigcup_{e \in E_1} \psi(e).$$

Hence, let us define the splitting operation on graphs as follows.

**Definition 2. The splitting and pairing constructions**

Given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, the splitting of $H$ denoted by $\psi(H) = (\tilde{V}, \tilde{E}_1, \tilde{E}_{1/2}, \tilde{v}_0, \tilde{v}_1)$ is a graph defined as follows,

* $\tilde{V} = V$, $\tilde{E}_1 = \emptyset$, $\tilde{E}_{1/2} = \tilde{E}_H$ and

* $\forall uh \in E_{1/2}$, $\tilde{v}_1(uh) = \{u\}$,

* $\forall ue_u \in \tilde{E}_H$, $\tilde{v}_1(ue_u) = \{u\}$ and
• $\tilde{v}_0$ is the empty mapping.

On the other hand, given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, a pairing on (the half-edges) of $H$ is a subset $\partial(E_{1/2}) \subseteq E_{1/2}^{=2}$ such that each half-edge appears in at most one of the elements of $\partial(E_{1/2})$. A pairing construction on a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$ along with a pairing $\partial(E_{1/2})$ gives rise to a new graph $\partial(H) \stackrel{\text{def}}{=} (V', E'_1, E'_{1/2}, v'_0, v'_1)$ defined as follows,

• $V' = V$,

• $E'_1 = E_1 \cup \{e_{uh|wg} \mid \exists \{uh, wg\} \in \partial(E_{1/2}) \& u \neq w\} \cup \{e_{uh|ug} \mid \exists \{uh, ug\} \in \partial(E_{1/2})\}$,

• $E'_{1/2} = E_{1/2} - \bigcup_{P \in \partial(E_{1/2})} P$,

• $v'_0|_{E_1} = v_0|_{E_1}$, $v'_0(e_{uh|wg}) = \{u, w\}$, $v'_0(e_{uh|ug}) = \{u\}$,

• $\forall uh \in E'_{1/2}$, $v'_1(uh) = \{u\}$.

Clearly, given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, one may define the intrinsic pairing of $H$, denoted by $\partial_H$, as a pairing on its splitting $\psi(H)$, i.e.

$$ \{uh, wg\} \in \partial_H(\tilde{E}_{1/2}) \Leftrightarrow \exists e \in E_1, \psi(e) = \{uh, wg\}. $$

Note that, as a direct consequence of definitions we have

$$ \partial_H(\psi(H)) \simeq H. $$

<figure><img src="image_4.png" /></figure>

A direct consequence of the splitting and pairing constructions is a reinterpretation of the graph structure defined in Definition 1 as follows. Given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, one may decompose the data defining the structure into two components, namely, the splitting which is a graph without any undirected edge along with the intrinsic pairing, as $H \simeq (\psi(H), \partial_H)$, hereafter referred to as the *pairing representation of H*. Clearly, the two presentations $H = (V, E_1, E_{1/2}, v_0, v_1)$ and $H = (\psi(H), \partial_H)$ are equivalent and define the same graph structure. In the sequel, we will see that the second interpretation in terms of splitting and pairing may turn out to be more handy when one considers some new lift constructions that will be defined later or when we are dealing with the configuration model of random graphs and random lifts in this setup.

**Definition 3. The $\pi$-lift construction**

A $\pi$-lift construction is actually a cylindrical graph construction in which the new graph is constructed using the data of a given graph along with a labeling of all of its half-edges with members of $S_2$ (see [21] for the details in a more general setting). To be more precise, given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$ and a labeling $\ell: \tilde{E}_H \to S_2$, the $\pi$-lift of $H$ using $\ell$ is the graph $\pi_\ell(H) = (V^\ell, E_1^\ell, E_{1/2}^\ell, v_0^\ell, v_1^\ell)$ defined as follows,

$$ \text{PL1)} \quad V^\ell \stackrel{\text{def}}{=} V \times \{1, 2\}. $$

$$ \text{PL2)} \quad E_1^\ell \stackrel{\text{def}}{=} \{u^\ell | u \in V\} \cup \{e^\ell | e \in E_1\}. $$
<figure><img src="image_5.png" /><figcaption>FIGURE 2. Different $\pi$-lifts of an edge $e = uv$ with a labeling $\ell: \{ue_u, ve_v\} \to S_2$; e.g. in Figure (b), note that we use $\{u_1, u_2\}$ instead of using the product set $\{u\} \times \{1, 2\}$ for convenience. We have $v_0^\ell(u^\ell) = \{u_1, u_2\}$ and $v_0^\ell(v^\ell) = \{v_1, v_2\}$. In each case, $e^\ell$ is the edge constructed by pairing two half-edges (depicted by dotted lines), having the associated labels.</figcaption></figure>

$$ \text{PL3)} \quad E_{1/2}^{\ell} \stackrel{\text{def}}{=} \{h^{\ell} \mid h \in E_{1/2}\}. $$

$$ \begin{array}{l} \text{PL4)} \quad \forall u \in V, \quad v_0^\ell(u^\ell) \stackrel{\text{def}}{=} \{(u, 1), (u, 2)\}, \\ \quad \forall e \in E_1 \quad [v_0(e) = \{u, w\}], \quad v_0^\ell(e^\ell) \stackrel{\text{def}}{=} \{(u, \ell(ue_u)(1)), (w, \ell(we_w)(1))\}, \\ \quad \forall e \in E_1 \quad [v_0(e) = \{u\}], \quad v_0^\ell(e^\ell) \stackrel{\text{def}}{=} \{(u, \ell(ue_1)(1)), (w, \ell(ue_2)(1))\}. \end{array} $$

$$ \text{PL5)} \quad v_1^\ell(h^\ell) \stackrel{\text{def}}{=} (v_1(h), \ell(h)(1)). $$

Let $d \ge 1$ be an integer. Then a labeling $\ell: \tilde{E}_H \to S_2$ of a 2d-regular graph $H = (V, E_1, E_{1/2}, v_0, v_1)$ is said to be *regular* if,

$$ \forall u \in V, |\{uh \in \tilde{E}_H \mid \ell(uh) = id\}| = |\{uh \in \tilde{E}_H \mid \ell(uh) = \tau\}| = d. $$

Hence, a $\pi$-lift of a 2d-regular graph $H$ by a regular labeling is said to be a *regular* $\pi$-lift of $H$, which is, clearly, a $(d+1)$-regular graph.

Given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$ and a labeling $\ell: \tilde{E}_H \to S_2$, we define the $\pi$-lift of a pairing $\partial(E_{1/2})$ using $\ell$ as follows,

$$ \pi_{\ell}(\partial(E_{1/2})) \stackrel{\text{def}}{=} \{\{h_1^{\ell}, h_2^{\ell}\} \in (E_{1/2})^{=2} \mid \{h_1, h_2\} \in \partial(E_{1/2})\}. $$

In what follows, we may refer to the pairing $\pi_{\ell}(\partial(E_{1/2}))$ as $\partial^{\ell}(E_{1/2}^{\ell})$ or just $\partial^{\ell}$ if the original pairing $\partial$ on $H$ is clear from the context. In particular, the $\pi$-lift of the intrinsic pairing of $H$ is denoted by $\partial_H^\ell$. $\blacktriangle$

### Example 2. Some examples of $\pi$-lift construction

Let us explicitly mention the pathological case of the $\pi$-lift of the trivial graph $K_1$, having the vertex set $V = \{u\}$, which is a graph with just an edge on two vertices $\{u_1, u_2\}$. Also, all possible $\pi$-lifts of the graph $K_2$, with the vertex set $V = \{u, v\}$, are depicted in Figure 2.

It is known that a large number of graph products are essentially symmetric cylindrical constructs (see [7, 21] for more details). In particular, it is interesting to recall that the Petersen graph is actually a regular $\pi$-lift of the complete graph on five vertices (see Figure 3).

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /><figcaption>FIGURE 3. (a) The graph $K_5$ along with a regular labeling $\ell$ (b) The Petersen graph generated through a $\pi$-lift construction (thick edges are the new edges coming from the $\pi$-lift construction).</figcaption></figure>

Now let us just provide a precise definition for the iterated $\pi$-lift construction. Clearly, given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, one may consider an iteration of $\pi$-lifts of $H$ using a properly chosen series of labelings applied to lifts of $H$, consecutively. To be more precise, and also to fix some notations, let $\ell_0$ be a labeling of $H$ and also let $H_1 = \pi_{\ell_0}(H)$ be the corresponding $\pi$-lift construction. Then one may consider a new labeling $\ell_1$ on $H_1$ and let $H_2 = \pi_{\ell_1}(H_1)$ be the next $\pi$-lift according to $\ell_1$. Clearly, this series of $\pi$-lifts may be considered as far as such a construction may be applied legitimately using the given labeling, say for $t \ge 1$ stages. In what follows, we refer to such a tower of $\pi$-lifts as an iterated $\pi$-lift construction using a series of labelings $\ell_0, \dots, \ell_{t-1}$, denoted by $\pi_{\ell_0, \dots, \ell_{t-1}}(H)$.

The following proposition records the main properties of the $\pi$-lift construction<fnref n="3" /> (see [21] for more on basic properties of cylindrical constructions).

**Proposition 1.** Given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$ along with a labeling $\ell$, the following statements hold.

a) If $H$ is a connected graph, then $\pi_\ell(H)$ is also a connected graph.

b) The $\pi$-lift construction commutes with the splitting construction through pairing in the sense that

$$ \pi_{\ell}(H) \simeq \partial_{H}^{\ell}(\pi_{\ell}(\psi(H))), $$

i.e. the following diagram is commutative,

<footnote n="3">³The main facts of Proposition 1 are also true for a larger class of cylindrical constructions, e.g. as those defined in [8].</footnote>
<figure><img src="image_8.png" /></figure>

c) An iterated $\pi$-lift of $S_d^{1/2}$ using a series of labelings $\ell = \ell_0, \dots, \ell_{t-1}$ gives rise to a half-edge tree on $2^t$ vertices and $d$ half-edges. Moreover, any iterated $\pi$-lift of a general graph $H$ on $n$ vertices may be described as a pairing on $n$ half-edge trees.

Proof.

a) Note that for any $\{i, j\} \subseteq \{1, 2\}^2$ and any $\{u, w\} \subseteq V^2$ there is a path of length at most three between $(u, i)$ and $(w, j)$ in the $\pi$-lift $\pi_{\ell}(H)$. Hence, any path in $H$ lifts to a walk in $\pi_{\ell}(H)$ with the same endpoints.

b) Note that the commutation property essentially means that applying the $\pi$-lift construction on $H$ using the labeling $\ell$ is equivalent to applying the same $\pi$-lift construction on the representation $H = (\psi(H), \partial_H)$ componentwise, i.e.

$$ \pi_{\ell}(H) \simeq (\pi_{\ell}(\psi(H)), \pi_{\ell}(\partial_H)). $$

Hence, noting that both graphs are defined on the same vertex set, it is sufficient to verify that extending the following map to be an identity map on the lift edges $u^{\ell}$'s, is actually an isomorphism of graphs,

$$ \forall e \in E_1 [\psi(e) = \{uh, wg\}], \quad e^{\ell} \mapsto e_{u^{\ell}(h)(1)} h^{\ell|w|_{\ell}(g)(1)} s^{\ell}. $$

c) Let $V(H) = \{u\}$ and verify that, by Part (a), any iterated $\pi$-lift of $H$ as $\pi_{\ell_0, \dots, \ell_{t-1}}(H)$ is a connected graph on $2^t$ vertices which has $2^t - 1$ edges, and consequently, it is a half-edge tree. On the other hand, by Part (b) an iterated $\pi$-lift of $H$ may be described as the iterated $\pi$-lift of its pairing representation on the splitting of $H$ that actually is a union of half-edge stars. Consequently, since any iterated $\pi$-lift of each of these stars is a half-edge tree by the previous part, the claim follows.

□

Comparing a $\pi$-lift to the concept of a 2-lift (e.g. see [3, 7, 22] and references therein) it is interesting to note that connectivity is not necessarily preserved by 2-lifts (also see Section 4 and Figure 5 for more on this observation), hence, intuitively, indicating a signature of better expansion properties of $\pi$-lifts in general.

## 2.1. Some random graph ensembles and contiguity of models.

In this article we are dealing with random regular graphs. Naturally, considering Definition 1 of a graph, one may define the ensembles $U_{n,d}$ and $SU_{n,d}$ as the spaces of random regular multigraphs of degree $d$ and random regular simple graphs of degree $d$, chosen uniformly at random on the set of vertices $V = \{1, \dots, n\}$, respectively.
On the other hand, one may try to define randomization in terms of the pairing representation as follows. Let us recall Definition 2, essentially stating that any half-edge graph, as $H$, may be described through its pairing representation as its splitting, consisting of a union of half-edge stars, along with the data contained in its intrinsic pairing that describes the way these half-edges must be paired to reconstruct the graph itself, i.e. $H \simeq (\psi(H), \partial_H)$. Then, within this setup, the main result of Proposition 1 states that the $\pi$-lift construction naturally operates on each component of this new representation in terms of pairings.

Hence, the above setup along with Proposition 1 guarantees that using this new representation of graphs in terms of pairings, one may apply all transformations naturally on the pairing representation, and consequently using this, one may try to choose the pairing or the commuting cylindrical construction (or both) at random in a predefined way to define some new ensembles of random graphs.

Although, the study of the iterated $\pi$-lift model was the ultimate motivation initiating this study, but since in this article we are just concentrating on the regular $\pi$-lift model itself, let us define a couple of well-known and new random graph ensembles that will be needed later in our study in what follows. It is instructive to note that this approach applied to the definition of a graph without considering any cylindrical construction, naturally rediscover the definition of the well studied configuration model^4 for random regular graphs by just applying the randomness to the pairing construction. In what follows, $\mathcal{P}_{n,d}$, denotes this configuration model as the ensemble of random $d$-regular graphs on the set of vertices $V = \{1, \dots, n\}$ generated using random pairings on $n$ half-edge stars $S_d^{1/2}$. Note that objects of this ensemble are actually multigraphs by Definition 1, while $S\mathcal{P}_{n,d} \subseteq \mathcal{P}_{n,d}$ stands for the subspace of the simple $d$-regular graphs in this ensemble.

On the other hand, one may consider random $\pi$-lifts^5 within the above context leading to the following definition.

**Definition 4. Random $\pi$-lifts**

Given a graph $H = (V, E_1, E_{1/2}, v_0, v_1)$, a random $\pi$-lift of $H$ is a random graph obtained as a $\pi$-lift of $H$ with respect to a random labeling $\ell: \tilde{E}_H \to S_2$ that assigns random labels to half-edges according to uniform distribution (i.e. probability $1/2$ for each element of $S_2$). If $H$ is a $2d$-regular graph, then a random regular $\pi$-lift of $H$ is a random $(d+1)$-regular graph which is constructed as a random $\pi$-lift of $H$ with respect to a random labeling $\ell$, chosen uniformly at random (e.g. see a construction of the Petersen graph as a regular $\pi$-lift of the complete graph on 5 vertices in Example 2).

In what follows, the ensemble $\mathcal{P}_{n,d}^\pi$ stands^6 for the space of random regular graphs obtained by taking a random $2(d-1)$-regular multigraph $H$ from the configuration model, i.e. $H \in \mathcal{P}_{n/2, 2(d-1)}$ for some even integer $n$ and then applying a random regular $\pi$-lift construction to $H$.

<footnote>^4The configuration model was first introduced, under the condition of regularity, as a model of generating random regular graphs. The model also appears in the literature as the *pairing model* in [23] which is quite justified by Proposition 1, and consequently, our notation. Note that based on our pairing representation one may generalize this model to generate random multigraphs in general, while given a distribution $\sigma$ on the set of natural numbers $\mathbb{N}$ to choose the splitting along with a distribution for random pairings. Naturally, this redefines the classical configuration model for $d$-regular graphs when $\sigma$ is fully concentrated on the number $d$ with probability equal to one.</footnote>

<footnote>^5Or more complex commuting cylindrical constructions not studied in this article.</footnote>

<footnote>^6Note that hereafter parameters appearing in our notations indicate the parameters of the graphs within the ensemble, not the parameters of the graphs used in the construction.</footnote>
Similarly, when $n$ is an even integer, then $U_{n,d}^{\pi}$ and $SU_{n,d}^{\pi}$ stand for the ensembles corresponding to randomization of the standard representation of graphs according to the uniform distribution. ▲

In this regard, let us recall that by Proposition 1 we have $\pi_{\ell}(H) \simeq (\pi_{\ell}(\psi(H)), \pi_{\ell}(\partial_{H}))$, indicating that the random structure is actually produced by the second component of the representation, since for the first component the $\pi$-lift construction just replaces a vertex $u$ by a simple edge $u_1u_2$. This observation turns out to be quite important when we are going to consider contiguity properties of these models, where one may also wish to consider a similar model in which some random pairings are applied to a randomly chosen perfect matching.

In particular, although, expansion, as the main parameter of interest in this article, is not sensitive to relabeling of vertices, in order to provide a better presentation, with an emphasis on using the existing results in the literature, it is instructive to define a symmetrization of the random $\pi$-lift model, in which, instead of applying a random pairing to a fixed perfect matching, we let the starting perfect matching be chosen at random too.

**Definition 5.** In what follows, $\bar{\mathcal{P}}_{n,d}^{\pi}$ stands for a variant of the $\pi$-lift model in which, at first, a uniformly random perfect matching is chosen on the vertex set $V = \{1, \dots, n\}$ and then the $d-1$ half edges adjacent to each vertex is paired randomly according to a randomly chosen pairing structure. Note that the ensembles $\bar{\mathcal{P}}_{n,d}^{\pi}$ and $\mathcal{P}_{n,d}^{\pi}$ are essentially equivalent up to permutations of the labels of vertices (also see Corollary 1). ▲

Before we proceed, let us recall some standard definitions of contiguity for random ensembles.

**Definition 6.** [13] Let $(\Omega_n, \mathcal{F}_n)_{n \in \mathbb{N}}$ be a sequence of arbitrary measurable spaces.

(1) Let $(P_n)_{n \in \mathbb{N}}$ be a sequence of probability measures on $(\Omega_n, \mathcal{F}_n)_{n \in \mathbb{N}}$ and $A_n \in \mathcal{F}_n$, for any $n \in \mathbb{N}$, be a measurable set. We say that $(A_n)_{n \in \mathbb{N}}$ happens asymptotically almost surely or a.a.s. for short, if $\lim_{n \to \infty} P_n(A_n) = 1$.

(2) Let $(P_n)_{n \in \mathbb{N}}$ and $(Q_n)_{n \in \mathbb{N}}$ be sequences of probability measures on $(\Omega_n, \mathcal{F}_n)_{n \in \mathbb{N}}$ componentwise. We say that the sequence $(P_n)_{n \in \mathbb{N}}$ is contiguous with respect to $(Q_n)_{n \in \mathbb{N}}$, if for every sequence of measurable sets as $A_n \in \mathcal{F}_n$,

$$ \lim_{n \to \infty} P_n(A_n) = 0 \iff \lim_{n \to \infty} Q_n(A_n) = 0. $$

Also, we say that these sequences of measures are (mutually) contiguous if for every sequence of measurable sets as $A_n \in \mathcal{F}_n$,

$$ \lim_{n \to \infty} P_n(A_n) = 0 \iff \lim_{n \to \infty} Q_n(A_n) = 0. $$

▲

Recall that if $\mathcal{G}$ and $\mathcal{G}'$ are two ensembles of random graphs on the same vertex set, then their sum (or the disjoint union), $\mathcal{G} + \mathcal{G}'$, is defined to be the ensemble whose elements are random graphs $G + G'$, where $G \in \mathcal{G}$ and $G' \in \mathcal{G}'$ are generated independently from the given ensembles.

**Theorem A.** [14] If $d \ge 1$ then $SU_{n,d}$ is contiguous with respect to $\mathcal{P}_{n,d}$. Moreover, if $d \ge 3$ then $\mathcal{P}_{n,d-1} + \mathcal{P}_{n,1}$ and $\mathcal{P}_{n,d}$ are (mutually) contiguous.
**Corollary 1.** For integers $n \ge 2$ and $d \ge 3$, if $n$ is even then $\bar{\mathcal{P}}_{n,d}^{\pi}$ and $\mathcal{P}_{n,d}$ are (mutually) contiguous.

*Proof.* First, note that the model $\bar{\mathcal{P}}_{n,d}^{\pi}$ is equivalent to $\mathcal{P}_{n,d-1} + \mathcal{P}_{n,1}$ by definitions and Proposition 1, in which the random matching in $\bar{\mathcal{P}}_{n,d}^{\pi}$ is essentially the component $\mathcal{P}_{n,1}$ in the model $\mathcal{P}_{n,d-1} + \mathcal{P}_{n,1}$. Consequently, the contiguity follows by Theorem A. $\square$

### 3. EXPANSION LOWER BOUNDS

Our main objective in this section is to introduce an approach that provides a lower bound for the asymptotic expansion of the random $\pi$-lift model $\mathcal{P}_{n,d}^{\pi}$. The core of this approach is a method already used in [5] by Bollobás that uses a double counting technique, transforming the asymptotic expansion lower bound to a large deviation problem, however, we also provide a relaxation of the optimization problem by transforming the data of the graph structure into a real-relaxation by degree-configuration vectors at the same time. Then, in a second stage and using properties of the $\pi$-lift structure, we reduce the whole space of cuts used in the double counting method into a more limited space of degree-configuration vectors that will give rise to an improvement in obtaining expansion lower bounds for our random graph models, and consequently, for the configuration model by contiguity.

To begin, let us recall some definitions and fix some notations. Given a graph $G = (V, E)$ of order $|V| = n$, any subset $S \subseteq V$ determines a cut $(S, S^c)$ whose size is denoted by $|\partial S|$, as the size of the set of edges with precisely one end-vertex in $S$. Hereafter, we may just refer to the first component $S$, as the *inner part*, to specify the cut whose order is defined to be equal to $|S|$. In what follows we denote the set of all cuts of the graph $G$ by $C(G)$ and also we define

$$C_{1/2}(G) \stackrel{\text{def}}{=} \{S \subset V \mid |S| \le n/2\}.$$

For a given cut $S \in C(G)$, we may refer to the relative *out-degree* of a vertex $u \in S$ with respect to $S$ as,

$$\mathrm{outd}_S(u) = |\{v \in V \setminus S \mid uv \in E\}|.$$

Within this setting, one may define the *expansion* of a cut $S$ as

$$h_G(S) \stackrel{\text{def}}{=} \frac{|\partial S|}{|S|},$$

and along the same line, the *expansion* and the *bisection width* of the graph $G$ are defined as,

$$h(G) \stackrel{\text{def}}{=} \min_{C_{1/2}(G)} h_G(S),$$

and

$$\mathrm{bw}(G) \stackrel{\text{def}}{=} \min_{(n-1)/2 \le |S| \le n/2} |\partial S|,$$

respectively, where, in the sequel, the set of all minimal cuts in relation to the expansion problem, is denoted by

$$\mathcal{M}(G) \stackrel{\text{def}}{=} \{S \in C_{1/2}(G) \mid h(G) = h_G(S)\}.$$
In what follows, for a given vector $f = (f_0, \dots, f_r)$ of non-negative entries we use the following notations,

$$|f| \stackrel{\text{def}}{=} \sum_{k=0}^{r} f_k, \quad E(f) \stackrel{\text{def}}{=} \sum_{k=1}^{r} k f_k, \quad \text{and} \quad \kappa(f) \stackrel{\text{def}}{=} \max\{k : f_k > 0\}.$$

In particular, the non-negative vector $\mu_p \in \mathbb{R}^{d+1}$ is defined as,

$$\forall 0 \le k \le d \quad \mu_k^p \stackrel{\text{def}}{=} \binom{d-1}{k-p},$$

where $\mu_k^p \stackrel{\text{def}}{=} 1$ when $p > k$.

Given a real number $0 \le x \le 1$ and a vector of real numbers $\zeta = (\zeta_1, \dots, \zeta_r)$ for which $0 \le \zeta_i \le 1$ and $|\zeta| = 1$, we define

$$I(x) \stackrel{\text{def}}{=} x \log x, \quad H(\zeta) \stackrel{\text{def}}{=} - \sum_{i=1}^{r} I(\zeta_i),$$

in which we always assume that $0 \times \log(0) = 0$.

For an even integer $n \in \mathbb{N}$, the number of matchings of an $n$-element set is denoted by

$$N(n) \stackrel{\text{def}}{=} (n-1)!! = (n-1) \times (n-3) \cdots 3 \times 1.$$

Using Stirling's approximation, it is straight forward to verify that,

$$N(n) = (1 + o(1)) \sqrt{2} (n/e)^{n/2},$$

while also Stirling's formula yields the following approximation, which is valid when $n$ and $k$ both tend to infinity and $k = \Omega(n)$,

$$\lim_{n \to \infty} \frac{1}{n} \log \binom{n}{k} = H\left(\frac{k}{n}\right).$$

As our main target in this article, the (normalized) optimal expansion lower bound for an ensemble $\mathcal{E}$ of random $d$-regular graphs is defined as

$$\overline{\text{ELB}}(\mathcal{E}) \stackrel{\text{def}}{=} \sup \left\{ 0 < \eta < 1 \mid \lim_{n \to \infty} \mathbb{P}_{\mathcal{E}} \left( \eta < \frac{h(G_n)}{d} \right) = 1 \right\}.$$

For any $d \ge 3$, given a random $d$-regular graph $G_n \in \mathcal{P}_{n,d}^\pi$ with a fixed perfect matching determined by an involution $\sigma$ on $[n]$, let us consider a cut $S \in C_{1/2}(G_n)$ with $|S| = s$ (see Figure 4). Also, let $a^S$ denote the number of edges in the perfect matching $\sigma$ that appear as cut-edges. Then, we have

$$|\{u \in [n] \mid u \in S, \sigma(u) \in S\}| = s - a^S, \quad |\{u \in [n] \mid u \in S^c, \sigma(u) \in S^c\}| = n - s - a^S.$$
<figure><img src="image_9.png" /><figcaption>FIGURE 4. Example of a cut S with $|S| = s$ in a graph $G_n \in \mathcal{P}_{n,3}^\pi$ with $a^S = 3$.</figcaption></figure>

Within this setting, the entries of the $d$-dimensional degree-configuration vectors $(f_{1,S}, \tilde{f}_{1,S})$ and $(f_{2,S}, \tilde{f}_{2,S})$ of the cut S are defined as

$$ \forall k \in [d]_0, \quad f_k^{1,S} \stackrel{\text{def}}{=} |\{i \in S \mid \sigma(i) \in S, \text{outd}_S(i) = k\}|, \quad f_k^{2,S} \stackrel{\text{def}}{=} |\{i \in S \mid \sigma(i) \in S^c, \text{outd}_S(i) = k\}|, $$

$$ \forall k \in [d]_0, \quad \tilde{f}_k^{1,S} \stackrel{\text{def}}{=} |\{i \in S^c \mid \sigma(i) \in S^c, \text{outd}_{S^c}(i) = k\}|, \quad \tilde{f}_k^{2,S} \stackrel{\text{def}}{=} |\{i \in S^c \mid \sigma(i) \in S, \text{outd}_{S^c}(i) = k\}|. $$

Note that if $|\partial S| = c$, then we have

$$ E(f_{1,S}) + E(f_{2,S}) = E(\tilde{f}_{1,S}) + E(\tilde{f}_{2,S}) = c. $$

Also, we define the maximum non-zero indices of these degree vectors as

$$ r_S \stackrel{\text{def}}{=} (\kappa(f_{1,S}), \kappa(f_{2,S}), \kappa(\tilde{f}_{1,S}), \kappa(\tilde{f}_{2,S})). $$

In order to provide a lower bound for $\overline{\text{ELB}}(\mathcal{P}_{n,d}^\pi)$ through a real relaxation of the parameters and relations defined above, let us consider the normalized parameters and probability vectors defined as follows,

$$ \left\{ \begin{array}{l} s \stackrel{\text{def}}{=} s/n, \quad c \stackrel{\text{def}}{=} c/n, \quad \alpha^S \stackrel{\text{def}}{=} a^S/n, \\ \\ \forall k \in [d]_0, \quad \ell_k^{1,S} \stackrel{\text{def}}{=} f_k^{p,S} \times 1/(s-a^S), \quad \ell_k^{2,S} \stackrel{\text{def}}{=} f_k^{2,S} \times 1/(a^S), \\ \\ \forall k \in [d]_0, \quad \tilde{\ell}_k^{1,S} \stackrel{\text{def}}{=} \tilde{f}_k^{1,S} \times 1/(n-s-a^S), \quad \tilde{\ell}_k^{2,S} \stackrel{\text{def}}{=} \tilde{f}_k^{2,S} \times 1/(a^S), \end{array} \right. $$

which satisfy,

$$ (s - \alpha^S) E(\ell_{1,S}) + \alpha^S E(\ell_{2,S}) = (1 - s - \alpha^S) E(\tilde{\ell}_{1,S}) + \alpha^S E(\tilde{\ell}_{2,S}) = c. \quad (1) $$

Our first step to simplify the problem is to apply a Lagrange multiplier method to get rid of the degree-configuration vectors. The details of this will actually appear within the proof of Theorem 1, where in the following definition we prepare the setup and introduce the relaxed expansion lower bound.
**Definition 7.** Given a real number $0 < \eta < 1$ and a tuple of integers

$$r = (r_1, r_2, \tilde{r}_1, \tilde{r}_2) \le (d-1, d, d-1, d)$$

let us consider for any $(s, c, \alpha) \in [0, 1/2] \times [0, ds\eta] \times [0, c]$ the following equations for $y \in \mathbb{R}_+$ and $\tilde{y} \in \mathbb{R}_+$,

$$ 
\left\{ 
\begin{array}{l}
Q(r_1, r_2, y) \stackrel{\text{def}}{=} (s - \alpha) y \frac{\partial}{\partial y} \log \Delta(d-1, r_1, y) + \alpha y \frac{\partial}{\partial y} \log \Delta(d-1, r_2 - 1, y) - (c - \alpha) = 0, \\
\\
\tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}) \stackrel{\text{def}}{=} (1 - s - \alpha) \tilde{y} \frac{\partial}{\partial \tilde{y}} \log \Delta(d-1, \tilde{r}_1, \tilde{y}) + \alpha \tilde{y} \frac{\partial}{\partial \tilde{y}} \log \Delta(d-1, \tilde{r}_2 - 1, \tilde{y}) - (c - \alpha) = 0,
\end{array}
\right.
\quad (2) $$

in which

$$ \Delta(d, r, y) \stackrel{\text{def}}{=} \sum_{k=0}^{r} \binom{d}{k} y^k. $$

By defining the parameter space,

$$ \mathcal{D}(r, \eta) \stackrel{\text{def}}{=} \{ \varphi \stackrel{\text{def}}{=} (s, c, \alpha, y_0, \tilde{y}_0) \mid s \in [0, 1/2], c \in [0, ds\eta], \alpha \in [0, c], Q(r_1, r_2, y_0) = 0, \tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_0) = 0 \}, $$

and also the function

$$ L(t, c, \alpha, z, d, r, r') \stackrel{\text{def}}{=} -1/2 (I(t - \alpha) + I(\alpha)) + (d-1)/2 \left( I(t - \frac{c - \alpha}{d-1}) + I(\frac{c - \alpha}{d-1}) \right) \\ + (t - \alpha) \log \Delta(d-1, r, z) + \alpha \log \Delta(d-1, r', z) - (c - \alpha) \log z, $$

one may define the relaxed expansion lower bound of the ensemble $\mathcal{P}_{n,d}^{\pi}$ to be

$$ \overline{\text{RELB}}_{\pi}(\mathbf{r}) \stackrel{\text{def}}{=} \sup \left\{ 0 < \eta < 1 \mid \max_{\varphi \in \mathcal{D}(r, \eta)} \text{L}\Gamma_r \varphi < 0 \right\}, $$

in which

$$ \text{L}\Gamma_r(\varphi) \stackrel{\text{def}}{=} L(s, c, \alpha, y, d, r_1, r_2 - 1) + L(1 - s, c, \alpha, \tilde{y}, d, \tilde{r}_1, \tilde{r}_2 - 1). $$

▲

Let us define

$$ r_{\pi}^{\infty} \stackrel{\text{def}}{=} \left\{ r = (r_1, r_2, \tilde{r}_1, \tilde{r}_2) \mid \lim_{n \to \infty} \mathbb{P} \left( \exists S \in \mathcal{M}(G_n), r_S \le r \right) = 1 \right\}, $$

for the ensemble $\mathcal{P}_{n,d}^{\pi}$. Then we are ready to state our first result as follows, showing that $\overline{\text{RELB}}_{\pi}(\mathbf{r})$ is a relaxation of $\overline{\text{ELB}}(\mathcal{P}_{n,d}^{\pi})$.

**Theorem 1.** Given an integer $d \ge 3$, for any $r \in r_{\pi}^{\infty}$ we have $\overline{\text{RELB}}_{\pi}(\mathbf{r}) \le \overline{\text{ELB}}(\mathcal{P}_{n,d}^{\pi})$.

*Proof.* See Appendix A.1. □

The following lemma is actually a direct consequence of Theorem 1, and is our main motivation for looking for smaller vectors $r$ in what follows.

**Lemma 1.** For any $r_1 \le r_2 \le (d-1, d, d-1, d)$, we have $\overline{\text{RELB}}_{\pi}(\mathbf{r}_2) \le \overline{\text{RELB}}_{\pi}(\mathbf{r}_1)$.
Proof. As discussed in the proof of Theorem 1, we maximize the function $\overline{\mathrm{L}\Gamma_r}$ over the space

$$ \mathcal{D}'(r, \eta) \stackrel{\mathrm{def}}{=} \{ \psi \in [0, 1/2] \times [0, d\delta\eta] \times [0, c] \times [0, 1]^{4(d+1)} \mid \psi \text{ is r-compatible} \}. $$

Hence, one may verify that $\mathcal{D}'(\eta, r_1) \subseteq \mathcal{D}'(\eta, r_2)$, implying that $\overline{\mathrm{RELB}}_\pi(r_2) \le \overline{\mathrm{RELB}}_\pi(r_1)$. $\square$

<figure><img src="image_10.png" /></figure>

**Remark 1.** Note that Lemma 1 indicates that one should look for smaller vectors $r \in r_\pi^\infty$ to get better expansion lower bounds. $\diamond$

<figure><img src="image_11.png" /></figure>

**Remark 2.** It is instructive to compare the statement of Theorem 1 to a similar result for the configuration model. Note that for any $d \ge 3$, just using the same ideas as in the proof of Theorem 1, one could go through the same procedure for random graphs $G_n \in \mathcal{P}_{n,d}$, for which one may just consider two $d$-dimensional degree-configuration vectors $f_S$ and $\tilde{f}_S$ associated to the vertices inside and outside of the cut $S \in C_{1/2}(G_n)$, where for these degree-configuration vectors the maximum non-zero indices are referred to as $(r, \tilde{r}) \le (d, d)$. If one similarly defines

$$ \mathbf{r}_{\mathrm{P}}^{\infty} \stackrel{\mathrm{def}}{=} \left\{ \mathbf{r} \stackrel{\mathrm{def}}{=} (r, \tilde{r}) \mid \lim_{n \to \infty} \mathbb{P} \left( \exists S \in \mathcal{M}(G_n), \mathbf{r}_S \le \mathbf{r} \right) = 1 \right\}, $$

then, for any $r \in r_\pi^\infty$, by defining

$$ \mathcal{W}(r, \tilde{r}, \eta) \stackrel{\mathrm{def}}{=} \left\{ \varphi \stackrel{\mathrm{def}}{=} (\delta, c, y_0, \tilde{y}_0) \mid \delta \in [0, 1/2], c \in [0, d\delta\eta], y_0, \tilde{y}_0 \text{ satisfy Equations 3} \right\}, $$

a (normalized) expansion lower bound for the ensemble $\mathcal{P}_{n,d}$ may be defined as

$$ \overline{\mathrm{RELB}}_{\mathrm{P}}(\mathbf{r}) \stackrel{\mathrm{def}}{=} \sup \left\{ 0 < \eta < 1 \mid \max_{\varphi \in \mathcal{W}(\mathbf{r}, \eta)} \mathrm{LP}_{\mathrm{r}}(\delta, c, y, \tilde{y}) < 0 \right\}, $$

in which

$$ \begin{aligned} \mathrm{LP}_{\mathrm{r}}(\delta, c, y, \tilde{y}) = & H(\delta, 1-\delta) - \frac{d}{2} H(\delta - c/d, 1-\delta - c/d, c/d, c/d) \\ & - c(\log y + \log \tilde{y}) + \delta \log \Delta(d, r, y) + (1-\delta) \log \Delta(d, \tilde{r}, \tilde{y}). \end{aligned} $$

with

$$ \left\{ \begin{array}{l} y \frac{\partial}{\partial y} \log \Delta(d, r, y) = \frac{c}{\delta}, \\ \tilde{y} \frac{\partial}{\partial \tilde{y}} \log \Delta(d, r, \tilde{y}) = \frac{c}{1-\delta}. \end{array} \right. \qquad (3) $$

One may verify (see Proposition 4), and of course it is quite interesting, that for any pair of out-degrees $(r, \tilde{r}) \le (d-1, d-1)$, we have

$$ \overline{\mathrm{RELB}}_{\mathrm{P}}(r, \tilde{r}) = \overline{\mathrm{RELB}}_{\pi}(r, r, \tilde{r}, \tilde{r}) $$

and

$$ \overline{\mathrm{RELB}}_{\mathrm{P}}(d, d) = \overline{\mathrm{RELB}}_{\pi}(d-1, d, d-1, d), $$

where $\overline{\mathrm{RELB}}_{\mathrm{P}}(d, d)$ is exactly the expansion lower-bound obtained in [5]. An intuitive combinatorial justification of these facts ought to add to our feelings about the $\pi$-lift model. $\diamond$

<figure><img src="image_12.png" /></figure>
Our basic goal in what follows is to provide an effective method of computing $\overline{\text{RELB}}_\pi(r)$ (see Theorem 2). In this regard, one has to deal with the solutions of Equations 2, which do not seem to be easy to compute, mainly for the presence of partial binomial sums $\Delta(d,r,y)$. In what follows we are going to prove our results, in a stronger setting, for every point in an interval containing the solutions of these equations, where in this regard, we will be facing two difficulties.

The first challenge is related to the conceptual well-definedness of the expansion lower bound which ought to be reflected in a *uniqueness of solutions* for Equations 2. The second challenge is to choose the intervals appropriately in a way that all we need are valid for the internal points as well as the points outside of the intervals. We will handle the first challenge using a couple of technical facts in Proposition 2.

For the second challenge we first try to justify our proposed interval boundary points in what follows, although, one may just start with the proposed candidates and verify that the whole proofs just go through. To do this, let us recall that given a real-valued bounded function $f$ defined on the interval $[0,1]$, the $d$th Bernstein polynomial approximation of $f$, denoted by $B_d(f)$, is the polynomial function defined on $[0,1]$ that assigns to $x$ the value

$$ \sum_{k=0}^{d} \binom{d}{k} x^k (1-x)^{d-k} f\left(\frac{k}{n}\right). $$

Then note that applying a change of variable from $y$ to $\frac{x}{1-x}$ in Equations 2, one may rewrite these equations in terms of Bernstein polynomials. For instance, the equation $Q(r_1,r_2,y) = 0$ may be rewritten as

$$ (s - \alpha) \omega(d - 1, r_1, x) + \alpha \omega(d - 1, r_2, x) = \frac{c - \alpha}{d - 1}, $$

in which

$$ \omega(d,r,x) \stackrel{\text{def}}{=} \frac{\sum_{k=0}^{r} \frac{k}{d} \binom{d}{k} x^k (1-x)^{d-k}}{\sum_{k=0}^{r} \binom{d}{k} x^k (1-x)^{d-k}}. $$

Now, note that using the identity $\omega(d,d,x) = x$, the function $\omega(d,r,x)$ may be roughly approximated by a linear function. Hence, given an integer $r \le d$, one may just approximately assume that

$$ \omega(d,r,x) \approx x/\delta $$

for some $\delta \ge 1$, and consequently, one may assume that the corresponding approximate solutions of Equations 2 may be described as

$$ y_{\delta} \stackrel{\text{def}}{=} \frac{\delta \frac{c-\alpha}{d-1}}{s - \delta \frac{c-\alpha}{d-1}} \quad \text{and} \quad \tilde{y}_{\delta} \stackrel{\text{def}}{=} \frac{\delta \frac{c-\alpha}{d-1}}{1 - s - \delta \frac{c-\alpha}{d-1}} $$

for some $\delta \ge 1$. In what follows we use the abbreviations $y_1 \stackrel{\text{def}}{=} y_{\delta=1}$ and $\tilde{y}_1 \stackrel{\text{def}}{=} \tilde{y}_{\delta=1}$, while one may note that for fixed parameters $s, c, \alpha$, both $y_\delta$ and $\tilde{y}_\delta$ are increasing functions of $\delta$.

It will be shown in Proposition 4 that $y_1$ and $\tilde{y}_1$ are actually the unique solutions of Equations 2 when $r = (d-1,d,d-1,d)$. However, since in general the solutions of these equations are not known in an explicit form, one needs some lower and upper bounds for $\overline{\text{RELB}}_\pi(r)$ to be able to handle the problem in a general situation. For this, let us define

$$ \eta_d \stackrel{\text{def}}{=} \left( \frac{1}{2} - \sqrt{\frac{\log 2}{d}} \right) $$
and

$$ \bar{\eta}_d \stackrel{\text{def}}{=} (1/2 - 0.64^- / \sqrt{d}). $$

where, actually, $\eta_d$ is the expansion lower-bound obtained in [5] and $\bar{\eta}_d$ is the expansion upper-bound derived in [20]. Furthermore, since $(c-\alpha)/(d-1) \le d\bar{\eta}_d/(d-1)$ one expects to have

$$ \lim_{d \to \infty} \delta \frac{c - \alpha}{d - 1} \le \lim_{d \to \infty} \delta \frac{d\bar{\eta}_d}{(d - 1)} = \frac{1}{2}. $$

As our first step, let us prove in the next proposition that the solutions of Equations 2 are actually of the form $y_\delta$ and $\tilde{y}_\delta$ for some $1 \le \delta \le \bar{\delta}(d)$ where

$$ \bar{\delta}(d) \stackrel{\text{def}}{=} \frac{1}{1 - \frac{1}{\sqrt{d\pi}}}. $$

**Proposition 2.** Given an integer $d \ge 3$, a vector

$$ \mathbf{r} = (r_1, r_2, \tilde{r}_1, \tilde{r}_2) \ge (\lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor), $$

and any $\varphi \in \mathcal{D}(\mathbf{r}, \bar{\eta}_d)$, Equations 2 admit unique solutions $y^* = y_{\delta^*}$ and $\tilde{y}^* = \tilde{y}_{\delta^*}$ over $\mathbb{R}_+^2$, respectively. Moreover, $y_1 \le y^* \le y_{\delta(d)}$ and $\tilde{y}_1 \le \tilde{y}^* \le \tilde{y}_{\delta(d)}$.

*Proof.* See Appendix A.2. $\square$

The next proposition focuses on the behaviour of the function $\mathrm{L}\Gamma_\pi$ with respect to the parameters $\alpha$ and $c$. For the parameter $c$ we prove similar results as in [5], where for $\alpha$, as a new parameter appearing in the optimization problem $\overline{\mathrm{REL}\mathrm{B}}_\pi(\mathbf{r})$, we have to provide an independent analysis. Hence, at first, we show that there is unique parameter $\alpha^*$ maximizing the function $\mathrm{L}\Gamma_\pi$ paving the way to compute $\alpha^*$ numerically, using an iterative convergent algorithm. It is also interesting to mention that when $r_1 = r_2$ and $\tilde{r}_1 = \tilde{r}_2$, the unique solution has a nice expression, implying some surprising asymptotic consequences appearing in Proposition 4.

Note that, the parameter $\alpha$ appears since the ensemble $\mathcal{P}_{n,d}^\pi$ has a predefined perfect matching. This is actually the simplest case of an *iterated random $\pi$-lift model* that asks for more sophisticated analysis (see Section 4 for more on this).

In what follows we use the following function,

$$ \alpha(\delta, x) \stackrel{\text{def}}{=} \left( \frac{(\delta - x)(1 - \delta - x)}{x^2} \right)^{\frac{1}{2}}. $$

**Proposition 3.** Given an integer $d \ge 3$ and a vector

$$ \mathbf{r} = (r_1, r_2, \tilde{r}_1, \tilde{r}_2) \ge (\lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor), $$

if $y_{\delta^*}$ and $\tilde{y}_{\delta^*}$ are the unique solutions of Equations 2, then

$$ (I) \text{ For any fixed } 0 \le \delta \le 1/2 \text{ and } 0 \le c \le d\delta\bar{\eta}_d, $$

i) the function $\mathrm{L}\Gamma_\pi(\delta, c, \alpha, y_{\delta^*}, \tilde{y}_{\delta^*})$ is a concave function on the interval $\alpha \in [0, c]$ with a global maximum achieved at the unique point $\alpha^*$ that satisfies the following equation

$$ \alpha(\delta, \alpha^*) \alpha(\delta, (c - \alpha^*)/(d - 1)) = \frac{\Delta(d - 1, r_1, y_{\delta^*})}{y_{\delta^*} \Delta(d - 1, r_2 - 1, y_{\delta^*})} \frac{\Delta(d - 1, \tilde{r}_1, \tilde{y}_{\delta^*})}{\tilde{y}_{\delta^*} \Delta(d - 1, \tilde{r}_2 - 1, \tilde{y}_{\delta^*})}. \quad (4) $$
ii) the following relations hold,

$$
\left\{
\begin{array}{ll}
a^* = c/d, & r_1 = r_2 \text{ and } \tilde{r}_1 = \tilde{r}_2, \\
a^* < c/d, & r_1 > r_2 \text{ and } \tilde{r}_1 > \tilde{r}_2, \\
a^* > c/d, & r_1 < r_2 \text{ and } \tilde{r}_1 < \tilde{r}_2.
\end{array}
\right.
$$

(II) For any fixed $0 \le s \le 1/2$, the function $\mathrm{L}\Gamma_r(s, c, \alpha^*, y_{s*}, \tilde{y}_{s*})$ is an increasing function of $c$ for all $0 \le c \le ds\tilde{\eta}_d$.

Proof. See Appendix A.3.

<figure><img src="image_13.png" /></figure>

Our next statement provides an interesting and strong relationship between the two asymp-
totic parameters $\overline{\mathrm{RELB}}_{\pi}(\mathbf{r})$ and $\overline{\mathrm{RELB}}_{\mathrm{p}}(\mathbf{r}, \tilde{\mathbf{r}})$, while it does not seem to be straight-forward to
justify this relationship for arbitrary finite graphs from a combinatorial point of view. This, in
its own right, shows that *asymptotically* the random $\pi$-lift model is a legitimate generalization
of the configuration model while it is more restricted than the configuration model when one
considers the whole set of possible sample graphs! In our opinion, providing a purely combi-
natorial justification of this fact may most probably add more to our understanding about the
random $\pi$-lift model.

**Proposition 4.** *Given an integer* $d \ge 3$,

i) We have, $\overline{\mathrm{RELB}}_{\mathrm{p}}(d,d) = \overline{\mathrm{RELB}}_{\pi}(d-1,d,d-1,d)$. Moreover, $\overline{\mathrm{RELB}}_{\mathrm{p}}(d,d)$ is exactly the expansion lower-bound obtained in [5].

ii) For any $(r, \tilde{r}) \le (d-1, d-1)$, we have $\overline{\mathrm{RELB}}_{\mathrm{p}}(r, \tilde{r}) = \overline{\mathrm{RELB}}_{\pi}(r, r, \tilde{r}, \tilde{r}) \le \overline{\mathrm{RELB}}_{\mathrm{p}}(d, d)$.

Proof. see Appendix A.4.

<figure><img src="image_14.png" /></figure>

Now, summing up, the next theorem as our main goal provides a description of the expansion
lowe bound $\overline{\mathrm{RELB}}_{\pi}(\mathbf{r})$ that may be used to effectively approximate this parameter in a compu-
tational approach. For the next theorem we define

$$
\eta'_{d} \stackrel{\text{def}}{=} 1/2 - 0.75/\sqrt{d}.
$$

**Theorem 2.** *Given an integer* $d \ge 3$ *and a vector*

$$
\mathbf{r} = (r_1, r_2, \tilde{r}_1, \tilde{r}_2) \ge (\lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor),
$$

if $\eta_d^*$ is the largest solution of the equation

$$
\mathrm{L}\Gamma_r(1/2, d\eta_d^*/2, \alpha^*, y^*, \tilde{y}^*) = 0,
$$

for $3 \le d \le 11$, and $\alpha^*$ is the unique solution of

$$
\frac{\partial}{\partial \alpha} \mathrm{L}\Gamma_r(1/2, d\eta_d^*/2, \alpha^*, y^*, \tilde{y}^*) = 0,
$$

in which $y^*, \tilde{y}^*$ are the unique solutions of Equations 2, then

$$
d \ge 12 \Rightarrow \overline{\mathrm{RELB}}_{\pi}(\mathbf{r}) = \eta_{d}^{*}.
$$

Moreover,

$$
(3 \le d \le 11 \ \& \ \eta_d^* \le \eta_d') \Rightarrow \overline{\mathrm{RELB}}_{\pi}(\mathbf{r}) = \eta_d^*.
$$
Proof. We know that $\overline{\mathrm{RELB}}_{\pi}(\mathbf{r}) \le \tilde{\eta}_d$. Choose $\alpha^*$ as in Proposition 3. Also, by Proposition 3(II) one may concentrate on the boundary point $c = d\delta\eta$ as far as the parameter $c$ is concerned. Now, taking $y^*$ and $\tilde{y}^*$ as the unique solutions of Equations 2 we claim that,

**Claim 1.** Given $d \ge 3$, let $\eta_d^*$ be the largest solution of $\mathrm{L}\Gamma_r(1/2, d\eta_d^*/2, \alpha^*, y^*, \tilde{y}^*) = 0$. If $\eta_d^* \le \eta_d'$ for all $3 \le d \le 11$, then

$$ \forall d \ge 3 \ \forall \delta \in [0, 1/2] \ \mathrm{L}\Gamma_r(\delta, d\eta_d^*, \alpha^*, y^*, \tilde{y}^*) \le 0. $$

(see Appendix A.5 for the proof of this claim).

Hence, the theorem follows by Proposition 3. $\square$

<figure><img src="image_15.png" /></figure>

It ought to be noted that the idea of applying a real-relaxation using degree-configuration vectors, has already appeared<fnref n="7" /> in [17]. Also, we know that by Proposition 4, not only there is a chance of having a better expansion lower bound for some $(r, \tilde{r}) \in \mathbf{r}_{\pi}^{\infty}$ with $(r, \tilde{r}) < (d, d)$, but using the $\pi$-lift model gives rise to a more relaxed setup based on four parameters $(r_1, r_2, \tilde{r}_1, \tilde{r}_2)$ that eventually may help to improve the lower bound by providing a better combinatorial analysis of out-degree vectors in $\mathbf{r}_{\pi}^{\infty}$ based on the known matching within the structure. Moreover, it seems that the approach of defining the ensemble $\mathcal{P}_{n,d}^{\pi}$ and using Corollary 1, in contrast to the method used<fnref n="8" /> in [18], is more handy for the combinatorial analysis of cuts. Our next proposition states the main result of this combinatorial analysis in this case.

**Proposition 5.** For any $d \ge 3$, given a $d$-regular graph $G_n \in \mathcal{P}_{n,d}^{\pi}$ we have,

i) If $h(G_n) < \zeta_d$ then for any $S \in \mathcal{M}(G_n)$,

$$ \forall u \in S \ \forall v \in S^c \ \mathrm{outd}_S(u) \le \lceil \frac{1}{2}(d + \lceil \zeta_d \rceil) - 1 \rceil, \mathrm{outd}_{S^c}(v) \le \lceil \frac{1}{2}(d + \lceil \zeta_d \rceil) - 1 \rceil. $$

ii) For any $S \in C_{1/2}(G_n)$, if we define

$$ r_S \stackrel{\mathrm{def}}{=} \max \{\kappa(f_{1,S}), \kappa(f_{2,S})\}, \quad \tilde{r}_S \stackrel{\mathrm{def}}{=} \max \{\kappa(\tilde{f}_{1,S}), \kappa(\tilde{f}_{2,S})\}, $$

then one of the following cases holds,

* $\exists S \in \mathcal{M}(G_n) : r_S + \tilde{r}_S \le d,$

* $\forall S \in \mathcal{M}(G_n) : r_S + \tilde{r}_S = d + 1 \ \& \ \max \{f_{r_S}^{1,S} + f_{r_S}^{2,S}, \tilde{f}_{\tilde{r}_S}^{1,S} + \tilde{f}_{\tilde{r}_S}^{2,S}\} \le d.$

iii) For even degrees $d$, if for any $S \in \mathcal{M}(G_n)$ we know that $(\kappa(f_{2,S}), \kappa(\tilde{f}_{2,S})) \le (d/2, d/2)$, then one of the following holds,

* $\exists S \in \mathcal{M}(G_n) : \min \{\kappa(f_{2,S}), \kappa(\tilde{f}_{2,S})\} < d/2,$

* $\forall S \in \mathcal{M}(G_n) : \kappa(f_{2,S}) = \kappa(\tilde{f}_{2,S}) = d/2 \ \& \ \max \{f_{d/2}^{2,S}, \tilde{f}_{d/2}^{2,S}\} \le d/2.$

<footnote n="7">⁷It seems that the preprint is not published yet where some proofs also seem not to be in their final rigorous form.</footnote>

<footnote n="8">⁸It seems that the preprint is not published yet.</footnote>
i) First, let us prove the following claim.

**Claim 2.** Given a real number $k \in \mathbb{R}$ along with a $d$-regular graph $G_n \in \mathcal{P}_{n,d}^\pi$. If there exists $(S, U, m) \in \mathcal{M}(G_n) \times C_{1/2}(G_n) \times \mathbb{N}$ such that

$$ (|S| - |U| \le m \ \& \ \partial S - \partial U \ge k \cdot m) $$

then, we have $h(G_n) \ge k$.

For the proof of the claim, note that by the hypothesis we have

$$ \frac{\partial U}{|U|} \le \frac{(\partial S - k \cdot m)}{(|S| - m)}. $$

But since $S \in \mathcal{M}(G_n)$, then $(\partial S - k \cdot m) / (|S| - m) \ge \partial S / |S|$, which proves the claim. Now, by contradiction, assume that for a minimal cut $S \in \mathcal{M}(G_n)$, there exists a vertex $u \in S$ such that $\text{outd}_S(u) \ge \lceil \frac{1}{2}(d + \lceil \xi_d \rceil) \rceil - 1 \rceil + 1$. Then, by moving the vertex $u$ from $S$ to $S^c$, one reduces the number of cut-edges at least by $\lceil \xi_d \rceil$ for the new cut. Hence, using the above claim we have $h(G_n) \ge \lceil \xi_d \rceil$, which is a contradiction. We can show the claim similarly for the vertices $v \in S^c$.

ii) Given a cut $S \in C_{1/2}(G_n)$, for any two vertices $u \in S$ and $v \in S^c$ which are not connected, if $\text{outd}_S(u) + \text{outd}_{S^c}(v) \ge d + 1$, then by swapping these vertices one obtains a new smaller cut, i.e.

$$ |\partial S| - \text{outd}_S(u) - \text{outd}_{S^c}(v) + d - \text{outd}_S(u) + d - \text{outd}_{S^c}(v) < |\partial S|. $$

By a similar argument for the case of two connected vertices $u \in S$ and $v \in S^c$, if $\text{outd}_S(u) + \text{outd}_{S^c}(v) \ge d + 2$ again one may decrease the size of the cut by a swapping strategy. Hence, the only case to be considered is when $u \in S$ and $v \in S^c$ are connected and $\text{outd}_S(u) + \text{outd}_{S^c}(v) = d + 1$. However, if we have $f_{r_S}^{1,S} + f_{r_S}^{2,S} > d$, then for any $u \in S$ with $\text{outd}_S(u) = r_S$ there is a $v \in S^c$ with $\text{outd}_{S^c}(v) = \tilde{r}_S$ such that $u$ and $v$ are not connected, and consequently, one may again apply a swapping strategy. A similar argument holds for the case when $\tilde{f}_{\tilde{r}_S}^{1,S} + \tilde{f}_{\tilde{r}_S}^{2,S} > d$.

iii) Let us consider a fixed perfect matching on the set of vertices $[n]_1$ and a cut $S \in C_{1/2}(G_n)$ with out-degree vector $r_S = (d/2, d/2, d/2, d/2)$. Suppose $u_1v_1$ and $u_2v_2$ are two cut-edges which are belong to the perfect matching. If we have

$$ \text{outd}_S(u_1) = \frac{d}{2}, \quad \text{outd}_{S^c}(v_2) = \frac{d}{2}. $$

such that $u_1$ and $v_2$ are not connected, then we have a new cut $S' = S \setminus \{u_1\} \cup \{v_2\}$ with the same number of cut-edges. By repeating this process, either there will be a cut with the same expansion as $S$ such that at least one endpoints of the cut-edges coming from the perfect matching, have out-degrees less than $d/2$, or with a similar argument of the part (ii) we have the other case.

□

**Remark 3.** It is important to note that parts (i) and (ii) of Proposition 5 are also true for the configuration model $\mathcal{P}_{n,d}^9$. ♦

<footnote n="9">⁹Proposition 5 (ii) is also one of the claims appearing in [17].</footnote>
In principal Proposition 2 paves the way to find non-trivial small out-degree vectors for any $d \ge 3$ which implies better asymptotic expansion lower-bound for the ensemble $\mathcal{P}_{n,d}^{\pi}$. In what follows Theorem 3 states the general form of finding asymptotic expansion lower-bound for any $d \ge 3$. But in Corollary 2 we concentrate on small degrees to show how our results may lead to some improvements for the expansion lower bound of the uniform model of random regular graphs. For the following theorem, when $d$ is an even integer we define

$$ \mathcal{R}_d(k) \stackrel{\text{def}}{=} \left\{ (r, r, \tilde{r}, \tilde{r}) \mid \begin{array}{l} d/2 \neq r \le \lceil \frac{1}{2}(d+k) - 1 \rceil \quad \& \quad d/2 \neq \tilde{r} \le \lceil \frac{1}{2}(d+k) - 1 \rceil \quad \& \quad r + \tilde{r} \le d \\ \cup \left\{ (d/2, d/2-1, d/2, d/2), (d/2, d/2, d/2, d/2-1) \right\} \end{array} \right\} $$

and when $d$ is an odd integer we define

$$ \mathcal{R}_d(k) \stackrel{\text{def}}{=} \left\{ (r, r, \tilde{r}, \tilde{r}) \mid r \le \lceil \frac{1}{2}(d+k) - 1 \rceil \quad \& \quad \tilde{r} \le \lceil \frac{1}{2}(d+k) - 1 \rceil \quad \& \quad r + \tilde{r} \le d \right\}. $$

**Theorem 3.** For any $d \ge 3$, let $\xi_d > 0$ be an asymptotically almost sure expansion upper-bound for the ensemble $\mathcal{P}_{n,d}^{\pi}$. Then we have

$$ \min \left\{ \overline{\mathrm{RELB}}_{\pi}(\mathbf{r}) \mid \mathbf{r} \in \mathcal{R}_d(\lceil \xi_d \rceil) \right\} \le \overline{\mathrm{ELB}}(\mathcal{P}_{n,d}^{\pi}). $$

*Proof.* On the one hand, given a random graph $G_n \in \mathcal{P}_{n,d}^{\pi}$, by the hypothesis $h(G_n) < \xi_d$ a.a.s, using Proposition 5 (i) it follows that for any $S \in \mathcal{M}(G_n)$ we a.a.s. have

$$ \forall u \in S \forall v \in S^c \quad \mathrm{outd}_S(u) \le \lceil \frac{1}{2}(d + \lceil \xi_d \rceil) - 1 \rceil, \quad \mathrm{outd}_{S^c}(v) \le \lceil \frac{1}{2}(d + \lceil \xi_d \rceil) - 1 \rceil. $$

On the other hand, by Proposition 5 (ii), for any $S \in \mathcal{M}(G_n)$, if we have

$$ r_S \stackrel{\text{def}}{=} \max \{ \kappa(f_{1,S}), \kappa(f_{2,S}) \}, \quad \tilde{r}_S \stackrel{\text{def}}{=} \max \{ \kappa(\tilde{f}_{1,S}), \kappa(\tilde{f}_{2,S}) \}, $$

then $r_S + \tilde{r}_S \le d + 1$. However, in order to compute $\overline{\mathrm{RELB}}_p(\mathbf{r})$ it is enough to consider out-degree vectors $\mathbf{r} \stackrel{\text{def}}{=} (r_1, r_2, \tilde{r}_1, \tilde{r}_2)$ for which

$$ \underbrace{\max\{r_1 + r_2\}}_{\mathbf{r} \stackrel{\text{def}}{=}} + \underbrace{\max\{\tilde{r}_1 + \tilde{r}_2\}}_{\tilde{r} \stackrel{\text{def}}{=}} \le d, $$

since otherwise, if we have $r + \tilde{r} \le d + 1$, then Proposition 5 (ii) shows that $\max\{f_r^1 + f_r^2, \tilde{f}_r^1 + \tilde{f}_r^2\} \le d$ which is of order $o(n)$, and does not asymptotically contribute to the function $\bar{\Gamma}(r, \eta)$ (see the proof of Theorem 1).

Also, for even degrees $d$ one may use Proposition 5 (iii) and similar arguments to justify the claim. $\square$

**Corollary 2.** For $3 \le d \le 8$, Table 1 lists some improved asymptotic expansion lower-bounds for the ensemble of uniform random d-regular graphs.

*Proof.* For $3 \le d \le 8$, one may use [9, 10] to get an asymptotically almost sure bisection-width upper-bound $\xi_d/2$ for the ensemble $\mathcal{P}_{n,d}$. Therefore, since $\mathcal{P}_{n,d}^{\pi} \subset \mathcal{P}_{n,d}$, given a random d-regular graph $G_n \in \mathcal{P}_{n,d}^{\pi}$ we have a.a.s.

$$ h(G_n) \le 2 \mathrm{bw}(G_n) < \xi_d. $$

Hence, using Theorem 3 it follows that,
<table><caption>TABLE 1. Asymptotic expansion lower-bound of random d-regular graphs for $3 \le d \le 8$.</caption><thead><tr><th>Degree</th><th>Previously known expansion<br>lower-bound for P<sub>n,d</sub></th><th>Refined expansion lower-bound<br>for P<sub>n,d</sub><sup>*</sup></th><th>Improved expansion lower-bound<br>for P<sub>n,d</sub><sup>π</sup></th></tr></thead><tbody><tr><td>d = 3</td><td>0.20202 [16]</td><td>0.194 &lt; 3 RELB<sub>p</sub> (1, 1)</td><td>0.194 &lt; 3 RELB<sub>π</sub> (1, 1, 1, 1)</td></tr><tr><td>d = 4</td><td>0.44011 [15]</td><td>0.444 &lt; 4 RELB<sub>p</sub> (2, 2)</td><td><b>0.464</b> &lt; 4 RELB<sub>π</sub> (1, 2, 2, 2)</td></tr><tr><td>d = 5</td><td>0.73051 [15]</td><td>0.740 &lt; 5 RELB<sub>p</sub> (3, 2)</td><td>0.740 &lt; 5 RELB<sub>π</sub> (3, 3, 2, 2)</td></tr><tr><td>d = 6</td><td>1.04371 [15]</td><td>1.056 &lt; 6 RELB<sub>p</sub> (3, 3)</td><td><b>1.086</b> &lt; 6 RELB<sub>π</sub> (2, 3, 3, 3)</td></tr><tr><td>d = 7</td><td>1.37347 [15]</td><td>1.399 &lt; 7 RELB<sub>p</sub> (4, 3)</td><td>1.399 &lt; 7 RELB<sub>π</sub> (4, 4, 3, 3)</td></tr><tr><td>d = 8</td><td>1.71601 [15]</td><td>1.741 &lt; 8 RELB<sub>p</sub> (4, 4)</td><td><b>1.774</b> &lt; 8 RELB<sub>π</sub> (3, 4, 4, 4)</td></tr></tbody></table>

* These numbers also appear in [17].

i) For $d = 3$ we have $\lceil \xi_3 \rceil = 1$ and $\mathcal{R}_3(1) = \{(1, 1, 1, 1)\}$.

ii) For $4 \le d \le 7$ we have $\lceil \xi_d \rceil = 2$. Hence, for $d \in \{5, 7\}$

$$ \mathcal{R}_d(2) = \{(\lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor), (\lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor, \lfloor d/2 \rfloor)\}, $$

and for $d \in \{4, 6\}$ we have $\mathcal{R}_d(2) = \{(d/2, d/2-1, d/2, d/2), (d/2, d/2, d/2, d/2-1)\}$.

iii) For $d = 8$ we have $\lceil \xi_8 \rceil = 3$ and $\mathcal{R}_8(3) = \{(3, 3, 5, 5), (5, 5, 3, 3), (4, 3, 4, 4), (4, 4, 4, 3)\}$.

□

**Remark 4.** Note that, by Proposition 4, as shown in the second column of the Table 1, using one round $\pi$-lift construction does not improve the refined lower-bound for odd degrees. It may be verified that using more iterated steps of the $\pi$-lift construction do actually give rise to better expansion lower bounds<fnref n="10" />.

♦

## 4. CONCLUDING REMARKS

An $n$-lift of a graph $H = (V, E)$ is defined to be a new graph $G = (V', E')$ on the vertex set $V' \stackrel{\text{def}}{=} V \times \{1, 2, \dots, n\}$ for which there is a perfect matching between the two sets of vertices $\{u\} \times \{1, 2, \dots, n\}$ and $\{v\} \times \{1, 2, \dots, n\}$ (joining vertices with the same index) if and only if there is an edge $uv$ in $E$. The following very basic and simple example of 2-lifts of the triangle $K_3$, depicted in Figure 5, clearly illustrates the effect of such a construction on the connectivity of the new constructed lift itself, showing that even in this most simple case such a construction may change a connected graph into a disconnected one. However, the very simple commutative structure<fnref n="11" /> of the construction has already paved the way to very interesting explicit results.

<footnote n="10">¹⁰This will appear in a separate article elsewhere.</footnote>

<footnote n="11">¹¹Thinking of the 2-lift construction in terms of block-adjacency matrices clearly shows that the whole construction comes from a simple commutative algebra on $2 \times 2$ block matrices.</footnote>
The following conjecture about 2-lifts has already appeared in a celebrated contribution of Bilu and Linial [4] which is still an open question<fnref n="12" />, but has been a strong source of motivation for quite interesting contributions as a breakthrough by Marcus, Spielman and Srivastava [22], stating that the conjecture holds for 2-lifts of bipartite graphs (also see [6] for the explicit construction in a second stage).

**Conjecture 1.** Every $d$-regular graph has a 2-lift with all new eigenvalues at most $2\sqrt{d-1}$ in absolute value.

Note that considering the Alon-Boppana spectral bound [19], the conjecture essentially states that every $d$-regular graph has a highly connected 2-lift. A general study of such combinatorial extensions called cylindrical constructions, satisfying tensor-hom duality properties, is initiated in [7, 21] which covers a variety of sporadic amalgams already used in graph theory, among which, $n$-lifts as cylindrical constructions using identity cylinders and the zig-zag product are closely related to construction of expanders and Ramanujan graphs. In addition to a variety of motivations for such a study of tensor-like constructions, an approach to construct highly connected regular graphs using suitable cylindrical constructions is already justified by many interesting examples provided in [7, 21] as well as the results of [8] on the spectra of such constructions when one uses symmetric cylinders.

It is also quite interesting to note that, although [8] tries to extract and study commutative substructures existing in such constructions, there are enough evidence to show that the whole structure of such constructions are intrinsically noncommutative in general, justifying a probabilistic approach of study as one's first attempt toward the problem. To be more precise, an special case of such constructions, when cylinders are symmetric with no base intersections<fnref n="13" />, may be interpreted as block matrix constructions, generalizing the matrix tensor operation, and clearly revealing the noncommutative underlying structure of such amalgams (see [8] for more on this<fnref n="14" />).

On the other hand, there exists a huge literature related to strong motivations for such constructions and their general connectivity or spectral properties, varying from quantum field theory and localization of the eigenstructure of random Schrödinger operators to applications of random matrices in low-dimensional or high-energy physics as well as connections to some important and related conjectures and problems as quantum unique ergodicity, justifying the importance of a thorough combinatorial study of such structures, and in particular, constructions related to constructing highly connected graphs (e.g. see [1, 2]).

It is well-known that finding a sequence of expanders of increasing order is among the most challenging problems within the setup described so far (e.g. see [12, 19, 22]). Thinking of this problem as finding a set of graphs converging to a universal object as a regular (in the deterministic setup) or a Galton-Watson (in the randomized setup) tree with a guaranteed expansion lower bound, also motivates the following general problem.

**Problem 1.** Optimal restriction of random regular models

Provide appropriate restriction of the configuration model of random regular graphs in such a way that

1) *The whole class admits a relatively large expansion lower bound.*

<footnote n="12">¹²This is to the best of our knowledge at the time of writing this article.</footnote>

<footnote n="13">¹³See [7] for the details of definitions.</footnote>

<footnote n="14">¹⁴Results related to pursuing this line of thought within the context of random matrix theory are not the focus of this article and will appear elsewhere.</footnote>
<figure><img src="image_16.png" /><figcaption>FIGURE 5. The role of twists in 2-lifts and its consequences on connectivity.</figcaption></figure>

2) There are sequences of objects within the class admitting a universal limit.

Clearly, the problem is challenging since the two properties that are to be satisfied present a trade off scenario. On the other hand, this problem may be approached through introducing lift constructions that preserve connectivity measures such as the expansion parameter, although the whole generated class of graphs will most probably turn out to be far away from the standard configuration model as far as the contiguity is concerned.

The iterated $\pi$-lift model, concisely described below, may be considered as an attempt toward such an approach. Let us start with a ($2^r + 2$)-regular graph for some $r \ge 1$ and iteratively apply regular $\pi$-lift transformations, which clearly will stop at a 3-regular graph after $r$ steps. In other words, to obtain a random ($2^{r-t} + 2$)-regular graph using this model, one may start from a ($2^r + 2$)-regular graph and apply the regular $\pi$-lift transformations for $t$ iterations. It ought to be noted that if one is looking for highly connected graphs then the best scenario is to start from a large complete graph and then apply the iterated $\pi$-lift transformation. The main question in this setup is whether such a randomized iteration of $\pi$-lift constructions starting from an arbitrary large complete graph will produce a universe with a large portion of highly connected graphs.

Let us mention that by Proposition 1 a $\pi$-lift construction is more likely to preserve connectedness compared to its 2-lift counterpart (e.g. see Figure 5). On the other hand, the $\pi$-lift construction has a magical property of reducing the degree as well as preserving the connectedness in a general sense, making it possible to transform connectedness which is more accessible in higher degrees to lower degrees, while the 2-lift construction just preserves the degree of the original graph.

Also, note that based on this background, it is intuitively understood that finding optimal expansion lower bounds for random regular graph ensembles is in general harder for small degrees while finding an explicit sequence of Ramanujan graphs is usually harder for large and complex (nonprime) degrees. This, in a way, justifies the better performance of our $\pi$-lift construction for larger degrees.

We also have enough evidence to be convinced that even a substructure of the iterated $\pi$-lift model is strong enough to improve the lower bound even for cubic graphs. These fundamental properties have been our main motivations for the study presented in this article and some other results to appear elsewhere.
ACKNOWLEDGEMENT

Mohammad-Hossein Shojaedin has been partially supported by Sharif University of Technology research grant #G961206 as a Ph.D. student.

APPENDIX A. PROOFS

A.1. **Proof of Theorem 1.** Let us first fix some notations. Given an $r \in \mathbb{r}_{\pi}^{\infty}$, a 7-tuple $\psi = (s, c, \alpha, \ell_1, \tilde{\ell}_1, \ell_2, \tilde{\ell}_2)$ of non-negative real entries, is said to be r-compatible if this data satisfies the condition stated in Equation 1, and

$$ \kappa(\ell_1) \le r_1, \quad \kappa(\tilde{\ell}_1) \le \tilde{r}_1, \quad \kappa(\ell_2) \le r_2 \quad \text{and} \quad \kappa(\tilde{\ell}_2) \le \tilde{r}_2. $$

Also, a 7-tuple

$$ \Psi \stackrel{\text{def}}{=} (s, c, a, f_1, \tilde{f}_1, f_2, \tilde{f}_2) $$

is said to be r-compatible when the corresponded normalized 7-tuple $\psi$ is r-compatible.

By considering the parameter space $\mathcal{D}'(r, \eta)$ as

$$ \mathcal{D}'(r, \eta) \stackrel{\text{def}}{=} \{ \psi \in [0, 1/2] \times [0, d_\delta\eta] \times [0, c] \times [0, 1]^{4(d+1)} \mid \psi \text{ is r-compatible} \}, $$

we want to compute the following function

$$ \overline{\mathrm{L}\Gamma}(r, \eta) \stackrel{\text{def}}{=} \max_{\psi \in \mathcal{D}'(r, \eta)} \mathrm{L}\Gamma'_{r} \psi, $$

in which

$$ \begin{aligned} \mathrm{L}\Gamma'_{r} \psi \stackrel{\text{def}}{=} & \frac{1}{2} (I(s - \alpha) + I(1 - s - \alpha) + 2I(\alpha)) \\ & + \frac{d-1}{2} \left( I(s - \frac{c-\alpha}{d-1}) + I(1-s - \frac{c-\alpha}{d-1}) + 2I(\frac{c-\alpha}{d-1}) \right) \\ & - (s - \alpha) \left( \sum_k I(\ell_k^1) - \ell_k^1 \log(\mu_k^0) \right) - \alpha \left( \sum_k I(\ell_k^2) - \ell_k^2 \log(\mu_k^1) \right) \\ & - (1-s - \alpha) \left( \sum_k I(\tilde{\ell}_k^1) - \tilde{\ell}_k^1 \log(\mu_k^0) \right) - \alpha \left( \sum_k I(\tilde{\ell}_k^2) - \tilde{\ell}_k^2 \log(\mu_k^1) \right). \end{aligned} \quad (5) $$

To prove the statement, first of all we show that for a fixed $0 < \eta < 1$,

$$ \overline{\mathrm{L}\Gamma}(r, \eta) = \max_{\varphi \in \mathcal{D}(r, \eta)} \mathrm{L}\Gamma_{r} \varphi. $$

This is because, in order to find optimal out-degree vectors $\ell_1, \tilde{\ell}_1, \ell_2, \tilde{\ell}_2$ for $\overline{\mathrm{L}\Gamma}(r, \eta)$, by using the convexity of relative entropy and since the Conditions 1 are linear, one may use Lagrange multipliers method. Hence, applying this method, for $p \in \{1, 2\}$ one finds

$$ \ell_k^{*p} = \begin{cases} \frac{\mu_k e^{k\tau}}{\Delta(d-1, r_p, e^\tau)} & k \le r_p \\ 0 & \text{otherwise} \end{cases} $$
and

$$
\tilde{\mathcal{F}}_{k}^{*p} = \begin{cases} \frac{\mu_k e^{k\tilde{\tau}}}{\Delta(d-1, \tilde{\mathcal{R}}_p, e^{\tilde{\tau}})} & k \le \tilde{\mathcal{R}}_p \\ 0 & \text{otherwise,} \end{cases}
$$

which are optimal solutions of the corresponded optimization problem and $\tau$ and $\tilde{\tau}$ are La-
grange's variables. Now, if one defines $y \stackrel{\text{def}}{=} e^{\tau} \in \mathbb{R}^{+}$ and $\tilde{y} \stackrel{\text{def}}{=} e^{\tilde{\tau}} \in \mathbb{R}^{+}$, by rephrasing $\mathrm{L}\Gamma'_{r}$ and
Equations 1 one derives $\mathrm{L}\Gamma_{r}$ along with Conditions 2.

Therefore, to prove the theorem it is enough to show that the following implication holds,

$$
\overline{\mathrm{L}\Gamma}(\mathbf{r}, \eta) < 0 \Rightarrow \lim_{n \to \infty} \mathbb{P} \left( \frac{h(G_n)}{d} \le \eta \right) = 0.
$$

By definition of $\mathbf{r}^\infty$, for any $\epsilon > 0$, there exists $n_\epsilon \in \mathbb{N}$, such that for all $n \ge n_\epsilon$ we have

$$
\mathbb{P} (\exists S \in \mathcal{M}(G_n), \mathbf{r}_S \le \mathbf{r}) > 1 - \epsilon.
$$

Therefore,

$$
\begin{align*}
\mathbb{P} (h(G_n) \le d\eta) &= \mathbb{P} (h(G_n) \le d\eta, (\exists S \in \mathcal{M}(G_n) \ r_S \le r) ) + \mathbb{P} (h(G_n) \le d\eta, (\forall S \in \mathcal{M}(G_n) \ r_S \ge r) ) \\
&\le \mathbb{P} (h(G_n) \le d\eta, (\exists S \in \mathcal{M}(G_n) \ r_S \le r) ) + \epsilon \\
&= \frac{1}{N((d-1)n)} \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid \exists S \in \mathcal{M}(G_n) \ r_S \le r, h_{G_n}(S) \le d\eta \right\} \right| + \epsilon \\
&\le \frac{1}{N((d-1)n)} \sum_{S \in C_{1/2}} \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid r_S \le r, h_{G_n}(S) \le d\eta \right\} \right| + \epsilon \\
&\le \frac{1}{N((d-1)n)} \sum_{S \in C_{1/2}} \sum_{c=0}^{\lfloor d\eta s \rfloor} \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid r_S \le r, h_{G_n}(S) = c/s \right\} \right| + \epsilon.
\end{align*}
$$

Now, to evaluate the last expression, we first reformulate the sum in terms of 7-tuples $\Psi = (s, c, a, f_1, \tilde{f}_1, f_2, \tilde{f}_2)$. For this, define

$$
S \stackrel{\text{def}}{=} [0, n/2] \times [0, \lfloor ds\eta \rfloor] \times [0, c],
$$

and note that for a cut $S_{(s,c,a)} \in C_{1/2}$ with parameters $(s,c,a) \in S$, we have

$$
\sum_{S \in C_{1/2}} \sum_{c=0}^{\lfloor d\eta s \rfloor} \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid \mathbf{r}_S \le \mathbf{r}, h_{G_n}(S) = c/s \right\} \right| \\
= \sum_{(s,c,a) \in S} A_1(s,a) \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid \mathbf{r}_{S_{(s,c,a)}} \le \mathbf{r}, h_{G_n}(S_{(s,c,a)}) = c/s \right\} \right|
$$

in which

$$
A_1(s, a) \stackrel{\text{def}}{=} \binom{n/2}{a} 2^a \binom{n/2 - a}{\frac{s-a}{2}}
$$
counts the number of cuts $S \in C_{1/2}$ with $|S| = s$ which have a cut-edges from the perfect matching. Since, eventually, we want to count the graphs which are compatible with a 7-tuples $\Psi = (s, c, a, f_1, \tilde{f}_1, f_2, \tilde{f}_2)$, let us define

$$ \nu(r, \eta) \stackrel{\text{def}}{=} \{ \Psi \in [0, n/2] \times [0, \lfloor ds\eta \rfloor] \times [0, c] \times (\mathbb{N} \cup \{0\})^{4(d+1)} \mid \Psi \text{ is r-compatible} \}, $$

that gives rise to the equality

$$ \begin{aligned} & \sum_{s=0}^{n/2} \sum_{c=0}^{\lfloor d\eta s \rfloor} \sum_{a=0}^{c} A_1(s, a) \left| \left\{ G_n \in \mathcal{P}_{n,d}^{\pi} \mid \mathcal{F}_S \preceq \mathcal{F}, h_{G_n}(S) = c/s \right\} \right| / N((d-1)n) \\ & = \sum_{\Psi \in \nu(r, \eta)} \underbrace{A_1(s, a) \cdot A_2(f_1, \tilde{f}_1, f_2, \tilde{f}_2) \cdot A_3(s, c, a) / N((d-1)n)}_{\stackrel{\text{def}}{=} \Gamma_r \Psi}, \end{aligned} $$

in which

$$ \begin{aligned} A_2(f_1, \tilde{f}_1, f_2, \tilde{f}_2) &\stackrel{\text{def}}{=} \binom{s-a}{f_0^1, \dots, f_{r_1}^1} \prod_{k=0}^{r_1} \binom{d-1}{k}^{f_k^1} \binom{a}{f_0^2, \dots, f_{r_2}^2} \prod_{k=0}^{r_2} \binom{d-1}{k-1}^{f_k^2} \\ &\qquad \binom{n-s-a}{\tilde{f}_0^1, \dots, \tilde{f}_{\tilde{r}_1}^1} \prod_{k=0}^{\tilde{r}_1} \binom{d-1}{k}^{\tilde{f}_k^1} \binom{a}{\tilde{f}_0^2, \dots, \tilde{f}_{\tilde{r}_2}^2} \prod_{k=0}^{\tilde{r}_2} \binom{d-1}{k-1}^{\tilde{f}_k^2} (c-a)! \end{aligned} $$

counts the number of possible ways to match the half-edges from the inner part to the half-edges in the outer part of the cut, in terms of $f_1, \tilde{f}_1, f_2, \tilde{f}_2$, and

$$ A_3(s, c, a) \stackrel{\text{def}}{=} N((d-1)s - c + a) N((d-1)(n-s) - c + a) / N((d-1)n), $$

counts the number of possible ways that the remained half-edges may be matched together within the cut and outside the cut, independently.

All together, it follows that

$$ \lim_{n \to \infty} \mathbb{P}(h(G_n) \le d\eta) \le \lim_{n \to \infty} \sum_{\Psi \in \nu(r, \eta)} \Gamma_r \Psi \le \lim_{n \to \infty} O(n^{4(d+1)+3}) \max_{\Psi \in \nu(r, \eta)} \Gamma_r \Psi. $$

For the rest of the proof we show that

$$ \bar{\Gamma}(r, \eta) \stackrel{\text{def}}{=} \max_{\Psi \in \nu(r, \eta)} \Gamma_r \Psi \le e^{-\gamma n}, $$

in which the large deviation parameter $\gamma$ is actually $-\overline{\Gamma}(r, \eta) > 0$. For this, since for any $n \ge 1$ we know that

$$ \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{1/(12n+1)} < n! < \sqrt{2\pi n} \left(\frac{n}{e}\right)^n e^{1/12n} $$

therefore, we have

$$ Y(0) < \binom{n}{a_1, \dots, a_p} < Y(1), $$
in which for $i \in \{0,1\}$

$$ Y(i) \stackrel{\text{def}}{=} \frac{\sqrt{2\pi n}}{\prod_{k=1}^{p} \sqrt{2\pi a_k}} \prod_{k=1}^{p} \left(\frac{n}{a_k}\right)^{a_k} \exp \left\{ \frac{1}{12n + ((i+1) \bmod 2)} - \sum_{k=1}^{p} \frac{1}{12n+i} \right\}. $$

Since for $i \in \{0,1\}$ we have

$$ \lim_{n \to \infty} \frac{1}{n} \log Y(i) = \lim_{n \to \infty} \sum_{k=1}^{p} \frac{a_p}{n} \log \left( \frac{n}{a_p} \right), $$

and we know that $\lim_{x \to 0} x \log(1/x) = 0$, hence we will consider all parameters in 7-tuples $\Psi$ as fraction of type $\Omega(n)$. Now, to complete the proof, note that $\Psi \in \mathcal{V}(r, \eta) \Rightarrow \psi \in \mathcal{D}(r, \eta)$, and consequently, an application of Stirling's approximation implies that

$$ \frac{1}{n} \log \bar{\Gamma}(r, \eta) = \max_{\Psi \in \mathcal{V}(r, \eta)} \mathrm{L}\Gamma'_{r}(1/n \Psi) \le \underbrace{\mathrm{L}\Gamma(r, \eta)}_{\stackrel{\text{def}}{=} -\gamma} < 0. $$

## A.2. Proof of Proposition 2.

*Proof.* We prove the proposition in four steps as follows,

(1) For any $d \ge 3$ and $z \in \mathbb{R}$, if $r \le d$ then

$$ \sum_{k=0}^{r} \binom{d}{k} (k-z) \left(\frac{z}{d-z}\right)^k = -\binom{d-1}{r} \left(\frac{z}{d-z}\right)^r z. $$

(2) For any $d \ge 3$ and $z \le d\bar{\eta}_d$, if $r \ge \lfloor d/2 \rfloor$, then
$$ \frac{\bar{\Delta}\left(d, r, \bar{\delta}(d)z/(d-\bar{\delta}(d)z)\right)}{\Delta\left(d, r, \bar{\delta}(d)z/(d-\bar{\delta}(d)z)\right)} > z. $$

(3) Each one of the equations $Q(r_1, r_2, y) = 0$ and $\tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}) = 0$ has at most one root over positive real numbers.

(4) We have $Q(r_1, r_2, y_1) < 0$, $\tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_1) < 0$ and $Q(r_1, r_2, y_{\delta(d)}) > 0$, $\tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_{\delta(d)}) > 0$.

### Proof of (1):
The proof is by induction on $r$. The identity is obviously true for $r = 0$. Then assuming it is also true for $r < d$, we have

$$
\begin{align*}
& \sum_{k=0}^{r+1} \binom{d}{k} (k-z) \left(\frac{z}{d-z}\right)^k \\
&= \sum_{k=0}^{r} \binom{d}{k} (k-z) \left(\frac{z}{d-z}\right)^k + \binom{d}{r+1} (r+1-z) \left(\frac{z}{d-z}\right)^{r+1} \\
&= - \binom{d-1}{r} \left(\frac{z}{d-z}\right)^r z + \binom{d}{r+1} (r+1-z) \left(\frac{z}{d-z}\right)^{r+1} \\
&= \left(\frac{z}{d-z}\right)^{r+1} z \left[ - \binom{d-1}{r} \left(\frac{d}{z}-1\right) + \binom{d}{r+1} \left(\frac{r+1}{z}-1\right) \right] \\
&= \left(\frac{z}{d-z}\right)^{r+1} z \left[ \binom{d-1}{r} - \binom{d}{r+1} - \binom{d-1}{r} \frac{d}{z} + \binom{d}{r+1} \frac{r+1}{z} \right] \\
&= - \binom{d-1}{r+1} \left(\frac{z}{d-z}\right)^{r+1} z. \quad \text{(using Pascal's identity)}
\end{align*}
$$

**Proof of (2):**

For brevity, let us write $\bar{\delta}$ for $\bar{\delta}(d)$. Define $x \stackrel{\text{def}}{=} \bar{\delta}(d) z/(d-\bar{\delta}(d) z)$ and $\bar{x} = \bar{x}(d) \stackrel{\text{def}}{=} \bar{\delta}(d) \frac{\bar{\eta}_d}{1-\bar{\delta}(d) \bar{\eta}_d}$. Now, using Part (1) we have

$$
\begin{align*}
\frac{\bar{\Delta}(d,r,x)}{\Delta(d,r,x)} - z &= \frac{\bar{\Delta}(d,r,x)}{\Delta(d,r,x)} - \bar{\delta}z + (\bar{\delta}-1)z \\
&= -\bar{\delta}z \binom{d-1}{r} \underbrace{\frac{x^r}{\Delta(d,r,x)}}_{\theta(x)} + (\bar{\delta}-1)z \\
&\geq z(\bar{\delta}-1) \left( 1 - \frac{\bar{\delta}}{\bar{\delta}-1} \binom{d-1}{\lfloor d/2 \rfloor} \frac{\bar{x}^{\lfloor d/2 \rfloor}}{\Delta(d, \lfloor d/2 \rfloor, \bar{x})} \right),
\end{align*}
$$

noting that $\theta(x)$ is increasing and $r \ge \lfloor d/2 \rfloor$. It is straight forward to verify that for degrees $3 \le d \le 30$ the expression inside the big parentheses is positive. However, for larger $d$'s, using an approximation from [11], for any $d \ge 3$ and $1/2 \le x \le 1$ we have

$$
\frac{(1+x)^d}{1+x^{\alpha_d}} \le \Delta(d, \lfloor \frac{d}{2} \rfloor, x)
$$

with $\alpha_d \stackrel{\text{def}}{=} \frac{d}{4\lfloor d/2 \rfloor} \binom{d-1}{\lfloor d/2 \rfloor}$. Therefore, since $\frac{4^k}{\sqrt{\pi(k+\frac{1}{2})}} \le \binom{2k}{k} \le \frac{4^k}{\sqrt{\pi k}}$, for any $k \ge 1$, we have

$$
\frac{1}{z(\bar{\delta}-1)} \left( \frac{\bar{\Delta}(d,r,x)}{\Delta(d,r,x)} - z \right) \ge \begin{cases} 1 - \frac{\bar{\delta}}{\bar{\delta}-1} \frac{2^{d-1}}{\sqrt{\pi \frac{d-1}{2}}} \frac{\bar{x}^{\frac{d-1}{2}}}{(1+\bar{x})^d} (1+\bar{x}^{\sqrt{\frac{2d}{\pi}}}) & \text{if } d \text{ is odd,} \\ 1 - \frac{\bar{\delta}}{\bar{\delta}-1} \frac{2^{d-1}}{\sqrt{\pi \frac{d}{2}}} \frac{\bar{x}^{\frac{d}{2}}}{(1+\bar{x})^d} (1+\bar{x}^{\frac{d}{2\sqrt{2\pi(d+1)}}}) & \text{if } d \text{ is even.} \end{cases}
$$
<figure><img src="image_17.png" /><figcaption>FIGURE 6. Positiveness of the right-hand side of Inequality 6 for odd degrees $30 \le d \le 1000$.</figcaption></figure>

Comparing these two expressions, for odd degrees we get

$$ \frac{(\bar{x}(2k+1))^k}{(1+\bar{x}(2k+1))^{2k+1}} \left(1+\bar{x}^{\sqrt{\frac{2(2k+1)}{\pi}}}\right) \le \frac{(\bar{x}(2k+1))^k}{(1+\bar{x}(2k))^2} \left(1+\bar{x}^{\frac{2k}{\sqrt{2\pi(2k+1)}}}\right), $$

and consequently,

$$ 1 - \frac{\bar{\delta}(2k)}{\bar{\delta}(2k) - 1} \frac{2^{2k-1}}{\sqrt{\pi k}} \frac{(\bar{x}(2k))^k}{(1 + \bar{x}(2k))^2k} \left(1 + (\bar{x}(2k))^{\frac{2k}{\sqrt{2\pi(2k+1)}}}\right) \ge 1 - \frac{\bar{\delta}(2k+1)}{\bar{\delta}(2k+1) - 1} \frac{2^{2k}}{\sqrt{\pi k}} \frac{\bar{x}(2k+1)^k}{(1 + \bar{x}(2k))^2k+1} \left(1 + (\bar{x}(2k+1))^{\frac{2k}{\sqrt{2\pi(2k+1)}}}\right), \quad (6) $$

since $\frac{2}{1+\bar{x}(2k)} \ge 1$. The right-hand side of the above inequality is a positive function as shown in Figure 6.

**Proof of (3):**

Let $y = e^{\lambda}$ for $\lambda \in \mathbb{R}$. First, we want to show that the function $g(\lambda) = \bar{\Delta}(d,r,e^{\lambda})/\Delta(d,r,e^{\lambda})$ is strictly increasing with respect to $\lambda$. Note that

$$ g(\lambda) = \frac{d}{d\lambda} \log \Delta(d,r,e^{\lambda}). $$

Using Hölder's inequality, it follows that the function $\log \Delta(d,r,e^{\lambda})$ is convex, i.e.

$$ \begin{aligned} \log \Delta(d,r, e^{\varepsilon\lambda_1 + (1-\varepsilon)\lambda_2}) &= \log \sum_{k=0}^{r} \left( \binom{d}{k} e^{k\lambda_1} \right)^{\varepsilon} \left( \binom{d}{k} e^{k\lambda_2} \right)^{1-\varepsilon} \\ &\le \log \left[ \left( \sum_{k=0}^{r} \left( \binom{d}{k} e^{k\lambda_1} \right)^{\varepsilon \cdot \frac{1}{\varepsilon}} \right)^{\varepsilon} \left( \sum_{k=0}^{r} \left( \binom{d}{k} e^{k\lambda_2} \right)^{\frac{1-\varepsilon}{1-\varepsilon}} \right)^{1-\varepsilon} \right] \\ &= \varepsilon \log \Delta(d,r, e^{\lambda_1}) + (1-\varepsilon) \log \Delta(d,r, e^{\lambda_2}). \end{aligned} $$
Therefore, since $\Delta(d,r,e^\lambda)$ is strictly increasing, one may deduce that $g(\lambda)$ is also strictly increasing. Now, rewriting $Q(r_1,r_2,y) = 0$ as

$$ (s - \alpha) \left( \frac{\bar{\Delta}(d-1, r_1, y)}{\Delta(d-1, r_1, y)} - \frac{c - \alpha}{s} \right) = -\alpha \left( \frac{\bar{\Delta}(d-1, r_2 - 1, y)}{\Delta(d-1, r_2 - 1, y)} - \frac{c - \alpha}{s} \right) $$

one may observe that the left hand side in a strictly increasing function while the right hand side is a strictly decreasing function, implying that this equation has at most one root. A similar argument proves the same statement for the equation $\tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y})$.

**Proof of (4):**

$$ Q(r_1, r_2, y_1) = (s - \alpha) \left( \frac{\bar{\Delta}(d-1, r_1, y_1)}{\Delta(d-1, r_1, y_1)} - \frac{c - \alpha}{s} \right) + \alpha \left( \frac{\bar{\Delta}(d-1, r_2 - 1, y_1)}{\Delta(d-1, r_2 - 1, y_1)} - \frac{c - \alpha}{s} \right) < 0, $$

in which the last inequality follows from Part (1) by considering $z = (c-\alpha)/s$. Similarly, one may show that

$$ \tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_1) < 0. $$

In the case of $y_{\delta(d)}$ and $\tilde{y}_{\delta(d)}$, the positiveness of $Q$ and $\tilde{Q}$ may be shown again by a similar argument and using Part (2). $\square$

### A.3. Proof of Proposition 3.

**Proof of I(i):**

The claim follows if for any fixed $0 \le s \le 1/2$ and $0 \le c \le d_3 \bar{\eta}_d$ we show that

$$ \frac{\partial^2}{\partial c^2} \mathrm{L}\Gamma_r(s, c, s, y_{\delta^*}, \tilde{y}_{\delta^*}) < 0. $$

Let us define,

$$ f_{-}(s, c, \alpha, d) \stackrel{\text{def}}{=} -1/2 \left( \frac{1}{s - \alpha} + \frac{1}{\alpha} \right) \pm 1/2 \left( \frac{1}{(d-1)s - c + \alpha} + \frac{1}{c - \alpha} \right), $$
then

$$
\begin{align*}
& \frac{\partial^2}{\partial \alpha^2} L(s, c, \alpha, y_{\delta^*}, d, r_1, r_2 - 1) \\
&= f_+(s, c, \alpha, d) - \frac{\partial}{\partial \alpha} \log \Delta(d-1, r_1, y_{\delta^*}) + \frac{\partial}{\partial \alpha} \log \Delta(d-1, r_2 - 1, y_{\delta^*}) + \frac{\partial}{\partial \alpha} \log y_{\delta^*} \\
&= f_+(s, c, \alpha, d) + \frac{\partial}{\partial \alpha} \log y_{\delta^*} \left( \frac{c-\alpha}{\alpha} - \frac{s}{\alpha} \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})} \right) + \frac{\partial}{\partial \alpha} \log y_{\delta^*} \quad \text{(using Conditions 2)} \\
&= f_+(s, c, \alpha, d) + \frac{s}{\alpha} \frac{\partial}{\partial \alpha} \log y_{\delta^*} \left( \frac{c-\alpha}{s} - \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})} \right) - \frac{1}{c-\alpha} - \frac{\delta^*}{(d-1)s - \delta^*(c-\alpha)} \\
&\le f_-(s, c, \alpha, d) + \frac{s}{\alpha} \frac{\partial}{\partial \alpha} \log y_{\delta^*} \left( \frac{c-\alpha}{s} - \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})} \right) \quad \text{(since } \delta^* \ge 1 \text{)} \\
&= f_-(s, c, \alpha, d) + \frac{s}{\alpha} \left( \frac{-1}{c-\alpha} - \frac{\delta^*}{(d-1)s - \delta^*(c-\alpha)} \right) \left( \frac{c-\alpha}{s} - \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})} \right).
\end{align*}
$$

Since $f_-(s, c, \alpha, d)$ is a negative function, we have to focus on the second term. It is not hard to
see that for fixed parameters $(s, c, \alpha)$,

$$
\frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})}
$$

is an increasing function of $1 \le \delta \le \bar{\delta}(d)$. Therefore, if we consider $y_1$ instead of $y_{\delta^*}$ and using
Step 1 of Proposition 2 we have

$$
\left( \frac{c - \alpha}{s} - \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\Delta(d-1, r_1, y_{\delta^*})} \right) \geq \frac{c - \alpha}{s} \frac{-(d-2)}{\Delta(d-1, r, y_1)}.
$$

Consequently,

$$
\begin{align*}
& \frac{\partial^2}{\partial \alpha^2} L(s, c, \alpha, y_{\delta^*}, d, r_1, r_2 - 1) \le \\
& f_-(s, c, \alpha, d) + \frac{1}{\alpha} (1 + y_{\delta^*}) \frac{\binom{d-2}{r} y_1^r}{\Delta(d-1, r, y_1)} = \\
& \quad -\frac{1}{2} \frac{1}{s-\alpha} - \frac{1}{2} \left( \frac{1}{(d-1)s-c+\alpha} + \frac{1}{c-\alpha} \right) + \frac{1}{\alpha} \left( (1+y_{\delta^*}) \frac{\binom{d-2}{r} y_1^r}{\Delta(d-1, r, y_1)} - \frac{1}{2} \right).
\end{align*}
$$

Hence, it suffices to show that

$$
(1 + y_{\delta^*}) \frac{\binom{d-2}{r} y_1^r}{\Delta(d-1, r, y_1)} - \frac{1}{2} < 0.
$$

Since $y_{\delta^*} \le y_{\delta(d)}$, using a similar argument as in Step 2 of Proposition 2, if we define

$$
\bar{x}(d) \stackrel{\text{def}}{=} \frac{d}{d-1} \frac{\bar{\eta}_d}{(1-d/(d-1)\bar{\eta}_d)},
$$
then

$$ (1 + y_{\delta^*}) \frac{\binom{d-2}{r} y_1^r}{\Delta(d-1, r, y_1)} \le \left( \frac{1}{1 - \bar{\delta}(d) \frac{d}{d-1} \bar{\eta}_d} \right) \binom{d-2}{\lfloor \frac{d}{2} \rfloor} \frac{\bar{x}^{\lfloor \frac{d}{2} \rfloor}}{\Delta(d-1, \lfloor \frac{d}{2} \rfloor, \bar{x})} \quad (7) $$

$$ \le \left( \frac{1}{1 - \bar{\delta}(d) \frac{d}{d-1} \bar{\eta}_d} \right) \frac{2^{2k-1}}{\sqrt{k\pi}} \frac{(\bar{x}(d))^k}{(1 + \bar{x}(2k))^{d-1}} \left( 1 + (\bar{x}(d))^{\frac{2k-2}{\sqrt{(2k+1)\pi/2}}} \right), \quad (8) $$

in which for the last inequality, we have $d = 2k + 1$.

It is straightforward to check for $d = 3$ that the right-hand side of Inequality 7 is less than $1/2$ and for larger odd degrees we use the right-hand side of Inequality 8 as shown in Figure 7(A).

Using a similar argument, one may show that

$$ \frac{\partial^2}{\partial \alpha^2} L(1 - s, c, \alpha, \tilde{y}_{\delta^*}, d, \tilde{r}_1, \tilde{r}_2 - 1) < 0. $$

Furthermore, since $Q(r_1, r_2, y_{\delta^*}) = \tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_{\delta^*}) = 0$, then

$$ \frac{\partial}{\partial \alpha} \mathrm{L} \Gamma_r(s, c, \alpha, y_{\delta^*}, \tilde{y}_{\delta^*}) = 0, $$

implying Equation 4.

### Proof of I(ii):

By the previous part we know that Equation 4 has a unique solution and therefore the function has a global maximum. Now, we show that for any fixed $0 \le s \le 1/2$ and $0 \le c \le ds\bar{\eta}_d$, when $r_2 \le r_1$ and $\tilde{r}_2 \le \tilde{r}_1$, we have

$$ \frac{\partial}{\partial \alpha} \mathrm{L} \Gamma_r(s, c, c/d, y_{\delta^*}, \tilde{y}_{\delta^*}) \le 0, $$

implying that $\alpha^* \le c/d$.

First, consider the following identity,

$$ \begin{align*} & \frac{1}{d} \sum_{k=1}^{r_1} \left( \binom{d-1}{k} + \binom{d-1}{k-1} \right) k y^k - \sum_{k=r_2+1}^{r_1} \binom{d-1}{k-1} y^k \\ &= \frac{1}{d} \sum_{k=1}^{r_1} \binom{d-1}{k} k y^k + \frac{1}{d} \sum_{k=1}^{r_2} \binom{d-1}{k-1} k y^k - \sum_{k=r_2+1}^{r_1} \left(1 - \frac{k}{d}\right) \binom{d-1}{k-1} y^k \\ &= \frac{1}{d} \left( \bar{\Delta}(d-1, r_1, y) + y \bar{\Delta}(d-1, r_2, y) \right) - \underbrace{\sum_{k=r_2+1}^{r_1} \left(1 - \frac{k}{d}\right) \binom{d-1}{k-1} y^k}_{\theta \stackrel{\text{def}}{=} 0} \end{align*} $$

and rewrite $Q(r_1, r_2, y_{\delta^*}) = 0$ as,

$$ \frac{\Delta(d-1, r_1, y_{\delta^*})}{y_{\delta^*} \Delta(d-1, r_2-1, y_{\delta^*})} = (s/\alpha - 1) \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\bar{\Delta}(d-1, r_1, y_{\delta^*}) - \theta} - (c - d\alpha) \frac{\Delta(d-1, r_1, y_{\delta^*})}{\bar{\Delta}(d-1, r_1, y_{\delta^*}) - \theta}. \quad (9) $$
Note that $\theta \ge 0$ with $\theta = 0$ when we have $r_1 = r_2$ and $\tilde{r}_1 = \tilde{r}_2$. It may be verified that the second term on the right-hand side of Equality 9 is zero when $\alpha = c/d$. Therefore, using Equality 9 we have

$$ \frac{\partial}{\partial \alpha} L(s, c, \alpha, y, d-1, r_1, r_2-1) = \frac{1}{2} \log \left( \frac{s-\alpha}{\alpha} \frac{(d-1)s-c+\alpha}{c-\alpha} \right) - \log \frac{\Delta(d-1, r_1, y)}{y\Delta(d-1, r_2-1, y)}, $$

implying that

$$ \frac{\partial}{\partial \alpha} L(s, c, c/d, y_{\delta^*}, d-1, r_1, r_2-1) = \log \left( \frac{s}{c/d} - 1 \right) - \log \left( \frac{s}{c/d} - 1 \right) - \log \left( \frac{\bar{\Delta}(d-1, r_1, y_{\delta^*})}{\bar{\Delta}(d-1, r_1, y_{\delta^*}) - \theta} \right) \le 0. $$

Similarly, one may show that when $\tilde{r}_2 \le \tilde{r}_1$ we have,

$$ \frac{\partial}{\partial \alpha} L(s, c, c/d, \tilde{y}_{\delta^*}, d-1, \tilde{r}_1, \tilde{r}_2-1) \le 0, $$

and consequently,

$$ \frac{\partial}{\partial \alpha} L \Gamma_r(s, c, c/d, y_{\delta^*}, \tilde{y}_{\delta^*}) \le 0. $$

Using a similar argument one may prove that $\alpha^* > c/d$ when $r_1 < r_2$ and $\tilde{r}_1 < \tilde{r}_2$.

**Proof of II:** For any fixed $0 \le s \le 1/2$, we have

<figure><img src="image_18.png" /><figcaption>FIGURE 7. Figure (A) shows Inequality 8 is less than $1/2$ for odd degrees $5 \le d \le 1000$. Figure (B) shows Inequality 10 for $3 \le d \le 1000$.</figcaption></figure>

$$ \frac{\partial}{\partial c} L \Gamma_r(s, c, \alpha^*, y_{\delta^*}, \tilde{y}_{\delta^*}) = \frac{\partial}{\partial c} L(s, c, \alpha^*, y^*, d, r_1, r_2-1) + \frac{\partial}{\partial c} L(1-s, c, \alpha^*, \tilde{y}^*, d, \tilde{r}_1, \tilde{r}_2-1). $$

Since $Q(r_1, r_2, y_{\delta^*}) = \tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}_{\delta^*}) = 0$ it follows that,

$$ \frac{\partial}{\partial c} L(s, c, \alpha^*, y_{\delta^*}, d, r_1, r_2-1) = \frac{1}{2} \log \left( \frac{(c-\alpha^*)/s}{d-1-(c-\alpha^*)/s} \right) - \log y_{\delta^*} + \\ \frac{\partial a^*}{\partial c} \left( \log y_{\delta^*} + \log \Delta(d-1, r_2-1, y_{\delta^*}) + \log \Delta(d-1, r_1, y_{\delta^*}) \right), $$
and using Equation 4 we have

$$ \frac{\partial}{\partial c} \mathrm{L}_{\mathrm{r}}(s, c, \alpha^*, y_{\delta^*}, \tilde{y}_{\delta^*}) = \frac{1}{2} \log y_1 - \log y_{\delta^*} + \frac{1}{2} \log \tilde{y}_1 - \log \tilde{y}_{\delta^*}. $$

If we define

$$ f(z, \delta) \stackrel{\text{def}}{=} \frac{1}{2} \log \left( \frac{z}{1-z} \right) - \log \left( \frac{\delta z}{1 - \delta z} \right), $$

then we have

$$ \frac{1}{2} \log y_1 - \log y_{\delta^*} = f\left(\frac{c - \alpha^*}{(d-1)s}, \delta^*\right). $$

Note that $f(z, \delta)$ is a decreasing function with respect to $z$ and $\delta$. Hence,

$$ f\left(\frac{c - \alpha^*}{(d-1)s}, \delta^*\right) \geq f\left(\frac{d \bar{\eta}_d}{d-1}, \bar{\delta}(d)\right) \geq 0, \quad (10) $$

since $\lim_{d \to \infty} \bar{\delta}(d) = 1$ and as shown in Figure 7 (B), the function $f((d-1)/d \bar{\eta}_d, \bar{\delta}(d))$ is decreasing and converges to zero.

Moreover, since for $0 \le s \le 1/2$ we have $(c-a^*)/(d-1)s \ge (c-a^*)/(d-1)(1-s)$ it follows similarly that

$$ f\left(\frac{c - \alpha^*}{(d-1)(1-s)}, \delta^*\right) \geq 0. $$

### A.4. Proof of Proposition 4.

**Proof of (i):** Using the identity,

$$ \Delta(d-1, d-1, y) = (1+y)^{d-1} $$

we find that $y_1$ and $\tilde{y}_1$ are the solutions of Equations 2, and Equation 4 imply that $a^* = c/d$ when Proposition 3 I(i) states that this solution is unique.

In what follows let us consider $y_1$ and $\tilde{y}_1$ for which $\alpha = c/d$. We have

$$ \begin{aligned} \mathrm{L}_{\mathrm{r}}(s, c, c/d, y_1, \tilde{y}_1) = & \frac{d-2}{2} (I(s-c/d) + I(1-s-c/d) + 2I(c/d)) \\ & + d\delta \log(1+y_1) - \delta \log(\frac{\delta}{s-\alpha}) + d(1-\delta) \log(1+y_1) - (1-\delta) \log(\frac{1-\delta}{1-\delta-\alpha}) \\ & - c(\log y_1 + \log \tilde{y}_1) + \frac{c}{d} \log \left( \frac{c/d}{s-c/d} \right) + \frac{c}{d} \log \left( \frac{c/d}{1-s-c/d} \right), \end{aligned} $$

for which the right-hand side of the equality is exactly the function $\mathrm{LP}_{(d,d)}(s, c, y_1, \tilde{y}_1)$. Furthermore, since by using Stirling's approximation we have

$$ -c(\log y_1 + \log \tilde{y}_1) + \delta \log \Delta(d, d, y_1) + (1-\delta) \log \Delta(d, d, \tilde{y}_1) \approx \frac{1}{n} \log \left[ \binom{ds}{c} \binom{d(n-s)}{c} \right], $$

the function $\mathrm{L}_{\mathrm{r}}(s, c, c/d, y_1, \tilde{y}_1)$ is actually the large deviation parameter already appeared in [5].

**Proof of (ii):**
For this part, it is enough to show that the optimization of $LP_{r,\tilde{r}}(s, c, y, \tilde{y})$ with Conditions 3 is equivalent to optimizing $L\Gamma_r \varphi$ for Conditions 2. From Proposition 3 part I(ii) we know that when $r_1 = r_2 = r \le d-1$ and $\tilde{r}_1 = \tilde{r}_2 = \tilde{r} \le d-1$, we have a unique solution $a^* = c/d$. If we consider $y$ and $\tilde{y}$ when $\alpha = c/d$, as in the proof of Proposition 3 part I(ii)

$$ \frac{\Delta(d-1, r_1, y)}{y \Delta(d-1, r_2-1, y)} = \frac{s-c/d}{c/d} \quad \text{and} \quad \frac{\tilde{\Delta}(d-1, \tilde{r}_1, y)}{\tilde{y} \tilde{\Delta}(d-1, \tilde{r}_2-1, \tilde{y})} = \frac{1-s-c/d}{c/d} $$

and by Pascal's identity we have

$$ \Delta(d-1, r_1, y) + y \Delta(d-1, r_2-1, y) = \Delta(d, r, y) = \frac{s}{c} \sum_{k=0}^{r} k \binom{d}{k} y^k. $$

Therefore,

$$ y \frac{\partial}{\partial y} \log \Delta(d, r, y) = \frac{c}{s}, $$

and, similarly we have

$$ \tilde{y} \frac{\partial}{\partial \tilde{y}} \log \Delta(d, \tilde{r}, \tilde{y}) = \frac{c}{1-s}, $$

which are exactly Conditions 3. Finally, if we rewrite the function $L\Gamma_\pi$ using Equation 4, we have

$$ L\Gamma_r(s, c, c/d, y, \tilde{y}) = \frac{d-2}{2} (I(s-c/d) + I(1-s-c/d) + 2I(c/d)) + s \log \Delta(d-1, r, y) \\ + (1-s) \log \Delta(d-1, \tilde{r}, \tilde{y}) - c(\log y + \log \tilde{y}) - \frac{c}{d} \log \left( \frac{s}{c/d} - 1 \right) \left( \frac{1-s}{c/d} - 1 \right). $$

Using Conditions 3, knowing that

$$ \Delta(d-1, r_1, y) = \Delta(d, r_1, y) \left(1 - \frac{c}{d s}\right), \quad \Delta(d-1, \tilde{r}_1, \tilde{y}) = \Delta(d, \tilde{r}_1, \tilde{y}) \left(1 - \frac{c}{d(1-s)}\right), $$

it follows that,

$$ L\Gamma_r(s, c, c/d, y, \tilde{y}) = LP_{(r, \tilde{r})}(s, c, y, \tilde{y}). $$

### A.5. Proof of Claim 1.

*Proof.* It would have been nice to use the idea already used in the proof of Theorem 4.2 of [3], however, it seems that it is not easy to prove that the second derivative of the function $L\Gamma_r(s, d\delta\eta^*, \alpha^*, y^*, \tilde{y}^*)$ has exactly one root. Therefore, letting $c^* \stackrel{\text{def}}{=} d\delta\eta_d^*$, we prove the claim in two steps.

$$ (1) \text{ For } 0 \le s \le 2/5, \text{ we have } L\Gamma_r(s, c^*, \alpha^*, y^*, \tilde{y}^*) \le 0. $$

$$ (2) \text{ For } 2/5 \le s \le 1/2, \text{ we have } \frac{\partial}{\partial s} L\Gamma_r(s, c^*, \alpha^*, y^*, \tilde{y}^*) > 0. $$

**Proof of (1):**

First, note that by Lemma 1, for any $r \le r_b = (d-1, d, d-1, d)$ we have

$$ \overline{\text{REL}}_{\pi}(r) \le \overline{\text{REL}}_{\pi}(r_b). $$
<figure><img src="image_19.png" /><figcaption>FIGURE 8. (A) Inequality 11 for $3 \le d \le 1000$. For small degrees $3 \le d \le 11$ we use $\eta'_d$ instead of $\tilde{\eta}_d$. (B) Positiveness of Inequality 12 for degrees $3 \le d \le 1000$. Again, for small degrees $3 \le d \le 11$ we use $\eta'_d$ instead of $\tilde{\eta}_d$. Also, for $d \ge 15$ use Inequality 13. Blue dotted line and green dash-dotted lines correspond to $\delta = 0.5$ and $\delta = 2/5$, respectively.</figcaption></figure>

Also, by Part (i) of Proposition 4, the expansion lower-bound derived by Bollobás in [5] is an special case of $\overline{\mathrm{RELB}}_\pi(r)$ when $r = r_b$ and we saw that $y_1$ and $\tilde{y}_1$ are the solutions of Equations 3 when $\alpha = c/d$. For the function

$$ \mathrm{LP}_{(d,d)}(\delta, c^*, y_1, \tilde{y}_1) = -\left(\frac{d}{2}-1\right)H(\delta, 1-\delta) - \frac{c^*}{2} \left( \log \frac{c^*/d}{\delta - c^*/d} + \log \frac{c^*/d}{1-\delta - c^*/d} \right) \\ + \frac{d}{2} \left( \delta \log \frac{\delta}{\delta - c^*/d} + (1-\delta) \log \frac{1-\delta}{1-\delta - c^*/d} \right), $$

we know from Theorem 4.2. in [3] that the second derivative of this function with respect to $\delta$ has only one root. Also, it has a negative derivative at $\delta = 0$ and a positive derivative at $\delta = 1/2$. Hence, it is enough to show that for $\delta_0 \stackrel{\mathrm{def}}{=} 2/5$ and $c_0 \stackrel{\mathrm{def}}{=} d\delta_0\bar{\eta}_d$ we have

$$ \mathrm{LP}_{(d,d)}(\delta_0, c_0, y_1, \tilde{y}_1) < 0. \qquad (11) $$

This is true for large degrees as shown in Figure 8(A). However, for $3 \le d \le 11$, since the upper-bound $\bar{\eta}_d$ is too large, we use the assumption $\eta_d^* \le 1/2 - 0.75/\sqrt{d} \le \bar{\eta}_d$, which eventually turn out to be a true assumption.

**Proof of (2):** Again, using $Q(r_1, r_2, y^*) = \tilde{Q}(\tilde{r}_1, \tilde{r}_2, \tilde{y}^*) = 0$, and Equation 4, one may verify that,
$$
\begin{align*}
& \frac{\partial}{\partial s} \mathrm{L}\Gamma_r(s, c^*, \alpha^*, y^*, \tilde{y}^*) \\
&= -\frac{1}{2} \log \frac{s - \alpha^*}{1 - s - \alpha^*} + \frac{d-1}{2} \log \frac{s - \frac{c^* - \alpha^*}{d-1}}{1 - s - \frac{c^* - \alpha^*}{d-1}} \\
&\quad + \frac{c^*}{s} \left( \frac{1}{2} \left( \log y_1 + \log \tilde{y}_1 \right) - \left( \log y^* + \log \tilde{y}^* \right) \right) + \log \frac{\Delta(d-1, r_1, y^*)}{\Delta(d-1, \tilde{r}_1, \tilde{y}^*)} \\
&= -\frac{1}{2} \log \frac{s - \alpha^*}{1 - s - \alpha^*} - \frac{d-1}{2} \log \frac{s - \frac{c^* - \alpha^*}{d-1}}{1 - s - \frac{c^* - \alpha^*}{d-1}} + \frac{c^*}{s} \left( \frac{1}{2} \left( \log y_1 + \log \tilde{y}_1 \right) - \left( \log y^* + \log \tilde{y}^* \right) \right) \\
&\quad + (d-1) \log \frac{s}{1-s} + \log \frac{\Delta(d-1, r_1, y^*)}{(1+y^*)^{d-1}} - \log \frac{\Delta(d-1, \tilde{r}_1, \tilde{y}^*)}{(1+\tilde{y}^*)^{d-1}} \\
&\geq \underbrace{-\frac{1}{2} \log \frac{s - \alpha^*}{1 - s - \alpha^*} - \frac{d-1}{2} \log \frac{s - \frac{c^* - \alpha^*}{d-1}}{1 - s - \frac{c^* - \alpha^*}{d-1}}}_{g_1(s, c^*, \alpha^*)} + (d-1) \log \frac{s}{1-s} \\
&\quad + \frac{c}{s} \left( \frac{1}{2} \left( \log y_1 + \log \tilde{y}_1 \right) - \left( \log y^* + \log \tilde{y}^* \right) \right) + \log \Delta(d-1, r_1, y^*) - (d-1) \log(1+y^*).
\end{align*}
$$

But

$$
\frac{\partial}{\partial s} g_1(s, c^*, \alpha) = \frac{1}{2}(2s - 1) \left( \frac{1}{\left( (1-s) - \frac{c^*-\alpha}{d-1} \right) (s - \frac{c^*-\alpha}{d-1})} - \frac{1}{(s-\alpha)(1-s-\alpha)} \right),
$$

is negative when $a \le \frac{c^*/d}$ and positive otherwise. Therefore,

$$
\frac{1}{\eta_d^*} \frac{\partial}{\partial s} \mathrm{L}\Gamma_r(s, c^*, \alpha^*, y^*, \tilde{y}^*) \geq \\
\underbrace{-\frac{d}{2\eta_d^*} \log \frac{s - \frac{c^*}{d}}{1 - s - \frac{c^*}{d}} + \frac{d-1}{\eta_d^*} \log \frac{s}{1-s} + d \left( \frac{1}{2} \log \tilde{y}_1 - \log \tilde{y}^* + \frac{1}{2} \log y_1 - \log y^* \right)}_{\stackrel{\text{def}}{=} g_2(s, c^*)} \\
+ \frac{1}{\eta_d^*} \left( \log \Delta(d-1, r_1, y^*) - (d-1) \log(1+y^*) \right).
$$

We know from Proposition 3(II) that

$$
\frac{\partial}{\partial c} \mathrm{L}\Gamma_r = \frac{1}{2} \log \tilde{y}_1 - \log \tilde{y}^* + \frac{1}{2} \log y_1 - \log y^*,
$$

and consequently, one may use the same lower bound derived in that proof. Therefore, replac-
ing $y_{\delta^*}, \tilde{y}_{\delta^*}$ for $y^*, \tilde{y}^*$ in which we consider $\alpha^* = 0$ and noting that $y_1, y_{\delta^*}$ are independent of $s$,
we have

$$
\frac{\partial^2}{\partial s^2} g_2(s, c^*) = \frac{1}{\eta_d^*} \frac{d}{s^2} \left( \frac{d-1}{d} \frac{2(s-1/2)}{(1-s)^2} - \frac{s+c^*/d-1/2}{(1-s-c^*/d)^2} \right. \\
\left. + \frac{c^*}{ds} \left( \frac{s+c^*/(d-1)-1/2}{(1-s-c^*/(d-1))^2} - \frac{2(s+c^*/(d-1)-1/2)}{(1-s-c^*/(d-1))^2} \right) \right),
$$
which is negative when $(\delta + c^*/d - 1/2) \ge 0$. By using the expansion lower-bound obtained in [5] for small degrees and $\eta_d$ for large degrees, one may numerically verify that the second derivative is less than zero.

Therefore, since $g_2(\delta, c^*)$ is a concave function of $\delta$, if we define

$$x \stackrel{\text{def}}{=} \frac{\bar{\delta}d}{d-1} \bar{\eta}_d,$$

it is enough to show that for $\delta = 2/5$ and $\delta = 1/2$ we have

$$-\frac{d}{2\bar{\eta}_d} \log \frac{\delta(1-\bar{\eta}_d)}{1-\delta-\delta\bar{\eta}_d} + \frac{d-1}{\bar{\eta}_d} \log \frac{\delta}{1-\delta} + \frac{1}{\bar{\eta}_d} \left( \log \Delta \left( d-1, \lfloor \frac{d}{2} \rfloor, \frac{x}{1-x} \right) - (d-1) \log \left( 1+\frac{x}{1-x} \right) \right) \\ + d \left( \frac{1}{2} \log \frac{x/\bar{\delta}}{1-x/\bar{\delta}} - \log \frac{x}{1-x} + \frac{1}{2} \log \frac{x/\bar{\delta}}{\frac{1-\bar{\delta}}{\delta} - \frac{x}{x/\bar{\delta}}} - \log \frac{x}{\frac{1-\bar{\delta}}{\delta} - x} \right) > 0. \tag{12}$$

Again, for small $d$'s, one may verify that the above expression is positive and specifically note that for $3 \le d \le 11$ this is true when $\bar{\eta}_d$ is replaced by $\eta'_d$. While for larger $d$'s, as in Step 2 of Proposition 2, the inequality

$$\frac{\left(1 + \frac{x}{1-x}\right)^{d-1}}{1 + \left(\frac{x}{1-x}\right)^{\sqrt{2\frac{d-1}{\pi}}}} \le \Delta \left(d-1, \lfloor \frac{d}{2} \rfloor, \frac{x}{1-x}\right), \tag{13}$$

implies the positiveness of $\frac{\partial}{\partial \delta} \mathrm{L}\Gamma_r$ (see Figure 8(B)). $\square$

REFERENCES

[1] M. Aizenman and S. Warzel. *Random Operators*. Graduate Studies in Mathematics. American Mathematical Society, 2015. URL: https://books.google.com/books?id=gM9YCwAAQBAJ.

[2] N. Alon, Sh. Ganguly, and N. Srivastava. High-girth near-ramanujan graphs with localized eigenvectors. *Israel Journal of Mathematics*, 246:1–20, 2019. doi:10.1007/s11856-021-2217-y.

[3] A. Amit and N. Linial. Random lifts of graphs: Edge expansion. *Combinatorics, Probability and Computing*, 15(3):317–332, 2006. doi:10.1017/S0963548305007273.

[4] Y. Bilu and N. Linial. Lifts, discrepancy and nearly optimal spectral gap. *Combinatorica*, 26(5):495–519, 2006. doi:10.1007/s00493-006-0029-7.

[5] B. Bollobás. The isoperimetric number of random regular graphs. *Eur. J. Comb.*, 9(3):241–244, 1988. doi:10.1016/S0195-6698(88)80014-3.

[6] M. B. Cohen. Ramanujan graphs in polynomial time. In Irit Dinur, editor, *IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA*, pages 276–281. IEEE Computer Society, 2016. doi:10.1109/FOCS.2016.37.

[7] A. Daneshgar, M. Hejrati, and M. Madani. On cylindrical graph construction and its applications. *Electron. J. Comb.*, 23(1):1, 2016. arXiv:1406.3767v2, doi:10.37236/4609.

[8] A. Daneshgar and A. Taherkhani. A class of highly symmetric graphs, symmetric cylindrical constructions and their spectra. *Discret. Math.*, 342(1):96–112, 2019. doi:10.1016/j.disc.2018.09.022.

[9] J. Díaz, N. Do, M. J. Serna, and N. C. Wormald. Bounds on the max and min bisection of random cubic and random 4-regular graphs. *Theor. Comput. Sci.*, 307(3):531–547, 2003. doi:10.1016/S0304-3975(03)00236-6.

[10] J. Díaz, M. J. Serna, and N. C. Wormald. Bounds on the bisection width for random d-regular graphs. *Theor. Comput. Sci.*, 382(2):120–130, 2007. doi:10.1016/j.tcs.2007.03.003.

[11] J. S. Frame and D. C. Gilliland. Votes and a half-binomial. *Discret. Appl. Math.*, 12(1):31–40, 1985. doi:10.1016/0166-218X(85)90038-1.
[12] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. *Bulletin of the American Mathematical Society*, 43:439–561, 2006. doi:10.1090/s0273-0979-06-01126-8.

[13] S. Janson. Asymptotic equivalence and contiguity of some random graphs. *Random Struct. Algorithms*, 36(1):26–45, 2010. doi:10.1002/rsa.20297.

[14] S. Janson, A. Rucinski, and T. Luczak. *Random Graphs*. Wiley Series in Discrete Mathematics and Optimization. Wiley, 2011. URL: https://books.google.com/books?id=RjnqVoB4VmUC.

[15] B. Kolesnik and N. C. Wormald. Lower bounds for the isoperimetric numbers of random regular graphs. *SIAM J. Discret. Math.*, 28(1):553–575, 2014. doi:10.1137/120891265.

[16] A. V. Kostochka and L. S. Melnikov. *On a Lower Bound for the Isoperimetric Number of Cubic Graphs*, pages 251–265. De Gruyter, 1993. doi:10.1515/9783112318980-020.

[17] M. Lampis. Local improvement gives better expanders. CoRR, abs/1211.0524, 2012. arXiv:1211.0524.

[18] L. Lichev and D. Mitsche. On the minimum bisection of random 3-regular graphs. arXiv: Probability, 2020. doi:10.48550/arXiv.2009.00598.

[19] A. Lubotzky. *Discrete Groups, Expanding Graphs and Invariant Measures*. Progress in Mathematics. Birkhäuser Basel, 1994. URL: https://books.google.com/books?id=aNUR1zNuotEC.

[20] R. Lyons. Factors of IID on trees. *Comb. Probab. Comput.*, 26(2):285–300, 2017. doi:10.1017/S096354831600033X.

[21] M. Madani. Graph amalgams and its applications. *Ph.D. Thesis (In Persian)*, Sharif University of Technology, 2016.

[22] A. Marcus, D. A. Spielman, and N. Srivastava. Interlacing families I: bipartite ramanujan graphs of all degrees. In *54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2013, 26-29 October, 2013, Berkeley, CA, USA*, pages 529–537. IEEE Computer Society, 2013. doi:10.1109/FOCS.2013.63.

[23] N. C. Wormald. *Models of Random Regular Graphs*, page 239–298. London Mathematical Society Lecture Note Series. Cambridge University Press, 1999. doi:10.1017/CBO9780511721335.010.

A. DANESHGAR, DEPARTMENT OF MATHEMATICAL SCIENCES, SHARIF UNIVERSITY OF TECHNOLOGY, P.O. BOX 11155-9415, TEHRAN, IRAN

*Email address: daneshagr@sharif.ir*

M. H. SHOJAEDIN, DEPARTMENT OF MATHEMATICAL SCIENCES, SHARIF UNIVERSITY OF TECHNOLOGY, P.O. BOX 11155-9415, TEHRAN, IRAN

*Email address: mh.shojaedin94@sharif.ir*