{'fraction_non_alphanumeric': 0.0674373795761079, 'fraction_numerical': 0.008945774841728598, 'mean_word_length': 3.619516846789574, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Properties of the Generalized Zig-Zag Product of Graphs

The operation of zig-zag products of graphs is the analogue of the semidirect product of groups. Using this observation, we present a categorical description of zig-zag products in order to generalize the construction for the category of simple graphs. Also, we examine the covering properties of zig-zag products and we utilize these results to estimate their spectral invariants in general. In addition, we provide specific spectral analysis for some such products.


Introduction
Expander graphs have very strong connectivity properties. For this reason, they play a very important role in computer science, network design, cryptography, just to mention a few of their applications. Originally, techniques from number theory provided the only known methods for constructing expanders. ( [7]). Zig-zag products of graphs were introduced as a combinatorial way of constructing infinite sequences of expanders ( [2], [8], [9]). We begin by extending zig-zag products to the whole category of simple graphs (not necessarily finite). We continue by showing that the spectral analysis of these graphs is greatly simplified by the structure of the zig-zag product for both finite and infinite graphs.
Zig-zag products were introduced as the graph-theoretic analogues of semidirect products of groups. That means that, with the right choice of generating sets, the Cayley graph of a semidirect product of groups is the zig-zag product of the Cayley graphs of those groups. In the first part of the paper we exploit this connection to give a categorical description of zig-zag products. That allows us to generalize the zig-zag construction for any graphs, finite or infinite, regular or not. In general, we construct the zig-zag product G z H when G is H-labeled i.e., equipped with a function where (u, e) ∈ D(G) means that e is an edge in G with one end-point u.
We begin by considering locally constant labelings and derive some specific information about the spectrum of the resulting zig-zag product. Namely, the non-trivial eigenfunctions of the adjacency operator correspond bijectively between G and G z H with eigenvalues scaled only by a fixed constant.
Kesten's Theorem ( [5], [6]) implies that, for a k-regular graph with ρ(G) maximum if and only if G is amenable and minimum if and only if G is the k-regular tree. In particular, using Kesten's Theorem, that if G is amenable so is G z H. In this case, we construct a Følner sequence for G z H from a Følner sequence of G.
Covers can be used to estimate the spectra of graphs. First we show that graph covers and combinatorial covers are preserved under generalized zig-zag products. Also, we show that for locally constant H-labelings of G the zig-zag product G z H is itself a combinatorial cover of G.
Combining these results, we construct an infinite sequence of combinatorial covers for any simple graph G.
Whereπ n+1 : D(∆ n+1 ) → D(∆ n ) is the map induced by the graph epimorphism, Then π n+1 is a combinatorial covering map for n ≥ 0. In fact, the spectrum of ∆ n is just the spectrum of ∆ n−1 scaled by a constant m, fixed for all n.
By applying the results of the previous section, we extend the result that eigenfunctions with non-zero eigenvalues correspond bijectively between ∆ n and ∆ n−1 . As a consequence of this, given a graph exhibiting a spectral gap, it is possible to construct an infinite sequence of graphs of increasing complexity that also exhibit a spectral gap and, in fact, the length of the spectral gap is scaled by a fixed natural number for each term in the sequence, allowing for an arbitrarily large spectral gap.
The first two authors would like to thank Terry Bisson for his helpful and insightfull suggestions. They would like also to thank Canisius College for the hospitality during the R.E.U. program in Summer 2006.

Definitions and Notation
All graphs will be simple locally finite graphs. Let G be a simple graph i.e., a graph without multiple edges and loops. Let V (G) denote the vertex set of G and E(G) the edge set. For two adjacent vertices u and v in G, (denoted u ∼ G v) we write {u, v} for the edge between u and v, and E G (u) for the set of edges adjacent to u. Also, we denote the neighborhood of a vertex u ∈ V (G) by Given two graphs, G and G ′ , we call the map φ : A graph morphism φ as above induces a map: Let f, g : A → G be two maps from a set A to a graph G. Then f and g are called adjacent if f (a) ∼ G g(a) for all a ∈ A.
Let H be a graph. An H-labeling on a graph G is a function The pair (G, α) is called an H-labeled graph.
Definition 2.1. Let (G, α) be an H-labeled graph, with H non-trivial. The zig-zag product G z H is the graph defined as follows: (1) We do not assume that G and H are finite graph as in the classical definitions of zig-zag products ( [2], [8], [9]). It is clear that if G and H are locally finite, then so is G z H. (2) We do not require the graphs involved to be regular. The disadvantage is that G z H is not necessarily regular. (3) The definition given above also generalizes the classical definitions in a different direction.
In the zig-zag products given in [8] and [9] the maps α(u, −) are assumed to be bijections, for each u ∈ V (G) and in [2] the maps α(u, −) are assumed to be injections whose image has k elements, where k | |V (G)|.
(1) In the usual definition of the zig-zag product, V (G z H) was taken to be V (G)×V (H). Our definition modifies this convention to avoid the presence of isolated vertices in G z H.
(2) There always exists a graph epimorphism, We begin with some helpful preliminaries regarding the structure of the zig-zag product.

Lemma 2.4. Let G and H be locally finite simple graphs with α an H-labeling of G. Then for
Lemma 2.5. Let G be a finite graph, H a locally finite graph, and α an H-labeling of G. Then We now define a labeling that we will find particularly useful.
Definition 2.6. Let G and H be locally finite simple graphs. Then α : , for all v and w adjacent to u. Lemma 2.7. Let G be a finite graph, H be locally finite graph and let α be a locally constant H-labeling such that for all h ∈ Im(α), val(h) = k. Then G z H contains at least k |V (G)| subgraphs isomorphic to G.
There are k such choices for each u. Let G ′ be the subgraph spanned by the chosen vertices. Note that (u, i) ∼ (v, j) ⇔ v ∼ G u. Thus, since a bijection exists between G ′ and G, they are isomorphic. Note that there exists k |V (G)| choices for the construction of G ′ .

Categories of H-labeled Graphs
We will give a categorical description of the zig-zag product. We define two categories of Hlabeled graphs. In one the morphism are commutative diagrams "up to adjacency" and in the other the diagrams strictly commute.
We write L w (H) for the weak category of H-labeled graphs: • Objects are H-labeled graphs (G, α).
We also write L s (H) for the strict category of H-labeled graphs, with the same objects but morphisms maps such that the following diagram commutes: There is a forgetful functor: We now describe the dependence of the zig-zag product on the second variable. (1) The morphism ψ induces a functor: (2) Assume that ψ is onto on the set of vertices and satisfies: Then ψ induces a functor Proof. If (G, α) is an H 1 -labeled graph, then (G, ψ•α) is an H 2 -labeled graph. Part (1) follows immediately. For Part (2) and for a morphism in L w (H 1 ), notice that: We now describe the dependence of the zig-zag product on the second variable. Again, we have two different descriptions, one for each category. Let C s be a category with is a pair of morphisms: Similarly, we define C w to be the category with the same set of objects as C s and morphisms pairs (φ, ψ) as above where φ is a morphism in L w (H 1 ) and ψ satisfies Condition (2) in Lemma 3.1.
If a pair (φ, ψ) is a morphism in C s or C w . Define Also, F induces a map: Proposition 3.2. The pair induces a graph map: Proof. It follows from the definitions.
Thus combining the categorical properties of the construction, we will find conditions that determine when zig-zag products are isomorphic. Theorem 3.3. Let φ : G 1 → G 2 and ψ : H 1 → H 2 be graph isomorphisms. Also, assume that Proof. The conditions imposed guarantee that there is a natural inverse graph map to F . The next result is another graph theoretic analogue of the semidirect product construction on groups. Let (G, α) be an H-labeled graph, and Z a graph equipped with an graph map f : Z → G. Then f induces a map The following follows from the definitions.
and, for z ∼ Z w,

Spectral Analysis of Zig-Zag Products
For a graph G, the adjacency matrix of G is the matrix A with rows and columns indexed by the vertex set of G such that  Proof. Letf ∈ L 2 (G z H) be defined asf (u, i) = f (u), for all (u, i) ∈ V (G z H). Notice that for each u ∈ V (G), We claim thatf is the desired eigenvector. First we show thatf ∈ L 2 (G z H). This is true because In particular, Now, since f is an eigenvector of A G , we know that for all u ∈ V (G). But this implies by Lemma 2.4 that for all (u, i) ∈ V (G z α H)). Proof. From the definition of the zig-zag product we can see that the last equality holds since α is locally constant. Thus, and sincef is an eigenvector, Thus, if λ is not equal to 0, thenf (u, i) =f (u, k).
Thus we see thatf (u, i) depends only on u. Now, define f ∈ L 2 (G) by the formula So, for any j ∈ V (H), this last sum is equal to The normalized adjacency matrix P = (1/d)A G of a d-regular graph G can be considered as an operator on L 2 (V (G)). Then the spectral radius of G is given by For a d-regular graph, Proof. Let f ∈ L 2 (G). Then f induces an elementf ∈ L 2 (G z H) bŷ It is obvious thatf ∈ L 2 (G z H). Then where − z denotes the norm in L 2 (G z H).
Let v ∈ V (G) and u ∈ N (v). Let α(u, |{u, v}) = i and α(v, |{u, v}) = j. Then (v, m) ∼ (u, n) in G z H if and only if m ∼ i and n ∼ j. Since H is d-regular, there are d 2 such pairs. If Q denotes the normalized adjacency matrix in G z H, then, if −, − z denote the inner product in L 2 (G z H), Using this calculation, we get Theorem 4.4 and Kesten's Theorem imply that the zig-zag product G z H of graphs that satisfy the assumptions of Theorem 4.4 with G amenable, is amenable.
If G has enough symmetries then ( [4], [5], [6], [10]) and equality on the left was obtained if and only if G is a d-regular tree and on the right if and only if G is amenable. We recall the definition of amenability that we will use: Definition 4.5. A graph G is amenable if there is a sequence of finite subgraphs {F n } ∞ n=1 whose union is G such that lim n→∞ |∂F n | |F n | = 0.
Here, for a subgraph H of G, ∂H = {e ∈ E(G) : one endpoint of e is in H and the other it is not}.
The sequence {F n } ∞ n=1 is called a Følner Sequence.
For an H-labeled graph (G, α), let F be a subgraph of G. Then the restriction of α induces an H-labeling on F . Using this observation we can construct Følner Sequences in the zig-zag products. Proof. First notice that for each n, |F n z H| = |F n |×|H|. Let D be the maximum degree in H. The definition of the zig-zag product implies that: Thus, taking limits, lim n→∞ |∂(F n z H)| |F n z H| = 0.

Covers of Zig-Zag Product
Despite the heavily relaxed conditions in our generalized definition of the zig-zag product, we retain some of the combinatorial properties of the original graphs.
First we show that zig-zag products preserve graph coverings.
Definition 5.1. For two graphs, G,G, a map p :G → G is said to be a graph covering map if: In this caseG is said to cover, or be a graph covering of G.
is a covering map.
Proof. The covering p induces a map, Since {p(x), p(y)} ∈ E(G),p induces an H-labeling ofG by β = α •p. Then p is a morphism in L s (H) and induces a graph map (Proposition 3.2) Also, since v ∼ G p(x) and p is a graph covering map, there exists a unique y ∈ p −1 (v) such that y ∼G x. Clearlyp(y, j) = (v, j). But, using (*), Similarly, by (*) again, β(y, {x, y}) ∼ H j. Thus (x, i) ∼ (y, j) inG z β H. That shows that the map is onto. The uniqueness of the choice for y shows thatp| N (x,i) is injective. Sop| N (x,i) is a bijection.
Corollary 5.4. IfG is a graph covering of an H-labeled graph G, with the notation of Theorem Chung and Yau ( [3]) introduced a variant to graph coverings. We will show that zig-zag products preserve combinatorial coverings.
Definition 5.5. For two graphs, G,G, a map π :G → G is said to be a combinatorial covering map if: (1) There is m ∈ R + ∪ {∞} such that for every {u, v} ∈ E(G), |{{x, y} ∈ E(G) : π(x) = u, π(y) = v}| = m (2) For x, y ∈ V (G) with π(x) = π(y), and v ∼ G π(x), we have, Definition 5.6. For a finite graph G, define the normalized Laplacian, Theorem 5.7. Let G,G, H be graphs with α be an H-labeling of G. Let p :G → G be a combinatorial covering map. Then there exists an H-labeling β ofG such that the induced map is a combinatorial covering map, Proof. As in the proof of Theorem 5.3, p induces a labeling β onG and a graph morphism . Then, as in the proof of Theorem 5.3, The last relation is satisfied because (u, i) ∼ G z α H (v, j). Similarly, Thus, If y ∈ N (x)∩p −1 (u) then p(y) = u and y ∼G x. Then Thus (y, j) is adjacent to (x, i) inG z β H and (y, j) ∈ N (x, i). Also,p(y, j) = (p(y), j) = (u, j), which implies (y, j) ∈ N (x, i)∩p −1 (u, j).
Thus there is a map But notice that So ξ is a bijection and the two sets have the same cardinality.
In [3], Lemma 1, the connection between the spectra of graphs in combinatorial covers is given. Applying this observation, we get the following consequence of Theorem 5.7.
Corollary 5.8. LetG, G and H be finite graphs. LetG be a combinatorial cover of an H-labeled graph G. With the notation of Theorem 5.7, each of the eigenvalues of the normalized Laplacian of G z α H are eigenvalues of the normalized Laplacian ofG z β H. In particular, if both G z α H and G z β H are regular, spec(G z α H) ⊂ spec(G z β H).
Combinatorial graphs arise naturally in zig-zag products.
Theorem 5.9. Let G be a locally constant H-labeled graph. Assume that the H-labeling α is such that for all h ∈ Im(α), val(h) = n. Then π : G z H → G, (u, i) → u is a combinatorial covering map.
Then π n+1 is a combinatorial covering map for n ≥ 0.
Combining Corollary 5.10 with the result in Corollary 5.8 we get: Corollary 5.11. For a finite graph G and H-labeling satisfying the conditions of Corollary 5.10, the spectrum of the normalized Laplacian for ∆ n is contained in the spectrum of the normalized Laplacian of ∆ m for all m ≥ n.