Abstract 1 Introduction 2 Our Results 3 Proof Overview 4 Derandomized Squaring with Interesting Graphs References

Derandomized Squaring: An Analytical Insight into Its True Behavior

Gil Cohen ORCID Tel Aviv University, Israel Itay Cohen ORCID Tel Aviv University, Israel Gal Maor ORCID Tel Aviv University, Israel Yuval Peled ORCID The Hebrew University of Jerusalem, Israel
Abstract

The notion of the derandomized square of two graphs, denoted as G[Uncaptioned image]H, was introduced by Rozenman and Vadhan as they rederived Reingold’s Theorem, 𝐒𝐋=𝐋. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and other reasons, understanding the spectral expansion λ(G[Uncaptioned image]H) becomes paramount. Rozenman and Vadhan derived an upper bound for λ(G[Uncaptioned image]H) in terms of the spectral expansions of the individual graphs, λ(G) and λ(H). They also proved their bound is optimal if the only information incorporated to the bound is the spectral expansion of the two graphs.

The objective of this work is to gain deeper insights into the behavior of derandomized squaring by taking into account the entire spectrum of H, where we focus on a vertex-transitive c-regular H. Utilizing deep results from analytic combinatorics, we establish a lower bound on λ(G[Uncaptioned image]H) that applies universally to all graphs G. Our work reveals that the bound is the minimum value of the function

dxd(d1)χx(H)χx(H)

in the domain (c,), where χx(H) is the characteristic polynomial of the d-vertex graph H. This bound lies far below the known upper bound for λ(G[Uncaptioned image]H) for most reasonable choices for H. Empirical evidence suggests that our lower bound is optimal. We support the tightness of our lower bound by showing that the bound is tight for a class of graphs which exhibit local behavior similar to a derandomized squaring operation with H. To this end, we make use of finite free probability theory.

In our second result, we resolve an open question posed by Cohen and Maor (STOC 2023) and establish a lower bound for the spectral expansion of rotating expanders. These graphs are constructed by taking a random walk with vertex permutations occurring after each step. We prove that Cohen and Maor’s construction is essentially optimal. Unlike our results on derandomized squaring, the proof in this instance relies solely on combinatorial methods. The key insight lies in establishing a connection between random walks on graph products and the Fuss-Catalan numbers.

Keywords and phrases:
Derandomized Squaring, Spectral Graph Theory, Analytic Combinatorics
Funding:
Gil Cohen: Supported by ERC starting grant 949499 and by the Israel Science
Foundation grant 1569/18.
Itay Cohen: Supported by ERC starting grant 949499 and by the Israel Science Foundation
grant 1569/18.
Gal Maor: Supported by ERC starting grant 949499 and by the Israel Science Foundation
grant 1569/18.
Copyright and License:
[Uncaptioned image] © Gil Cohen, Itay Cohen, Gal Maor, and Yuval Peled; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Spectra of graphs
Related Version:
Full Version: https://eccc.weizmann.ac.il/report/2023/183/
Editors:
Raghu Meka

1 Introduction

Expander graphs have played a crucial role in essentially all areas within theoretical computer science as well as in coding theory, and cryptography, among others. Their utility stems to a large extent from the ability to interpret expansion from various perspectives, be it combinatorial, probabilistic, or linear algebraic. This multifaceted understanding offers a unique advantage: it enables the otherwise challenging inference of combinatorial attributes of graphs by examining the spectral properties of related operators.

We briefly recall the notion of spectral expansion. Let G be an undirected d-regular graph on n vertices with adjacency matrix 𝐀. Since G is undirected, 𝐀 is symmetric and so its spectrum is real-valued. We denote the eigenvalues of 𝐀 by d=λ1λ2λn. The spectral expansion of G, denoted as λ(G), is given by max(λ2,|λn|). We further denote the normalized spectral expansion of G by ω(G)=λ(G)d[0,1]. We alternate between the two variants–the normalized and the unnormalized–depending on context.

An expander is a graph G with a normalized spectral expansion ω(G) that is bounded away from 1 111To be more precise, it is common to consider a family of graphs in this context. However, we will exclude this technical detail from our discussion for simplicity.. However, for a typical application of expander graphs one “pays” a cost that increases with the degree d and has an “error” that vanishes as ω(G)0. This raises the question of what is the lowest possible value of ω(G) attainable by d-regular graphs. From the Alon-Boppana bound [30], which is usually stated in terms of λ(G), it follows that for every ε>0 there are only finitely many d-regular graphs G with λ(G)2d1ε. A d-regular graph G satisfying λ(G)2d1 is called a Ramanujan graph. Over the past several decades, Ramanujan graphs have been a focal point of research. The constructions of Ramanujan graphs and their variants lean on profound number theoretic results [19, 24, 27] (see also [18]), or is rooted in deep analytical methods and on the accompanied technique of polynomial interlacing [20, 23, 22, 13, 16].

In their highly influential paper [34], Reingold, Vadhan, and Wigderson introduced the Zig-Zag product which enabled them to obtain a combinatorial construction of expander graphs by elementary means. While the expanders that were constructed were not quite close to Ramanujan, the fact that the construction is combinatorial and highly flexible made the Zig-Zag product extremely useful. Indeed, no long after, Reingold [33] based his breakthrough result, 𝐒𝐋=𝐋, on the Zig-Zag product, not for constructing expanders per se but for the purpose of “transforming” a given graph to an expander while maintaining its connected components structure. In a subsequent work, Ben-Aroya and Ta-Shma [5] put forth an improved variant of the Zig-Zag product, dubbed the wide-replacement product, that enabled the combinatorial construction of graphs that come quite close to Ramanujan. That variant was key in a recent breakthrough by Ta-Shma who constructed near-optimal small-bias sets [36]. Several other expander construction paradigms have been put forth in the literature, e.g., [6, 26]. We refer the reader to the excellent survey by Hoory, Linial, and Wigderson [17] for a comprehensive exposition on expander graphs.

1.1 Derandomized squaring

Not long after the work of Reingold [33], Rozenman and Vadhan [35] introduced a close sibling to the Zig-Zag product, dubbed derandomized squaring, which we describe soon. This operation can be “cleaner” than the Zig-Zag product in some settings, in particular for their rederivation of Reingold’s result, though the two operations are tightly connected. In the past few years, derandomized squaring has gained significant traction in the space-bounded derandomization literature (see, e.g., [28, 1, 2, 11]) mostly since it facilitated the adaptation of ideas from the realm of fast Laplacian solvers into the domain of space-bounded derandomization. For these reasons, in this paper we focus on the operation of derandomized squaring though we are confident that our techniques can be extended to other operations such as the Zig-Zag product and the wide-replacement product.

Squaring a graph is an easy way of improving its normalized spectral expansion. The square of a graph G, denoted as G2, is the graph on the same vertex set that has an edge between a pair of vertices for every length-2 path in G between the vertices. Clearly, if 𝐀 is the adjacency matrix of G then 𝐀2 is the adjacency matrix of G2. Hence, ω(G2)=ω(G)2. However, if G is d-regular, G2 is a d2-regular graph. As a result, the degree growth associated with squaring the graph often surpasses the advantages gained from reducing the normalized spectral expansion. The purpose of derandomized squaring is to obtain a comparable improvement to the normalized spectral expansion without blowing up the degree by a quadratic factor.

From the view point of a vertex v of G, in the graph G2, the neighbors of v are all connected to each other. That is, G2 is obtained by adding copies of the complete graph with self-loops, one copy for each vertex v, where the complete graph associated with v is placed on the neighbors of v. Let H be a graph on d vertices, where we focus on the case in which H is vertex-transitive, and denote the degree of a vertex in H by c. The derandomized square of G and H, denoted as G[Uncaptioned image]H, is defined by replacing each such copy of the complete graph with a copy of H. Note that G[Uncaptioned image]H is a D-regular graph where D=dc. Formally, the derandomized squaring, like the Zig-Zag product, requires working with edge-labeled graphs, but we sidestep this technicality. For the reader that is familiar with these intricacies, we remark that, for simplicity, in this extended abstract we circumvent labeling issues by assuming that G is given as the union of d perfect matchings, though this condition can be relaxed.

Given that an expander H approximates the complete graph, one is correct to expect that the derandomized square G[Uncaptioned image]H approximates G2 for every graph G. Rozenman and Vadhan formalized this intuition with regards to the normalized spectral expansion by establishing the bound

ω(G[Uncaptioned image]H)(1ω(H))ω(G)2+ω(H)ω(G)2+ω(H). (1.1)

How tight is this bound? This is a somewhat subtle question. Rozenman and Vadhan proved that the bound is tight as a function of ω(G) and ω(H), however, it is certainly conceivable that a superior bound might be achieved if one incorporates more information about the graphs beyond just their spectral expansions into the bound. In particular, if we fix H and consider the mapping λ([Uncaptioned image]H) which maps every d-regular graph G to λ(G[Uncaptioned image]H), then it is interesting to ask how strong a bound can be obtained on this mapping as a function of the entire spectrum of H.

Given the significance of the derandomized squaring operation, and the related Zig Zag product as well as the wide-replacement product, a substantial improvement to the bound could profoundly impact our understanding on several fundamental problems, including in space-bounded derandomization and in coding theory. For example, in the context of space-bounded derandomization such a result may reduce the seed length of PRGs or weighted PRGs (see [9, 10, 11] and references therein). Such a result may also lead to a better construction of small-bias sets in which the wide-replacement product is used for bias-reduction. Therefore, gaining a thorough understanding of derandomized squaring is highly motivated from the theoretical computer science standpoint.

1.2 Two case studies

Before presenting our results, which we view as a first step towards the above goal, we wish to highlight the gap between the Rozenman-Vadhan bound, as given in Equation 1.1, and the “true” behavior of the derandomized squaring operation. We do so by considering two case studies, starting with H=Kc,c, the complete c=d2-regular bipartite graph on d vertices.

1.2.1 Derandomized squaring with the complete regular bipartite graph

Since H=Kc,c is bipartite, ω(H)=1, and so the bound given by Equation 1.1 becomes trivial, ω(G[Uncaptioned image]H)1 for all d-regular graphs G. For this special case, one can get a nontrivial bound by elementary means by incorporating some information on G. To see this, assume that G is the union of two c-regular Ramanujan graphs on n vertices, whose adjacency matrices are denoted 𝐁 and 𝐑, respectively. That is, the adjacency matrix of G is given by 𝐀=𝐁+𝐑. Thus, it can be shown that the adjacency matrix of G[Uncaptioned image]H can be expressed as 𝐑𝐁+𝐁𝐑 222With regards to the edge labeling, for the last statement to hold we assume that neighbors 1,,d2 of every vertex are those coming from 𝐁 and the remaining neighbors d2+1,,d are coming from 𝐑., and so by the Courant-Fischer Theorem,

λ(G[Uncaptioned image]H)=2maxx𝟏x𝖳𝐁𝐑xx𝖳x2(2d21)232D15.66D1,

where D=d22 is the regularity of G[Uncaptioned image]H.

Although the above bound on λ(G[Uncaptioned image]H) certainly beats the trivial bound, D, it still seems to undersell the typical behavior of G[Uncaptioned image]H. In fact, by sampling 333Our sampling is done by taking the union of d uniformly random and independent perfect matchings, where edges that are sampled multiple times are counted with the respective multiplicity. a random d-regular graph G and evaluating λ(G[Uncaptioned image]H), one can verify that for a sufficiently large d, the value of λ(G[Uncaptioned image]H) distributes around 2.35D1. But where does the 2.35 value originate? How can this number be determined based on our selected H? Jumping the gun, the analytical tool we introduce predicts that the exact value, for this H, is

1211+552.35. (1.2)

By saying that we “predict” this bound captures the true behavior of derandomized squaring with H=Kc,c, we mean the following: First, we prove the aforementioned value to be a lower bound on λ(G[Uncaptioned image]H) for every d-regular graph G; Second, we prove the existence of infinitely many graphs that meet this bound. These graphs exhibit a local structure resembling a derandomized square with H. Lastly, our predictions align with every experiment we made for every graph H and when G is sampled uniformly at random. We provide further details in Section 2, where our results are formally presented.

1.2.2 Derandomized squaring with a Paley graph

In the aforementioned example, the Rozenman-Vadhan bound was non-informative. It is worth noting that it is not just in these instances where the typical performance of the derandomized square surpasses the predictions of the bound. To give one such example, consider a Paley graph on d vertices, denoted as Pald. For a typical d-regular graph G, the limit behavior as d of the spectral expansion λ(G[Uncaptioned image]Pald), when properly normalized, is predicted by our analytic tool to equal

limdλ(G[Uncaptioned image]Pald)D1=1+13+16282.46, (1.3)

where D=d(d1)2 is the degree G[Uncaptioned image]Pald. This should be compared with a bound of 2, the least possible value given the Alon-Boppana bound. Additionally, it should be compared with Equation 1.1, which, irrespective of the choice of G, cannot produce a bound lower than O(D1/4).

From the preceding discussion and, in particular, the two case studies, a key question lingers: Is there an exact formula or efficient method that enables us to compute, and more importantly, to gain insight on the spectral expansion of the operation of derandomized squaring with H?

2 Our Results

As our case studies suggest, the spectral expansion of the graphs G and H might not adequately represent the spectral expansion of their derandomized square. In this paper we initiate the study of the following question:

Main Question.

What is the “true” behavior of the spectral expansion of derandomized squaring?

We turn to give a brief summary of our results. We elaborate further on each of these results in the subsequent sections, Sections 2.1, 2.2, and 2.3.

Limitations of derandomized squaring

Our first result is a lower bound on λ(G[Uncaptioned image]H), factoring in the full spectrum of H, which holds for every graph G. Encoding this spectrum by the characteristic polynomial of H, denoted as χx(H), our work reveals that the bound is the minimum value of the function

dxd(d1)χx(H)χx(H) (2.1)

in the domain (c,), where recall that d and c are the degrees of G and H, respectively. Our proof leans on deep results from analytic combinatorics and the symbolic method. Although this bound may look more complicated than Equation 1.1, it is easy to calculate for various explicit choices of H, and easy to bound for families of graphs, as we will examplify in Section 2.1 (a more comprehensive review of examples, including the ones discussed in Section 1.2, is done in Section 4).

Based on our empirical experiments, it appears that our lower bound is tight in a strong sense, namely, for every vertex-transitive graph H and for a typical graph G. However, a definitive proof of the bound’s tightness eludes us in general. In spite of this, we have made notable progress by first proving tightness of the bound for particular choices of H, and second by proving its tightness for a broader class of graphs, we term H-local graphs. For obtaining this result we make use of finite free probability theory and the accompanied technique of interlacing. These were instrumental in the seminal works of Marcus, Spielman, and Srivastava [21, 22, 23] who introduced these techniques for their study of bipartite Ramanujan graphs. We elaborate on this in Section 2.2.

Comparison to known bounds

The lower bound described above requires solving a separate polynomial equation for every choice of H. However, restricting the discussion to reasonable choices of H–for example, graphs H having no self loops–we show universally that the lower bound for ω(G[Uncaptioned image]H) lies within the range (2dc,3dc), very close to the Alon-Boppana bound and significantly distant from Equation 1.1 that suggests at best that ω(G[Uncaptioned image]H)=O(1c). As discussed above, we also expect our lower bound to represent the behavior of G[Uncaptioned image]H for a typical choice of G. Note that the restriction of H to simple graphs makes sense, as in all applications of derandomized squaring we are aware of, H is for our choosing.

The proof of Rozenman and Vadhan [35] for the tightness of Equation 1.1 involves a choice of H which is a graph with many self loops. Moreover, our lower bound applied to this specific choice (see Section 4.1.3) exactly yields the formula given by Equation 1.1. This suggests that a better upper bound should hold for particular choices of H (potentially under some assumptions on G). We leave these intriguing open questions for future work.

A lower bound for rotating expanders

In the process of establishing our lower bound on the spectral expansion of derandomized squaring, we address an open problem concerning the spectral expansion of rotating expanders [12]. In this recent paper, random walks on expanders were studied, wherein a permutation is applied to the vertices following each step. The objective of this approach is to mitigate the inherent exponential deterioration of the spectral expansion with respect to the length of the walk. Indeed, the authors proved that by using a carefully chosen permutation sequence, the deterioration can be reduced from exponential to linear. The authors left open the question of whether their construction is optimal.

In this work, we resolve this question by proving the optimality of their construction. More generally, we prove that a graph which is constructed as a graph product is inherently far from Ramanujan. Our key observation lies in relating the problem with the Fuss-Catalan numbers which generalize the Catalan numbers that emerge when bounding the spectral expansion of d-regular graphs. We elaborate on this in Section 2.3, where we also give the necessary background on rotating expanders.

A broader perspective: beyond spectral expansion

Almost all of the numerous works and applications of spectral expanders in theoretical computer science, indeed, the very definition of a spectral expander G, rely on the notion of the spectral expansion, λ(G). Only a few instances utilize the entire spectrum of G, which holds significantly more, and sometimes vital, information about the graph. In their seminal series of works, Marcus, Spielman, and Srivastava developed finite free probability as a framework to handle the full spectrum of a graph. As mentioned, this enabled them to establish the existence of bipartite Ramanujan graphs of all sizes and degrees.

Our current work serves as a further exploration into analyzing graphs beyond their spectral expansion. Instead of aiming to construct expanders, our objective is to achieve a deeper insight into the derandomized squaring operation. While we primarily target the spectral expansion of the derandomized square G[Uncaptioned image]H, our approach involves leveraging the entire spectrum of H for establishing our bounds. In addition to our use of finite free probability, we employ deep results from analytic combinatorics, and the framework offered by the symbolic method. We posit that working with the full spectrum of a graph could yield significant results and improvements for various problems in theoretical computer science, and we believe that the deep results we use could be advantageous in other scenarios where analyzing the full spectrum is desired.

Related work

Already at this point, prior to delving into the formal details concerning our results, we would like to highlight some related work. Our study of the graph G[Uncaptioned image]H for a d-regular graph G is done by considering the graph 𝒯d[Uncaptioned image]H, where 𝒯d is the d-ary infinite tree. The study of graphs, which represent the quotient of a given (typically infinite) graph X, has a long history (see [15] as an example). Of particular interest are the extreme graphs, known as X-Ramanujan graphs. The reader is referred to [25, 31] and references therein for more details. Our result supporting the tightness of our lower bound, presented in Section 3.2.2, can also be derived from the work of Mohanty and O’Donnell [25]. For completeness and accessibility of our paper, we present the full proof here, as it sheds more light on Equation 2.1 and connections between analytic combinatorics and free probability which we discuss further in Section 2.2.

Regarding our lower bound, the spectral radius of operators associated with infinite graphs has been extensively explored. This is particularly true when these graphs exhibit a well-defined group-theoretic structure. Analytic combinatorics has a well-established presence in this context [37]. Finally, it is noteworthy that the Fuss-Catalan numbers are significant in free probability theory and have known associations with the product of certain random matrices [32].

2.1 Limitations of derandomized squaring

Let H be a vertex-transitive graph on d vertices. Recall that, throughout, c denotes the degree of a vertex in H. In this section we state our result regarding the lower bound on λ(G[Uncaptioned image]H) which holds for every d-regular graph G. As previously suggested, our approach integrates the complete spectrum of H into the bound. This integration is accomplished by encoding the spectrum through the characteristic polynomial of H-s adjacency matrix, denoted as χx(H)=i=1d(xλi), where, as before, c=λ1λd are the corresponding eigenvalues.

Theorem 1.

Let H be a vertex-transitive c-regular graph on d3 vertices, where c1. Let x0 be the largest real solution to the polynomial equation

(d1)χx(H)χx′′(H)=(d2)χx(H)2. (2.2)

Then, for every d-regular graph G on n vertices, λ(G[Uncaptioned image]H)ΛHon(1), where

ΛHd(x0(d1)χx0(H)χx0(H)). (2.3)

As shown in the proof of Theorem 1, despite the polynomial equation from Equation 2.2 usually yielding complex solutions, there is always at least one real solution. Experiments overwhelmingly suggest that the bound accurately reflects the behavior of λ(G[Uncaptioned image]H) for a typical graph G. Having this in mind, we may posit that the structure of Equations 2.2 and 2.3, namely, (d1)ΦΦ′′=(d2)(Φ)2, and the accompanied expression d(x(d1)Φ(x)Φ(x)), epitomize the derandomized squaring operation with a typical d-regular graph. By setting Φ=χ(H), we incorporate details about H.

Although the proof of Theorem 1 leans on deep results from analytic combinatorics and the symbolic method, employing the theorem remains elementary. However, as perhaps anticipated, it is not as direct as the Rozenman-Vadhan bound from Equation 1.1, but rather it requires finding the largest real solution to a polynomial equation.

Before proceeding further, we introduce the following notation. Recall that G[Uncaptioned image]H is D-regular where D=cd. We define κH=ΛHD1, and note that, due to the Alon-Boppana bound, κH[2,DD1][2,D].

Equivalent reformulations of Theorem 1

One can alternatively recast our procedure for finding a lower bound for λ(G[Uncaptioned image]H), as given by Theorem 1, in several equivalent ways, as we describe next.

The Cauchy transform is a useful analytic tool which we will make an extensive use of in this paper. For a graph H on d vertices, the Cauchy transform takes a simple form and is given by

𝒢H(x)=1dχx(H)χx(H)=1di=1d1xλi. (2.4)

Using the Cauchy transform we can reformulate Theorem 1 as follows.

Theorem 2 (Recasting Theorem 1 in terms of the Cauchy transform).

Let H be a vertex-transitive c-regular graph on d3 vertices, where c1. Let x0 be the unique positive real solution to the equation

dd1𝒢H(x)2+𝒢H(x)=0. (2.5)

Then, for every d-regular graph G on n vertices, λ(G[Uncaptioned image]H)ΛHon(1), where

ΛH=dx0d1𝒢H(x0). (2.6)

We emphasize that, as demonstrated in the proof of Theorem 2, there always exists a positive real solution to Equation 2.5 and it is unique.

By defining ψH(x)=dxd1𝒢H(x), it can further be shown that

ΛH=minx>cψH(x), (2.7)

where the minimal point x0>c exists and is unique (see the full version of the paper for the details).

2.2 Tightness of the lower bound

As previously discussed, we have yet to establish that the lower bound provided by Theorem 1 is tight in general. However, empirical results strongly suggest its accuracy. Specifically, we believe this to be true for every vertex-transitive graph H on d vertices and for a typical d-regular graph G. In light of the evidence supporting this assertion, as we discuss next, we will formulate it as a conjecture in Section 2.4. In order to state our analytic evidence for the tightness of our bound, we observe that from the perspective of a vertex v in G[Uncaptioned image]H, the vertex v participates in d instances of H. This is because each of the d neighbors of v positions it within a copy of H. We call a graph that has the above local property an H-local graph (see the full version of this paper for the formal definition). The following theorem formalizes the evidence we have gathered for the tightness of our lower bound.

Theorem 3.

For every vertex-transitive graph H on d3 vertices and for every n1, there exists an H-local graph XH on nd vertices such that λ2(XH)ΛH.

In addition to Theorem 3, we prove the optimality of our lower bound for λ(G[Uncaptioned image]H) in three specific cases of H: the clique with self-loops, where G[Uncaptioned image]H corresponds to the actual squaring operation; the clique without self-loops, which corresponds to a non-backtracking length-2 random walk; and lastly, the graph employed in the Rozenman-Vadhan bound’s tightness result. We provide further details on these cases in Section 4.1. Going back to Theorem 3, note that we manage to bound only the second-largest eigenvalue, λ2(X), rather than the spectral expansion λ(X)=max(λ2(X),|λn(X)|). Graphs with such property are termed one-sided spectral expanders. These graphs are suitable for numerous applications, primarily due to the fact that this property alone suffices for the Alon-Chung Lemma [3].

The proof of Theorem 3 leverages finite free probability and the interlacing technique that were developed by Marcus, Spielman, and Srivastava [21, 22, 23]. We provide a high-level overview for the proof of Theorem 3 in Section 3.2, however, already here we emphasize that the fact that our lower bound, which is based on results from analytic combinatorics, matches our upper bound which is rooted in tools from free probably theory is an instantiation of a deep connection between the two fields. This has to do with the fact that one combinatorial proof for the Lagrange inversion formula–a tool used under the hood in our lower bound–makes use of Lukasiewicz paths that in turn are tightly connected to the lattice of non-crossing partitions which is at the heart of free probability theory. The reader is referred to Chapter 16 in the excellent book by Nica and Speicher [29] to learn more about this connection, though for our purpose, of studying the derandomized squaring operation, we give a direct and self-contained proof in the full version of the paper.

2.3 Lower bound on the spectral expansion of rotating expanders

A “standard” length-t random walk on a graph G is analyzed by considering the power graph, denoted as Gt, generalizing the square of the graph G2 which was discussed so far. This graph encodes the number of length-t walks by introducing an edge for each such walk between the two corresponding vertices. It is easy to see that if 𝐀 is the adjacency matrix of G, then the matrix 𝐀t is the adjacency matrix of Gt. Consequently, the spectral expansion of Gt, which is the most pertinent quantity when examining length-t random walks on G, is given by λ(Gt)=λ(G)t. In particular, if G is a d-regular Ramanujan graph, then λ(Gt)=2Ω(t)D1, where D=dt is the degree of Gt. Therefore, even if G is initially Ramanujan, the power graph is exponentially distant, in t, from Ramanujan.

With an eye towards potential applications to theoretical computer science, Cohen and Maor [12] proposed that permuting the vertices after each step (in a palindrome fashion to result in an undirected graph) can circumvent this exponential deterioration. More precisely, the authors proved that for every d-regular Ramanujan graph G with adjacency matrix 𝐀, and for every integer t2, there exists a sequence of permutation matrices 𝐏=(𝐏1,,𝐏t1) such that the graph G𝐏, whose adjacency matrix is given by

𝐀𝐏=𝐀𝐏t1𝐀𝐏1𝐀2𝐏1𝖳𝐀𝐏t1𝖳𝐀,

has spectral expansion

λ(G𝐏)(1+1t)t(t+1)D+o(1), (2.8)

where D=d2t is the degree of G𝐏 and the o(1) term is a quantity that vanishes exponentially fast with the girth of G, and should be ignored in this introductory section. Specifically, by permuting the vertices after each step using suitable permutations, the deterioration is reduced from exponential to linear in t.

An open problem left in [12] is to establish a lower bound on the spectral expansion of G𝐏 that is applicable for any permutation sequence 𝐏. Specifically, the authors left open the question of whether the linear dependence in t is optimal. Experimental results suggest that for a typical 𝐏, Equation 2.8 holds with equality, up to the vanishing o(1) term. However, it is entirely plausible that the typical behavior does not accurately represent the behavior of the optimal permutation sequence 𝐏. The logic would be that for a graph with substantial structure, such as a Cayley graph, a permutation sequence that takes into account the structure of the underlying group and the set of generators may yield a superior spectral expansion. However, in this work we resolve this open problem by proving that the bound is indeed tight.

Theorem 4.

For every d-regular graph G and for every permutation sequence 𝐏=(𝐏1,,𝐏t1),

λ(G𝐏)(1+1t)t(t+1)Do(1).

In fact, our lower bound applies to the product of any d-regular graphs, not only isomorphic graphs as used in the construction of G𝐏. For t=1, where no actual product is involved, this essentially aligns with the Alon-Boppana bound. As suggested by Theorem 4 (ignoring the o(1) term), we have λ(G𝐏)=λ(G2)4D. However, for t=2, the bound increases to λ(G𝐏)3322D=6.75D, and for t=3, it further deteriorates to λ(G𝐏)4433D9.48D. As indicated, the gap for graph products increases linearly with the number of graphs involved, making them inherently far from Ramanujan.

2.4 Two conjectures and open problems

Given our results and the above discussion, we wish to put forth two conjectures that capture different aspects of the tightness of our lower bound as given by Theorem 1. These are analog to fundamental questions on Ramanujan graphs where Theorem 1 plays in this analogy the role of the Alon-Boppana bound.

Conjecture 5.

For every vertex-transitive graph H, λ(G[Uncaptioned image]H)ΛH holds for infinitely many graphs G.

5 is analog to the fundamental question regarding the existence of Ramanujan graphs which has received significant attention in the literature. Resolving 5 with respect to λ2(G[Uncaptioned image]H) would be interesting as well. Our second conjecture focuses on the typical behavior, and is analogous to Friedman’s resolution [14] of Alon’s conjecture [4] (see also [7]). We first introduce the following notation: For an even integer n and for an integer d, we let n,d denote the distribution over d-regular graphs on n vertices that are sampled by taking the union of d uniformly random and independent perfect matchings, where edges that are sampled multiple times are counted with the respective multiplicity.

Conjecture 6.

For every vertex-transitive graph H on d vertices and for every ε>0,

𝐏𝐫Gn,d[λ(G[Uncaptioned image]H)ΛH+ε]=on(1).

Note that a similar statement is proven in [8] for a wide variety of graph distributions. However, these do not include the one suggested above for graphs of the form G[Uncaptioned image]H.

In addition to the conjectures previously discussed, our research raises several intriguing questions. An obvious open problem is the generalization of our results to non-vertex-transitive graphs. For potential theoretical computer science applications, it would be pertinent to identify conditions that a pair of graphs G and H satisfy so that the spectral expansion λ(G[Uncaptioned image]H) is close to our lower bound or, at a minimum, substantially improves upon the Rozenman-Vadhan bound. Once this aspect is clearer, problems regarding the explicitness can be addressed. To give just one additional research question, we believe that the extension of our techniques to additional graph operations, including the Zig-Zag product and the wide-replacement product, is feasible. We defer this exploration to future research.

Organization of the rest of the paper

In Section 3 we give a high-level proof overview of our results on the derandomized squaring operator. The detailed proofs of the theorems stated above are provided in the full version of this paper. In Section 4 we apply our results to interesting graph families, and prove our universal bound on κH for simple graphs.

3 Proof Overview

In this section, we provide an informal overview of the proofs for our results. We begin with our lower bound for the spectral expansion of derandomized squaring, as given by Theorem 1 (outlined in Section 3.1). Our proof relies on the symbolic method and leverages results from analytic combinatorics, both of which we introduce and explain in the full version of this paper. Additionally, we briefly outline the proof for our evidence regarding the tightness of our lower bound, as stated in Theorem 3, in Section 3.2. In that section, we provide the necessary background on finite free probability, which is essential for understanding the proof.

3.1 Limitations of derandomized squaring

As before, let G be a d-regular graph and H a vertex-transitive c-regular graph on d vertices. In this section we sketch the proof for our lower bound on λ(G[Uncaptioned image]H), as stated in Theorem 1. Our starting point is standard, relying on the trace method which asserts that λ(G[Uncaptioned image]H) is lower bounded by roughly c(G[Uncaptioned image]H)1/ for every >0, where c(G[Uncaptioned image]H) is the number of length- cycles that originate at some fixed vertex v of G[Uncaptioned image]H. Thus, the task at hand is to compute, or at least lower bound c(G[Uncaptioned image]H), where we will choose to be sufficiently large. A common strategy for this is to consider a suitable infinite cover of the graph of interest, G[Uncaptioned image]H in our case, which we take to be 𝒯d[Uncaptioned image]H, where 𝒯d is the d-regular infinite tree. Indeed, for every , every length- cycle in 𝒯d[Uncaptioned image]H that originated at some fixed vertex induces a unique cycle in G[Uncaptioned image]H, initiated at some fixed vertex, and so c(G[Uncaptioned image]H)c(𝒯d[Uncaptioned image]H).

We obtain an accurate estimate on c(𝒯d[Uncaptioned image]H) by first expressing the combinatorial class of cycles in 𝒯d[Uncaptioned image]H using the symbolic method, from which we immediately derive a functional equation that is satisfied by the corresponding generating function. We then use results from analytic combinatorics to get the desired estimate on the coefficients of the latter. The symbolic method, a prominent combinatorial theory, allows one to deduce a functional equation that is satisfied by the class’s generating function straight from its specification. Following this, in Section 3.1.1, we utilize the symbolic method to define the cycle class in 𝒯d[Uncaptioned image]H and from there, derive a functional equation that is satisfied by the associated generating function.

With the functional equation in hand, our objective is to deduce estimates of its coefficients. To achieve the estimate, we employ deep results from analytic combinatorics. These treat the functional equation as a meromorphic function, considering its singularities to determine the bound.

3.1.1 The functional equation for derandomized squaring

Refer to caption
Figure 1: Cycles in 𝒯4Refer to captionC4. The black edges represent the edges of 𝒯4, while the red edges represent those of 𝒯4Refer to captionC4. Dashed red edges indicate the truncated edges. Edges that are irrelevant to the cycles of v (e.g., (u1,x1)) have not been included in the figure. The blue cycle within 𝒯4Refer to captionC4 corresponds to the cycle (vw1w2w3v) within the copy of H centered around vertex u1. In this cycle, the first, second, and last steps are substituted with the pair (,ϵ), while the third step is substituted with the pair (,c), where c represents a nested cycle from 𝒞𝒯dRefer to captionH (specifically, c=(w3y1y2y3w3)).

Let H be a vertex-transitive graph on d vertices. Define 𝒞𝒯d[Uncaptioned image]H as the combinatorial class of cycles in 𝒯d[Uncaptioned image]H that originate at the root. As previously mentioned, the size function corresponds to the cycle’s length. To prevent double-counting, we exclude the empty cycle from this class. When expressing the class using the symbolic method, we use 𝒮H to represent the combinatorial class of nonempty cycles in H that only revisit the originating vertex upon completing the cycle. Consequently, as detailed below, after truncating one branch of the root, and overriding the class definition of 𝒞𝒯d[Uncaptioned image]H to capture cycles on the truncated graph, it satisfies the recursive relation

𝒞𝒯d[Uncaptioned image]H={1,,d1}×(𝒮H(×(𝒞𝒯d[Uncaptioned image]H+ϵ))). (3.1)

Here, symbolizes an atom, which we interpret as a step within a cycle in H.

To see this, remember that each child of the root positions the root within a copy of H. Therefore, when describing a non-empty cycle originating at the root, we first select one of its d1 children, which determines the copy of H in which the root is involved. Now, consider any cycle within that copy of H starting at the root, v1v2v=v1. This cycle corresponds to a cycle in 𝒯d[Uncaptioned image]H that begins at the root in the following manner: After each step vivi+1 on the cycle, we examine the copy of 𝒯d[Uncaptioned image]H rooted at vi+1 and attach a cycle from that copy of 𝒯d[Uncaptioned image]H. When we return to vi+1, we proceed with vi+1vi+2. Note that attaching an empty cycle is permissible, even though it is not included in 𝒞𝒯d[Uncaptioned image]H, leading to the addition of the neutral element ϵ in Equation 3.1. Furthermore, after the final step v1v=v1, we attach another (potentially empty) copy of 𝒞𝒯d[Uncaptioned image]H to account for cycles that visit the root more than twice. This rationale underpins our definition of 𝒮H, which is designed to prevent over-counting that would have otherwise occur.

Equation 3.1 directly implies that the generating function, C𝒯d[Uncaptioned image]H(z), associated with the class 𝒞𝒯d[Uncaptioned image]H satisfies

C𝒯d[Uncaptioned image]H(z)=(d1)SH(z(C𝒯d[Uncaptioned image]H(z)+1)), (3.2)

where SH(z) is the generating function corresponding to the class 𝒮H. On its own, this result does not provide much insight, as the functional equation u=(d1)SH(z(u+1)) tends to be intricate, hindering our ability to extract the coefficients of C𝒯d[Uncaptioned image]H(z). For instance, even in the simple case of a length-4 cycle, H=C4, in which case SC4(z)=2z212z2, Equation 3.2 takes the form

2z2c(z)3+10z2c(z)2+(14z21)c(z)+6z2=0,

where the term c(z) is a shorthand for C𝒯d[Uncaptioned image]C4(z), resulting in a complicated expression for c(z).

To address this challenge, we leverage a deep result from analytic combinatorics. We provide the essential background in the full version of the paper. Subsequently, in Section 3.1.3, we will outline our approach to estimating the coefficients of C𝒯d[Uncaptioned image]H(z) using Equation 3.2 as our starting point.

3.1.2 A brief introduction to analytic combinatorics

The symbolic method classifies combinatorial classes into schemes based on their shared structures. This approach aims to consolidate solutions to these problems and highlight their interrelations. A notable schema within this framework is termed smooth inverse-function schema. These are classes whose generating function ζ(z) satisfies the functional equation u=zϕ(u), namely, ζ(z)=zϕ(ζ(z)), for some “well-behaved” function ϕ(u). By manipulating Equation 3.2, we see that 𝒞𝒯d[Uncaptioned image]H is tightly connected to this schema. Indeed, letting ζH(z)=z(C𝒯d[Uncaptioned image]H(z)+1), we have that ζH(z)=zϕH(ζH(z)), where

ϕH(u)=1+(d1)SH(u). (3.3)

Analytic combinatorics provides a method to estimate the coefficients of the generating function for smooth inverse-function schema. This approach is applicable under certain technical conditions on ϕ(u), which we hide under the rug in this informal proof overview. The key requirement though is that there is a real positive solution to the characteristic equation ϕ(u)=uϕ(u) within ϕ-s analytic domain around the origin. To denote the k’th coefficient of a function we use the coefficient extractor operator, [zk]. For an analytic function A(z)=Akzk, we have

[zk]A(z)Ak

With this, we have the following theorem which is informally stated here (see the full version of the paper for the formal statement).

Theorem 7.

Let ζ(z) belong to the smooth inverse-function schema. Then, with τ the positive root of the corresponding characteristic equation ϕ(u)=uϕ(u), one has

([zk]ζ(z))1kϕ(τ). (3.4)

3.1.3 Proof sketch of Theorem 1

With Theorem 7 in hand, and by the discussion above that led us to Equation 3.3, we are ready to sketch the proof of Theorem 1. In fact, it will be more convenient to consider the variant using the Cauchy transform of H. Since 𝒞H=𝖲𝖤𝖰(𝒮H), we have that SH(z)=11CH(z). It can also be shown that CH(z)=1z𝒢H(1z) (see the full version of the paper for the proof), and so Equation 3.3 takes on the form

ϕH(z)=d(d1)z𝒢H(1z).

Through some algebraic manipulations, it becomes evident that the characteristic equation, ϕH(z)=zϕH(z), transforms into the form presented in Equation 2.5 from Theorem 2 when z is substituted with its reciprocal. Specifically, the equation becomes

dd1𝒢H(1z)2+𝒢H(1z)=0.

Upon further analytical exploration, it can be shown that this equation has a positive real root z0>d. Consequently, there exists a positive τ<1dR, where τ=1z0, that satisfies the characteristic equation. This allows us to apply Theorem 7 and derive the sought-after estimate

[zk]CH(z)1/kϕH(τ)=ϕH(τ)τ=dz0d1𝒢H(z0).

3.2 Matching the lower bound with 𝑯-local graphs

As briefly discussed in Section 2.2, the proof of Theorem 3 makes use of finite free probability. Thus, to start with, in Section 3.2.1 we give a brief account of this elegant theory. Then, in Section 3.2.2 we sketch the proof of Theorem 3.

3.2.1 Finite free probability

Free probability is a branch of mathematics, initiated by Voiculescu, that extends classical probability theory into the non-commutative setting. In classical probability, random variables are analyzed using their joint distribution, which encodes the correlations or lack of between them. In contrast, free probability introduces the abstract notion of “freeness” to represent the absence of correlations, appropriately defined, among non-commutative random variables. Free probability theory provides, in particular, tools to analyze the spectrum of the sum and product of two operators, given that these operators are free, using knowledge of their individual spectra. Freeness is an infinite-dimensional phenomena in the sense that a pair of finite-dimensional operators can only be free from one another if one of them is constant. As a result, operators associated with finite graphs cannot be studied directly by free probability theory.

In response to this limitation, Marcus, Spielman, and Srivastava, in their groundbreaking series of works [21, 22, 23], introduced the theory of finite free probability along with the associated technique of interlacing. This enabled them to extend some results of free probability to the finite-dimensional setting, especially regarding the spectra of matrix sums and products. While finite free probability may not capture all details of the latter spectra, it provides a one-sided bound on its support. Finite free probability does not depend on the abstract concept of freeness or any analogous notion. Rather, it demonstrates that conjugating a finite operator, 𝐀, with an orthogonal matrix – sampled according to the Haar measure on this group – effectively “frees” 𝐀 from other operators. We consider a specific application of this principle in the context of operator addition.

Definition 8 (Definition 2.4 in [22]).

Let 𝐀,𝐁 be d×d real symmetric matrices, with characteristic polynomials a(x) and b(x), respectively. The additive convolution of a(x) and b(x) is defined as

a(x)db(x)=𝐄𝐐χx(𝐀+𝐐𝐁𝐐𝖳), (3.5)

where the expectation is taken over random orthogonal matrices 𝐐 sampled according to the Haar measure on the group of n-dimensional orthogonal matrices.

We note that, while it may not be immediately apparent, the right-hand side of Equation 3.5 depends only on the spectra of 𝐀 and 𝐁. Consequently, the additive convolution is well-defined. It was also proved in [23] that a(x)db(x) is real-rooted itself, hence a discussion of bounding its roots is sensible. When d is clear from context, we omit the subscript d in d.

The analytic machinery that will allow us to study the additive convolution is the Cauchy transform and its max-inverse (see the full version for details). More precisely, the Cauchy transform of a real-rooted degree d polynomial p(t)[t], whose roots are λ1λ2λd, is defined as 𝒢p(x)=1di=1d1xλi. Clearly, for an undirected graph H, the Cauchy transform 𝒢H(x) as defined in Equation 2.4 can be expressed as 𝒢p(x) where p(t)=χt(H) is the characteristic polynomial of H.

Note that when the Cauchy transform of a polynomial p(t) is restricted to the domain to the right of its rightmost pole, (λ1,), its range is (0,). Additionally, 𝒢p(x) is monotonically decreasing within this domain. With this in mind, one can define 𝒦p:(0,)(λ1,) to be the inverse of 𝒢p(x) when restricted to the latter domain. In other words, 𝒦p is the max-inverse of 𝒢p. Particularly, for every y(0,), 𝒦p(y) provides an upper bound on the largest root, λ1, of p(t). The key feature of the 𝒦-transform is that it behaves very-well under additive convolution.

Theorem 9 (Theorem 1.12 in [23]).

For all d×d real symmetric matrices 𝐀,𝐁 with characteristic polynomials a(x),b(x), respectively, and for every y>0, it holds that

𝒦ab(y)𝒦a(y)+𝒦b(y)1y.

It is worth noting that in free probability, the analog statement to Theorem 9 in the infinite dimensional case holds with equality.

3.2.2 Proof sketch of Theorem 3

The main idea in proving Theorem 3 is to randomly construct an H-local graph in a very intuitive way: since we want each vertex v to appear in d instances of H, we place v in d such instances, choosing the neighbors uniformly at random. Formally, we define a matrix consisting of disjoint copies of H, and sum d random permutations of this matrix. This results in the matrix

X𝐏(H)=i=1d𝐏i𝐏i𝖳,

where 𝐏=𝐏1,,𝐏d are permutation matrices. The proof for the existence of an H-local graph whose second largest eigenvalue meet our lower bound incorporates two parts:

  1. 1.

    Bounding the second largest root of the expected characteristic polynomial, 𝐄𝐏χx(X𝐏(H)), where the permutations are sampled uniformly and independently at random.

  2. 2.

    Relating the roots of 𝐄𝐏χx(X𝐏(H)) to roots of a particular choice for 𝐏, resulting in finding a good permutation, which induces a graph.

On first sight, it is not clear how to relate the expectation polynomial from Part 1 with the aforementioned tools of finite free probability. Definition 8 uses an expectation over the Haar measure, and together with Theorem 9 (applied d1 times) enables us to establish an upper bound on the largest root of the expected characteristic polynomial, derived as the “free sum” of d of identical matrices. More precisely, a corollary from Theorem 9, together with the above discussion, yields

𝗆𝖺𝗑𝗋𝗈𝗈𝗍(χx(𝐀)d)minx>λ1(dxd1𝒢𝐀(x)), (3.6)

where λ1 is the largest eigenvalue of 𝐀. When taking 𝐀 to be the matrix , the RHS of Equation 3.6 resembles Equation 2.6 from Theorem 2. However, the relevance of the LHS of the above equation remains unclear, as the expectation hidden in the operation is over the Haar measure and not over permutations. For bridging this gap, as well as for establishing Part 2, we follow MSS and proceed in two steps: quadrature and interlacing. While our proof makes a black-box use of these techniques we believe that the unfamiliar reader will benefit from this short account.

Quadrature

Quadrature refers to a general technique by which an integral is written as a finite sum. In our context, we make use of the result showing that finite free additive convolution can be expressed using the finite subgroup of permutation matrices of the unitary group. Specifically,

Theorem 10 (Theorem 4.1 in [22]).

Let 𝐀,𝐁 be symmetric d×d matrices with 𝐀𝟏=a𝟏 and 𝐁𝟏=b𝟏. Let χx(𝐀)=(xa)a(x) and χx(𝐁)=(xb)b(x). Then,

𝐄𝐏χx(𝐀+𝐏𝐁𝐏𝖳)=(x(a+b))a(x)d1b(x),

where 𝐏 is a uniformly random permutation matrix.

Assume that 𝐀 is the adjacency matrix of a c-regular graph, and let p(x)=χx(𝐀)xc. As a direct corollary of Theorem 10, we get that

𝐄𝐏1,,𝐏dχx(i=1d𝐏i𝐀𝐏i𝖳)=(xdc)pd(x).

Consequently, by taking 𝐀=, the upper bound on the max-root of the convolution polynomial, derived using Equation 3.6, directly establishes a bound on the max-root of the expected characteristic polynomial appearing on the LHS. The advantage is that we are now considering an expectation over a finite distribution, and more importantly, each element in the support of the distribution is an H-local graph. The final step of interlacing permits us to conclude that an element exists within this distribution for which the same upper bound holds.

Interlacing

So far, we have discussed how to obtain a bound on the largest root of the expected characteristic polynomial (excluding the trivial root), where the expectation is over the group of permutation matrices. It is generally incorrect to assert that a bound on the largest root of the expectation of polynomials can be utilized to infer a bound on the largest root of one of the polynomials involved in the expectation. A key observation by MSS concerning this issue is that such an result holds if the polynomials participating in the expectation form an interlacing family. In fact, for any choice of k, this structure suffices to deduce a bound on the k-th largest root of at least one polynomial in the family, given that we are able to bound the k-th largest root of the expected characteristic polynomial.

4 Derandomized Squaring with Interesting Graphs

In this section we apply our results to some interesting graph families, starting with graphs which demonstrate the tightness of our lower bound (see Section 4.1). Our general bound on bounded-degree graphs is given in Section 4.2 and the stronger bound assuming good spectral expansion is given in Section 4.3. The complete bipartite graph is studied in Section 4.4. The remaining sections deal with Paley graphs (see Section 4.5) and, more generally, strongly regular graphs (see Section 4.6), as well as some specific interesting graphs in Section 4.7. Some of the proofs of the results are omitted and can be found in the full version of the paper.

4.1 Three tight examples

In this short section we analyze some basic choices for the graph H, for which we know what behavior to expect and compare against our bound. We prove that for these instances, our lower bound given by Theorem 2 is tight, up to an additive vanishing term, for every Ramanujan graph G.

4.1.1 The true square

Let G be a d-regular graph, where d3, and let Jd denote the complete graph on d vertices, self-loops included. That is, Jd is the graph whose adjacency matrix is the all-ones d×d matrix, typically denoted as 𝐉. Note that G[Uncaptioned image]Jd=G2. Our lower bound on λ(G[Uncaptioned image]Jd) obtained in Theorem 2 holds for all graphs G in the sense that ΛJd is independent of G. Therefore, it is sensible to expect that if the lower bound is tight for this choice of H=Jd then it is matched by taking G to be a d-regular Ramanujan graph. In such case, the spectral expansion λ(G[Uncaptioned image]Jd)=λ(G2) can be computed directly and is equal to λ(G)2=(2d1)2=4(d1). As we will now show, it is indeed the case that ΛJd=4(d1), establishing that our lower bound is tight for this choice of H.

The Cauchy transform of Jd is given by

𝒢Jd(x)=1d(d1x+1xd)=xd+1x(xd).

Substituting to Equation 2.5 and simplifying, we see that the derandomized squaring polynomial associated with Jd is given by ΔJd(x)=x2+(22d)x. The unique real positive root of ΔJd(x) is, of course x0=2d2. Substituting to Equation 2.6 yields ΛJd=4(d1).

4.1.2 Non-backtracking random walks

A second example for the tightness of our bound is given by the clique, denoted as Kd, namely the complete graph without self-loops. It is easily seen combinatorially that G[Uncaptioned image]Kd corresponds to the graph of non-backtracking length-2 walks in G, which we denote by G(2). The corresponding adjacency matrix is given by 𝐀(2)=𝐀2d𝐈. Hence, for a Ramanujan graph G, the best value we can hope for coming from the analysis is

λ(𝐀(2))=λ(𝐀2)d=4(d1)d=3d4.

This bound is indeed what results from our analysis. To see this, note that the Cauchy transform of Kd is

𝒢Kd(x)=1d(d1x+1+1xd+1)=xd+2(x+1)(xd+1).

Substituting to Equation 2.5 and simplifying, we see that the derandomized squaring polynomial associated with Kd is given by

ΔKd(x)=x2+(42d)x+32d.

The unique real positive root of ΔKd(x) is x0=2d3. Substituting to Equation 2.6 yields the desired bound, ΛKd=3d4.

It is instructive to compare our bound with the upper bound obtained by the Rozenman-Vadhan bound, Equation 1.1 for a Ramanujan graph G. The second largest (normalized) eigenvalue of Kd in absolute value is 1d1, leading to an overall bound of 5d compared to the true behavior of 3d.

4.1.3 The graph achieving the Rozenman-Vadhan bound

In [35], Rozenman and Vadhan proved that the bound that is given in Equation 1.1 is tight in a strong sense, namely, for every rational μ, there exists a graph RVμ with ω(RVμ)=μ, such that for every graph G it holds that ω(G[Uncaptioned image]RVμ)=(1μ)ω(G2)+μ. For ease of notation, we write RV instead of RVμ from hereon. The graph RV is constructed as follows: assume μ=sr for some integers r,s1, then RV is a graph on d vertices which is rd-regular, consisting of rs copies of the complete graph Jd, and additional sd self-loops on each vertex. The combinatorial analysis shows that a step in the rd2-regular graph G[Uncaptioned image]RV amounts to staying at the same vertex with probability μ or taking a step in G2 with probability 1μ, leading directly to the tightness of the bound.

Assume once again that G is Ramanujan, hence λ(G)2d1. In this case, by Equation 1.1, we get that

λ(G𝗌RV) =ω(G𝗌RV)rd2
=((1sr)4(d1)d2+sr)rd2
=4(d1)r+(d2)2s.

As in the above two examples, we use the Cauchy transform of RV which is given by

𝒢RV(x)=1d(d1xsd+1xrd)=x(d1)rs(xdr)(xds).

Expanding Equation 2.7 and solving, we get

ΛRV=ψRV(x0)=4(d1)r+(d2)2s,

as in the Rozenman-Vadhan bound.

4.2 Bounded-degree graphs and a universal bound on 𝜿

In this section we prove that derandomized squaring with a simple vertex-transitive graph of bounded degree results with a graph that gravitates towards Ramanujan as the number of vertices in H increases. Moreover, we establish a universal bound on κH which holds for all simple vertex-transitive graphs.

Theorem 11.

Let H be a simple vertex-transitive c-regular graph on d vertices, where d3 and c1. Then,

κH2+cdc.

Moreover, for every d11 it holds that κH3. Lastly, if H is triangle-free then

κH2+cd11cd.

4.3 Spectral expanders

In this section we prove a stronger bound on κH than the one obtained in Theorem 11, which recall holds for general bounded-degree graphs, assuming that H is a good spectral expander. The proof follows the same argument as in the proof of Theorem 11 though takes into account the bound on the spectral expansion.

Proposition 12.

Let H be a simple vertex-transitive c-regular graph on d vertices. Assume that 10c<d. Then,

κH2+3d(λ(H)c)3.

Furthermore, if H is triangle-free then

κH2+4d(λ(H)c)4.

4.4 Complete bipartite graphs

In this section we consider the operation of derandomized squaring with the complete bipartite graph on d vertices, for an even integer d4. This is, of course, a c=d2 regular graph which we denote as Kc,c. It is easy to see that Kc,c has eigenvalues ±c, each with multiplicity 1, and the remaining eigenvalues are all 0. Therefore, the corresponding Cauchy transform, which for ease of notation we denote by 𝒢c,c, is given by

𝒢c,c(x)=4x2d(d2)(4x2d2)x.

From here one can compute the derandomized squaring polynomial

Δc,c(x)=x4d(2d3)2x2(d2)d316

whose unique positive root x0=md2, where m=2d3+(d1)(5d9). One can verify that 𝒢(x0)=md+2x0(md). Substituting this to Equation 2.6, we get

ΛKc,c=x0(m+dmd+2)=md2(m+dmd+2).

The resulted graph is D=d22-regular, and so we normalize by dividing by D1 to get

κKc,c=md2d24(m+dmd+2).

From here one can compute the first couple of values, κK2,22.089 which, of course, matches the bound we computed for the length-4 cycle, and κK3,32.157. Considering the limit behavior as d we have that mγd where γ=2+5, and so

κK,limcκKc,c=γ2γ+1γ1=1211+552.355.

4.5 Paley graphs

Let q=4r+1 be a prime power. The Paley graph, denoted as Palq, has vertex set corresponding to the finite field 𝔽q with the vertices adjacent if and only if their difference is a nonzero square in 𝔽q. As q1 modulo 4, we have that 1 is a square in 𝔽q, and so Palq is undirected.

Theorem 13.
κPallimqκPalq=1+13+16282.464.

4.6 Strongly regular graphs

A c-regular graph on d vertices with no self-loops is called strongly regular with parameters λ,μ 444It is customary to denote these parameters by λ and μ and so, despite our use of λ for denoting the spectral expansion, we proceed with this standard notation. if 0<c<d (namely, the graph is neither complete nor edgeless) and the following hold:

  1. 1.

    For each pair of adjacent vertices there are λ vertices adjacent to both.

  2. 2.

    For each pair of nonadjacent vertices there are μ vertices adjacent to both.

Strongly regular graphs include dozens of interesting graphs such as the Peterson graph, the Hoffman-Singelton graph (see Section 4.7), and the symplectic graphs (see Section 4.6.1), as well as all Paley graphs which we analyzed in Section 4.5. It is a well-known fact that strongly regular graphs have two eigenvalues other than the trivial eigenvalue c, denoted r,s, with the convention r>s. This is, in fact, a spectral characterization of strongly regular graph among regular graphs. The multiplicity of these eigenvalues are denoted by f,g, respectively. In the following we compute the derandomized squaring polynomial of a strongly regular graph.

Proposition 14.

Let H be a c-regular strongly regular graph on d3 vertices with parameters λ,μ. Let α=λμ and e=cd+1. Then, the derandomized squaring polynomial associated with H is given by

ΔH(x)=x42(α+c)x3+Ax2+Bx+C,

where

A =2μ+4αc+α2+ce,
B =2αμ+2c(cceα2μ),
C =(μc)(μ+2αc+c)+c3e.

4.6.1 The symplectic graphs

An interesting sub-family of strongly regular graphs are the so-called symplectic graphs. Let r1 be an integer. The symplectic graph Sp(2r) is the graph whose vertex set consists of all nonzero vectors in 𝔽22r. Two vertices x,y are adjacent whenever x𝖳𝐍y=1, with all calculations over 𝔽2, where 𝐍 is the (2r)×(2r) block diagonal matrix with r blocks of the form (0110). It is well-known that Sp(2r) is a strongly regular graph with λ=μ=22r2.

Theorem 15.
limrκ(Sp(2r))=1+13+16282.464.

Interestingly, though not unexpectedly, this limit behavior is also shared by Paley graphs (see Section 4.5).

4.7 Some specific graphs

In this section we consider some specific interesting graphs.

Table 1: Summary of specific graphs and their derandomized squaring constants.
H (Graph name) d (Number of vertices) c (degree) κH
Petersen graph 10 3 2.025
Heawood graph 14 3 2.004
Hoffman-Singelton graph 50 7 2.007
Biggs-Smith graph 102 3 2.000000016
Conway’s 99-graph 99 14 2.041

References

  • [1] AmirMahdi Ahmadinejad, Jonathan Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil Vadhan. High-precision estimation of random walks in small space. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 1295–1306. IEEE Computer Soc., Los Alamitos, CA, [2020] ©2020. doi:10.1109/FOCS46700.2020.00123.
  • [2] AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, and Salil Vadhan. Singular value approximation and reducing directed to undirected graph sparsification. arXiv preprint arXiv:2301.13541, 2023. doi:10.48550/arXiv.2301.13541.
  • [3] N. Alon and F. R. K. Chung. Explicit construction of linear sized tolerant networks. In Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), volume 72, pages 15–19, 1988. doi:10.1016/0012-365X(88)90189-6.
  • [4] Noga Alon. Eigenvalues and expanders. Combinatorica, 6(2):83–96, 1986. doi:10.1007/BF02579166.
  • [5] Avraham Ben-Aroya and Amnon Ta-Shma. A combinatorial construction of almost-Ramanujan graphs using the zig-zag product. SIAM J. Comput., 40(2):267–290, 2011. doi:10.1137/080732651.
  • [6] Yonatan Bilu and Nathan Linial. Lifts, discrepancy and nearly optimal spectral gap. Combinatorica, 26(5):495–519, 2006. doi:10.1007/s00493-006-0029-7.
  • [7] Charles Bordenave. A new proof of Friedman’s second eigenvalue theorem and its extension to random lifts. Ann. Sci. Éc. Norm. Supér. (4), 53(6):1393–1439, 2020. doi:10.24033/asens.2450.
  • [8] Charles Bordenave and Benoît Collins. Eigenvalues of random lifts and polynomials of random permutation matrices. Annals of Mathematics, 190(3):811–875, 2019.
  • [9] Mark Braverman, Gil Cohen, and Sumegha Garg. Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs. SIAM Journal on Computing, 49(5):STOC18–242, 2019. doi:10.1137/18M1197734.
  • [10] Eshan Chattopadhyay and Jyun-Jie Liao. Optimal error pseudodistributions for read-once branching programs. In 35th Computational Complexity Conference, volume 169 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 25, 27. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020. doi:10.4230/LIPICS.CCC.2020.25.
  • [11] Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, and Hongxun Wu. Weighted pseudorandom generators via inverse analysis of random walks and shortcutting. In Electronic Colloquium on Computational Complexity (ECCC), volume 114, 2023.
  • [12] Gil Cohen and Gal Maor. Random walks on rotating expanders. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 971–984, 2023. doi:10.1145/3564246.3585133.
  • [13] Michael B. Cohen. Ramanujan graphs in polynomial time. In 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, pages 276–281. IEEE Computer Soc., Los Alamitos, CA, 2016. doi:10.1109/FOCS.2016.37.
  • [14] Joel Friedman. A proof of Alon’s second eigenvalue conjecture and related problems. Mem. Amer. Math. Soc., 195(910):viii+100, 2008. doi:10.1090/memo/0910.
  • [15] Rostislav I Grigorchuk and Andrzej Zuk. On the asymptotic spectrum of random walks on infinite families of graphs. Random walks and discrete potential theory (Cortona, 1997), pages 188–204, 1999.
  • [16] Chris Hall, Doron Puder, and William F. Sawin. Ramanujan coverings of graphs. Adv. Math., 323:367–410, 2018. doi:10.1016/j.aim.2017.10.042.
  • [17] Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439–561, 2006.
  • [18] Yasutaka Ihara. On discrete subgroups of the two by two projective linear group over p-adic fields. J. Math. Soc. Japan, 18:219–235, 1966. doi:10.2969/jmsj/01830219.
  • [19] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. doi:10.1007/BF02126799.
  • [20] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families I: Bipartite Ramanujan graphs of all degrees. Ann. of Math. (2), 182(1):307–325, 2015. doi:10.4007/annals.2015.182.1.7.
  • [21] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem. Ann. of Math. (2), 182(1):327–350, 2015. doi:10.4007/annals.2015.182.1.8.
  • [22] Adam W Marcus, Daniel A Spielman, and Nikhil Srivastava. Interlacing families IV: Bipartite Ramanujan graphs of all sizes. SIAM Journal on Computing, 47(6):2488–2509, 2018. doi:10.1137/16M106176X.
  • [23] Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Finite free convolutions of polynomials. Probab. Theory Related Fields, 182(3-4):807–848, 2022. doi:10.1007/s00440-021-01105-w.
  • [24] Grigorii Aleksandrovich Margulis. Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators. Problemy peredachi informatsii, 24(1):51–60, 1988.
  • [25] Sidhanth Mohanty and Ryan O’Donnell. X-Ramanujan graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 1226–1243. SIAM, Philadelphia, PA, 2020. doi:10.1137/1.9781611975994.75.
  • [26] Sidhanth Mohanty, Ryan O’Donnell, and Pedro Paredes. Explicit near-Ramanujan graphs of every degree. SIAM J. Comput., 51(3):1–23, 2022. doi:10.1137/20M1342112.
  • [27] Moshe Morgenstern. Existence and explicit constructions of q+1 regular Ramanujan graphs for every prime power q. J. Combin. Theory Ser. B, 62(1):44–62, 1994. doi:10.1006/jctb.1994.1054.
  • [28] Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan. Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space. SIAM J. Comput., 50(6):1892–1922, 2021. doi:10.1137/20M134109X.
  • [29] Alexandru Nica and Roland Speicher. Lectures on the combinatorics of free probability, volume 335 of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2006. doi:10.1017/CBO9780511735127.
  • [30] A. Nilli. On the second eigenvalue of a graph. Discrete Math., 91(2):207–210, 1991. doi:10.1016/0012-365X(91)90112-F.
  • [31] Ryan O’Donnell and Xinyu Wu. Explicit near-fully X-Ramanujan graphs. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pages 1045–1056. IEEE Computer Soc., Los Alamitos, CA, 2020.
  • [32] Karol A Penson and Karol Życzkowski. Product of ginibre matrices: Fuss-Catalan and Raney distributions. Physical Review E, 83(6):061118, 2011.
  • [33] Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):Art. 17, 24, 2008. doi:10.1145/1391289.1391291.
  • [34] Omer Reingold, Salil Vadhan, and Avi Wigderson. Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3–13. IEEE, 2000. doi:10.1109/SFCS.2000.892006.
  • [35] Eyal Rozenman and Salil Vadhan. Derandomized squaring of graphs. In Approximation, randomization and combinatorial optimization, volume 3624 of Lecture Notes in Comput. Sci., pages 436–447. Springer, Berlin, 2005. doi:10.1007/11538462_37.
  • [36] Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 238–251, 2017. doi:10.1145/3055399.3055408.
  • [37] Wolfgang Woess. Random walks on infinite graphs and groups, volume 138 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2000. doi:10.1017/CBO9780511470967.