Expanders and right-angled Artin groups

2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Journal of Topology and Analysis (2021) c World Scientific Publishing Company DOI: 10.1142/S179352532150059X Expanders and right-angled Artin groups Ram´on Flores Department of Geometry and Topology University of Seville, Spain [email protected] Delaram Kahrobaei Department of Computer Science, Queens College CUNY, Queens, NY, United States of America Department of Mathematics, Queens College CUNY, Queens, NY, United States of America New York University, Tandon School of Engineering PhD Program in Computer Science CUNY Graduate Center, United States of America Department of Computer Science University of York, United Kingdom [email protected]; [email protected] Thomas Koberda∗ Department of Mathematics, University of Virginia Charlottesville, VA 22904, United States of America [email protected] Received 30 June 2021 Accepted 7 October 2021 Published 13 November 2021 The purpose of this paper is to give a characterization of families of expander graphs via right-angled Artin groups. We prove that a sequence of simplicial graphs {Γi}i∈N forms a family of expander graphs if and only if a certain natural mini-max invariant arising from the cup product in the cohomology rings of the groups {A(Γi)}i∈Nagrees with the Cheeger constant of the sequence of graphs, thus allowing us to characterize expander graphs via cohomology. This result is proved in the more general framework of vector space expanders, a novel structure consisting of sequences of vector spaces equipped with vector-space-valued bilinear pairings which satisfy a certain mini-max condition. These objects can be considered to be analogues of expander graphs in the realm of linear algebra, with a dictionary being given by the cup product in cohomology, ∗Corresponding author. 1 J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 2R. Flores, D. Kahrobaei & T. Koberda and in this context represent a different approach to expanders that those developed by Lubotzky–Zelmanov and Bourgain–Yehudayoff. Keywords: Right-angled Artin groups; expander graphs; Cheeger constant; cohomology algebra. Mathematics Subject Classification: 20F36, 05C48, 05C50, 20J06 1. Introduction Expander graphs, which are infinite sequences of graphs of bounded valence which are uniformly difficult to disconnect, are of fundamental importance in discrete mathematics, graph theory, knot theory, network theory, and statistical mechanics, and have a host of applications in computer science including to probabilistic computation, data organization, computational flow, amplification of hardness, and construction of hash functions [6, 13, 16]. Many constructions of graph expander families are now known, though originally explicit constructions were few despite the fact that their existence is relatively easy to prove through probabilistic methods (see [1, 23, 26] for discussions of both explicit and probabilistic constructions). In this paper, we provide a new perspective on graph expander families that relates them to fundamental objects in geometric group theory, and which allows them to be probed in a novel way through linear algebraic methods. In particular, we characterize families of expander graphs through their associated right-angled Artin groups, and in the process, define the notion of vector space expander families. Recall that a simplicial graph (sometimes known in the literature as a simple graph) is an undirected graph with no double edges between any pair of vertices and with no edges whose source and target coincide. If Γ is a finite simplicial graph with vertex set Vert(Γ) and edge set Edge(Γ), we define the right-angled Artin group on Γby A(Γ) = Vert(Γ) |[vi,v j] = 1 if and only if {vi,v j}∈Edge(Γ). It is well known that the isomorphism type of a finite simplicial graph is uniquely determined by the corresponding right-angled Artin group, and thus all the combinatorial properties one may assign to Γ should be reflected in the intrinsic algebra of A(Γ) [10, 21, 22, 28]. If A(Γ) is given via a presentation as above (as opposed to as an abstract group), then there is a trivial way to pass between the graph Γ and elements of the group A(Γ). Indeed, the vertices of Γ are then identified with the generators in the presentation, and the adjacency relation in Γ is exactly the commutation relation among generators of A(Γ). The problem with this perspective is that a choice of generators of A(Γ) is not canonical. For instance, it is possible to find a generating set of A(Γ) that such that commutation relations between generators have nothing to do with the combinatorics of Γ. The point of this paper is to translate between the combinatorics of Γ and the algebraic structure of A(Γ) in a way that is intrinsic to A(Γ). Specifically, we wish to characterize graph expander families in a canonical J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 3 algebraic way, and in particular without any reference to specific generators of the right-angled Artin group. Some examples of this principle are as follows: (1) A(Γ) decomposes as a nontrivial direct product if and only if Γ is a nontrivial join [29]. (2) A(Γ) decomposes as a nontrivial free product if and only if Γ is disconnnected [4, 21]. (3) A(Γ) contains a subgroup isomorphic to a product F2×F2of nonabelian free groups if and only if Γ has a full subgraph which is isomorphic to a square [18, 19]. (4) The poly-free length of A(Γ) is two if and only if Γ admits an independent set Dof vertices such that every cycle in Γ meets Dat least twice [15]. (5) A(Γ) is obtained from infinite cyclic groups through iterated free products and direct products if and only if Γ contains no full subgraph which is isomorphic to a path of length three [19, 20]. (6) A(Γ) is a semidirect product of two free groups of finite rank if and only if Γ is a finite tree or a finite complete bipartite graph [15]. (7) There is a finite nonabelian group acting faithfully on A(Γ) by outer automorphisms if and only if Γ admits a nontrivial automorphism [11]. (8) A graph Γ with nvertices is k-colorable if and only if there is a surjective map A(Γ) → k  i=1 Fi, where for 1 ≤i≤kthe group Fiis a free group of rank mi,andwhere k i=1 mi=n[12]. In this paper, we develop this dictionary by characterizing graph expander families through the intrinsic algebra of right-angled Artin groups. Recall that a family {Γi}i∈Nof finite graphs is called a graph expander family if the number of vertices in Γitends to infinity as itends to infinity, if the valence of each vertex of Γiis bounded independently of i, and if a certain isoperimetric invariant called the Cheeger constant (or expansion constant)ofeachΓ iis uniformly bounded away from zero. We refer the reader to Sec. 2 for precise definitions. We remark that in general, graph expander families are not assumed to consist of simplicial graphs, though for the purposes of the algebraic dictionary we develop here, we will retain a blanket assumption that all graphs under consideration are simplicial unless explicitly noted otherwise. The main result of this paper is to give an intrinsic algebraic characterization of graph expander families via right-angled Artin groups, without any reference to distinguished generating sets. In order to achieve this, one must define a certain analogue hVof the Cheeger constant that can be described from the data of the right-angled Artin group. This constant is constructed in terms of the triple {(H1(A(Γ),L),H2(A(Γ),L),)}, J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 4R. Flores, D. Kahrobaei & T. Koberda where Hi(A(Γ),L)istheith cohomology group of A(Γ) with coefficients in a field L,andthe cup product restricted to H1(A(Γ),L) (see 2.2.1). The following result, which is a central pillar of this paper, establishes the link between the two versions of the Cheeger constant: Proposition 1.1. (cf. Theorem 4.1) Let Γbe a finite simplicial graph,let hΓdenote the Cheeger constant of Γ,andlethVdenote the Cheeger constant of the triple {(H1(A(Γ),L),H2(A(Γ),L),)}. Then hΓ=hV. Proposition 1.1 is the key in establishing a group-theoretic description of expander graphs. Our main result is therefore as follows: Theorem 1.2. Let {Γi}i∈Nbe a family of finite simplicial graphs,let {A(Γi)}i∈N denote the corresponding family of right-angled Artin groups,and let Lbe an arbitrary field. Then {Γi}i∈Nis a graph expander family if and only if: (1) The rank (i.e. size of the smallest generating set)of A(Γi)tends to infinity as itends to infinity. (2) The rank of the centralizer of each nontrivial element of A(Γi)is bounded independently of i. (3) The Cheeger constant of the family {(H1(A(Γi),L),H2(A(Γi),L),)}i∈N, is bounded away from zero. This result is proved in the more general framework of vector space expanders (with a precise definition in Sec. 2.2). This is a certain sequence of triples {(Vi,W i,q i)}i∈N, each of which is defined over a fixed field L,whereeachViis a finite-dimensional vector space such that dim Vi→∞as i→∞.EachWiis an L-vector space, and qiis a symmetric or anti-symmetric Wi-valued bilinear pairing on Vi. The family {(Vi,W i,q i)}i∈Nis a vector space expander family if the pairings {qi}i∈Nsatisfy certain linear algebraic criteria called bounded qi-valence and bounded Cheeger constant in a uniform way. As mentioned already, the Cheeger constant is defined generally for the data (V,W,q) (see Sec. 2.2). In this context, the previous theorem can be restated succinctly as follows: Theorem 1.3. Let {Γi}i∈Nbe a family of finite simplicial graphs,and let {A(Γi)}i∈Ndenote the corresponding family of right-angled Artin groups. Then {Γi}i∈Nis a graph expander family if and only if {(H1(A(Γi),L),H2(A(Γi),L),)}i∈N, is a vector space expander family. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 5 Observe that connectedness of the graphs in the family is not assumed as a hypothesis of the stated theorems, nor shall it be for us in the definition of a graph expander family. Instead, connectedness of the graphs in both cases is a consequence of the Cheeger constant being nonzero. We remark that whereas the cohomology vector spaces of a right-angled Artin group depend on the field over which they are defined, the property of being a graph expander family or a vector space expander family is independent of the choice of field. As a further remark concerning the fields occurring in the previous results, it will become apparent to the reader that not only can Lbe arbitrary, but it need not be fixed as the index ivaries. Indeed, the numerical invariants used to define vector space expanders are all either related to the non-degeneracy of the bilinear pairing or to dimension, both of which are blind to the intrinsic structure of the field of definition. The Cheeger constant of a finite graph is an invariant that is computable from the adjacency matrix of the graph. The Cheeger constant of a vector space equipped with a pairing is less obviously computable, since its definition quantifies over all subspaces of up to half the dimension of the ambient space (see Sec. 2.2). However, the reader will note that the methods in Sec. 4 are explicit and constructive, and they do in fact effectively yield the Cheeger constant of the relevant vector spaces. The notion of a vector space expander family is more flexible than that of a graph expander family, and we will illustrate this with an example of a vector space expander family which does not arise from the cohomology of the right-angled Artin groups associated to a graph expander family. This is a reflection of the relatively lax hypotheses on the input data of a vector space expander family. For instance, the vector space valued bilinear pairing is more or less arbitrary other than being assumed to be (anti)-symmetric, which relaxes much of the inherent structure of the cup product on the cohomology of a right-angled Artin group. The authors expect that the flexibility of vector space expanders will contribute to their applicability. There is another linear-algebraic version of expanders, called dimension expanders, which were proven to exist by Lubotzky–Zelmanov in the case of characteristic zero fields [27], and by Bourgain–Yehudayoff in the case of finite fields [2, 3]. Here, one considers a finite-dimensional vector space Vand a collection of klinear maps {Ti:V→V}1≤i≤k. This data is called an -dimension expander if for all subspaces W⊂Vof dimension at most half of that of V, the dimension of W+ k  i=1 Ti(W), is at least (1 +)dimW. The construction of dimension expanders (with bounded away from zero, kbounded above, and the dimension of Vtending to infinity) is much harder over finite fields than over fields of characteristic zero, whereas the constructions in this paper are independent of the base field. One bridge between graph expander families and dimension expanders arises from interpretation of regular graphs of even valence as Schreier graphs, from which one can use finitary versions of Kazhdan’s property (T) to construct the suitable linear maps. The J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 6R. Flores, D. Kahrobaei & T. Koberda authors do not know how to relate dimension expanders to vector space expanders, since a general right-angled Artin group does not usually admit any natural endomorphisms of its first cohomology. The paper is organized as follows. Section 2 introduces the definitions of the objects considered in this paper. Section 3 discusses the cohomology of right-angled Artin groups, and the circle of ideas relating connectedness of graphs, pairingconnectedness, q-valence, graph valence, and ranks of centralizers of elements in a right-angled Artin group. Section 4 establishes the main technical result of the paper, namely that the linear-algebraic Cheeger constant associated to a vector space with an (anti)-symmetric bilinear pairing agrees with the Cheeger constant of a finite simplicial graph in the case that the vector space is the first cohomology of the right-angled Artin group on the graph, and the bilinear pairing is the cup product. Section 5 builds an example of a vector space expander family not arising from the cohomology of right-angled Artin groups on a graph expander family. 2. Graph and Vector Space Expanders In this section, we recall some relevant facts about graph expander families and define vector space expander families. 2.1. Graph expander families The literature on graph expander families and their applications is enormous. The reader may consult [16, 23, 24, 26] and the references therein, for example. For the sake of brevity, we will only discuss the combinatorial definition of an expander family. Let Γ be a finite graph, not necessarily simplicial, with vertex set Vert(Γ) and edge set Edge(Γ). We assume that Γ is undirected. If A⊂Vert(Γ), we write ∂A for the neighbors of A.Thatis,∂A consists of the vertices of Vert(Γ) which are not contained in Abut which are adjacent to a vertex in A. If in addition |A|≤|Vert(Γ)|/2, we consider the isoperimetric invariant hA=|∂A| |A|. The Cheeger constant hΓis defined to be hΓ=min AhA, where the minimum is taken over all subsets of Vert(Γ) satisfying |A|≤|Vert(Γ)|/2. Let {Γi}i∈Nbe a sequence of connected graphs such that |Vert(Γi)|→∞,such that each vertex in Γihas valence which is bounded independently of i.Wesay that {Γi}i∈Nis a graph expander family if infihΓi>0. We note that as is well known, the bound infihΓi>0 makes any connectivity assumption of the graphs {Γi}i∈Nredundant. Indeed, if Γ is disconnected then there is a component Λ of Γ that contains at most half of the vertices of Γ. Setting A= Vert(Λ), we obtain ∂A =∅,andsohΓ=0. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 7 2.2. Vector space expander families Throughout this section and for the rest of the paper, we fix a field Lover which all vector spaces will be defined. All bilinear pairings are assumed to be symmetric or anti-symmetric, so that for all suitable vectors vand w,wehaveq(v,w)=±q(w, v). Our reasons for adopting this assumption are that it mirrors an intrinsic property of the cup product pairing, and because otherwise the orthogonal complement of F may be asymmetric depending on which side it is defined. An asymmetric orthogonal complement would result in an unnecessary layer of subtlety and complication that would not enrich the theory at hand. 2.2.1. The Cheeger constant Let Vbe a collection {(Vi,W i,q i)}i∈Nof finite dimensional vector spaces Viequipped with vector space valued bilinear pairings qi:Vi×Vi→Wi. The Cheeger constant of Vis defined by analogy to graphs. To begin, let Vbe a fixed finite-dimensional vector space and let q:V×V→W, be a vector space valued bilinear pairing on V.LetF⊂Vbe a vector subspace such that 0 <dim F≤(dim V)/2. We write Cfor the orthogonal complement of F in V,sothat C={v∈V|q(f,v) = 0 for all f∈F}. Clearly Cis a vector subspace of V.TheCheeger constant of Fis defined to be hF=dim V−dim F−dim C+dim(C∩F) dim F. The Cheeger constant of Vis defined by hV=inf dim F≤(dim V)/2hF. We will call hVthe Cheeger constant of the triple (V,W,q). We will suppress W and qfrom the notation for the Cheeger constant if no confusion can arise. We note that whereas the Cheeger constant hVmay appear strange at first, it is defined in such a way as to reflect the Cheeger constant of a graph. To see this last statement illustrated more explicitly, see Lemma 4.2. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 8R. Flores, D. Kahrobaei & T. Koberda 2.2.2. The q-valence of a vector space Let Vbe a finite-dimensional vector space, and let qbe a vector space valued bilinear pairing on V.If∅ =S⊂Vand Bis a basis for V,wewrite dB(S)=max s∈S|{b∈B|q(s, b)=0}|,d(S)= min Babasis dB(S), d(V)= min Sspans Vd(S). We call d(V)theq-valence of V. 2.2.3. Pairing-connectedness Let Vand qbe as before. We say that Vis pairing-connected if whenever V∼ =V0⊕V1 is a nontrivial direct sum decomposition of V, then there are vectors v0∈V0and v1∈V1such that q(v0,v 1)=0. 2.2.4. Defining vector space expanders We are now ready to give the definition of a vector space expander family. Definition 2.1. We say that Vis a vector space expander family if the following conditions are satisfied: (1) We have lim i→∞ dim Vi=∞. (2) There exists an Nsuch that for all i,wehaved(Vi)≤N. (3) We have h=inf ihVi>0. The reader may note that the first condition is analogous to the requirement that the number of vertices in a family of expander graphs tends to infinity. The second condition is analogous to the finite valence condition in a family of expander graphs. As with the connectedness assumption for graph expander families, the pairingconnectedness of a vector space Vis a formal consequence of hV>0. Precisely, we have the following proposition. Proposition 2.2. Let (V,W,q)be as above, and suppose hV>0.ThenVis pairing-connected. Proof. Suppose the contrary, so that V=V0⊕V1is a nontrivial splitting of V witnessing the failure of pairing-connectedness. Without loss of generality, dim V0≤ J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 9 dim V/2. Set F=V0. Note then that V1⊂C, the orthogonal complement of F.If C∩F=0thendimC≥dim V1+dim(C∩F). It follows that dim V−dim F−dim C+dim(C∩F)≤dim V−dim V0−dim V1=0, which proves the proposition. As we will show in Sec. 3, pairing-connectedness for the triple (H1(A(Γ),L),H2(A(Γ),L),), is equivalent to connectedness of Γ. 3. Cohomology, q–Valence and Pairing–Connectedness In this section, we establish a generator-free characterization of bounded valence in a graph through cohomology of the corresponding right-angled Artin group. 3.1. The cohomology ring of a right-angled Artin group A general reference for this section is [21], for instance. Let Γ be a finite simplicial graph and A(Γ) the corresponding right-angled Artin group. The group A(Γ) is naturally the fundamental group of a locally CAT(0) cube complex, called the Salvetti complex S(Γ) of Γ. The space S(Γ) is a classifying space for A(Γ), so that H∗(S(Γ),R)∼ =H∗(A(Γ),R), over an arbitrary ring R.ThecomplexS(Γ) can be built from the unit cube in R|Vert(Γ)|, with the coordinate directions being identified with the vertices of Γ. One includes the face spanned by a collection of edges if the corresponding vertices span a complete subgraph of Γ. Finally, one takes the image inside R|Vert(Γ)|/Z|Vert(Γ)|, so that S(Γ) is a subcomplex of a torus. With this description, it is clear that one can build S(Γ) out of a collection of tori of various dimensions, one for every complete subgraph of Γ, and by gluing these tori together along distinguished coordinate subtori. The reader may compare with the description of the Salvetti complex given in [7]. Let Lbe a field, viewed as a trivial A(Γ)–module. We have that H∗((S1)n,L)∼ =Λ(Ln), the exterior algebra of Ln. Via Poincar´e duality, coordinate subtori of tori making up S(Γ) give rise to preferred cohomology generators in various degrees of the exterior algebra, and the gluing data of the subtori determines how the exterior algebras corresponding to complete subgraphs assemble into the cohomology algebra of S(Γ). To give slightly more detail, let Λ ⊂Γ be a subgraph. For us, a subgraph is always full, in the sense that if λ1,λ 2∈Vert(Λ) and {λ1,λ 2}∈Edge(Γ) then {λ1,λ 2}∈Edge(Λ). Full subgraphs are sometimes called induced.Itisawellknown and standard fact that A(Λ) is naturally a subgroup of A(Γ)[7].Itisnotdifficult J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 16 R. Flores, D. Kahrobaei & T. Koberda if for each index ik, there is a vector wikcontained in the linear span of {v∗ 1,...,v∗ n}\{v∗ i1,...,v∗ ij}, so that the vectors of the form fik=v∗ ik+wikform a basis for F. Such bases for Fwill be called admissible bases.Notethatif{v∗ i1,...,v∗ ij}is admissible then the vectors wikare uniquely determined for 1 ≤k≤j. It is straightforward to determine whether a tuple is admissible: indeed, express an arbitrary basis for F in terms of the basis {v∗ 1,...,v∗ n}, the latter of which we view as the columns of a matrix. A tuple is admissible if and only if the corresponding j×jminor is invertible. Let E∗={v∗ 1,...,v∗ j}⊂{v∗ 1,...,v∗ n}, be admissible, and let E={v1,...,v j}be the corresponding set of vertices. We write ΓEfor the subgraph of Γ spanned by E,andE0for the set of isolated vertices in E. For a given subspace F, there are many possible admissible tuples E∗we might consider. Among those, we will always focus our attention on those for which |E0| is minimized. Such a choice of E∗may of course not be unique. Returning to an admissible basis for F, after re-indexing the vertices of Γ if necessary, we will fix a basis for Vnow of the form {f1,...,f j,v∗ j+1,...,v∗ n}, where fi=v∗ i+wias before. Such a basis for Vwill be called standard relative to F,andE∗will be the corresponding admissible tuple. We will fix the following notation in the sequel. Suppose F⊂Vhas dimension j. If {f1,...,f j,v∗ j+1,...,v∗ n}is a standard basis of Vrelative to F,writeFfor the span of {v∗ 1,...,v∗ j},writeCfor its orthogonal complement with respect to q,and let Ydenote the span of {v∗ j+1,...,v∗ n}. We will in fact prove the following lemma, which implies Lemma 4.3. Lemma 4.4. If F⊂Vhas dimension jthen there exists a standard basis {f1,...,f j,v∗ j+1,...,v∗ n}, of Vrelative to Fsuch that if x∈Cand F∩C=0then x∈C∩Y, and if F∩C=0then x∈(C∩F)+(C∩Y). Lemma 4.4 implies Lemma 4.3, since then dim C≤dim C−dim(C∩F)+dim(C∩F). We first establish it in the simpler cases where dim F= 1 and in the case where there exists an admissible basis for Fwith E0=∅. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 17 Proof of Lemma 4.4. When dim F= 1 Clearly we may assume that dim V≥2. Suppose Fis the span of a∈V.ObservethatF⊂C.Wewrite{f1,v∗ 2,...,v∗ n}for a standard basis for Vrelative to F.Wehavethatais a nonzero multiple of f1, and Fis the span of v∗ 1.Ifx∈Cthen we may write x=λ1f1+ n  i=2 λiv∗ i. We write w=x−λ1f1and we assume λm=0forsomem≥2. Note that q(f1,x)= q(f1,w). If q(v∗ 1,v∗ m)=0thenq(f1,x)hasλ1λmas the coefficient appearing before the vector dual to the edge {v1,v m}.So,ifx∈Cthen q(v∗ 1,v∗ m) = 0, whence it follows that v∗ m∈C.Sincemwas chosen arbitrarily subject to the condition λm=0,wehavethatw∈C∩Y,whereYis the span of {v∗ 2,...,v∗ n}.This establishes the lemma in this case. ProofofLemma4.4.When E0=∅Let {f1,...,f j,v∗ j+1,...,v∗ n}be a standard basis relative to F, where the admissible tuple E∗satisfies E0=∅. Each component of ΓEconsists of at least two vertices. We write {F,C,Y}as before. Let x∈C be written as j  i=1 λifi+ n  i=j+1 λiv∗ i. Suppose first that λm=0forsomem≤j.Thevertexvm∈Eis adjacent to avertexvk∈E,sothatq(λmfm,f k)= 0, whence it follows that q(x, fk)=0, contradicting the fact that x∈C. We conclude that λm=0form≤j,sothatwe may write x= n  i=j+1 λiv∗ i. Mimicking the proof in the case dim F=1,wehavethatx∈C∩Y, as desired. Now let us consider a standard basis B={f1,...,f k,f k+1,...,f j,v∗ j+1,...,v∗ n}, relative to F, where the vertices in the admissible tuple Ewith indices 1 ≤i≤k are precisely those which are not isolated in ΓE. We remind the reader that we assume here and henceforth that Bis chosen in such a way that |E0|is minimized. By the proofs of the cases of Lemma 4.4 given so far, we may assume that k<j. Let x∈Cas before, and write x= j  i=1 λifi+ k  i=j+1 λiv∗ i. As argued in the proof in the case E0=∅,wehavethatλm=0form≤k. Lemma 4.5. Let Bbe as above. If k+1<m≤jthen q(fk+1,f m)=0. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 18 R. Flores, D. Kahrobaei & T. Koberda Proof. Write fk+1 =v∗ k+1 + n  s=j+1 μk+1 sv∗ s,f m=v∗ m+ n  t=j+1 μm tv∗ t. Byassumption,wehavethatq(v∗ k+1,v∗ m) = 0, since the corresponding vertices are isolated. If q(fk+1,f m)= 0 then one of the three following cases must occur. (1) The coefficient μk+1 sis nonzero for a suitable s>jwith q(v∗ s,v∗ m)=0. (2) The coefficient μm tis nonzero for a suitable t>jwith q(v∗ k+1,v∗ t)=0. (3) We have μk+1 sμm t=μk+1 tμm sfor suitable indices s, t > j with s=tand q(v∗ s,v∗ t)=0. In the first of these possibilities, we write E=(E\{vk+1})∪{vs}. We claim that (E)∗remains admissible. This is straightforward to check. Indeed, we record an n×nmatrix Mwhose columns are labeled by {v∗ 1,...,v∗ n},whose rows are labeled by {f1,...,f j,v∗ j,...,v∗ n}, and whose entries are the v∗ coefficient mi, of the ith row basis element. We have that the j×jblock in the upper left hand corner is the identity matrix. Exchanging vk+1 for vscorresponds to switching the (k+1)standsth columns of M.The(k+ 1)st row of the sth column reads μk+1 s= 0. Thus after exchanging these two columns, the upper left hand j×j block remains invertible. Moreover, q(v∗ s,v∗ m)= 0, whence vsand vmare no longer isolated vertices. It follows that |E 0|<|E0|, which contradicts the minimality of |E0|. Thus, the first item is ruled out. We may rule out the second of these items analogously. To rule out the third item, we let E =E\{vk+1,v m}∪{vs,v t}. It suffices to show that (E)∗is admissible, since vsand vtare adjacent in Γ under the assumptions of the third item. We switch the columns with labels k+1ands,and with labels mand t.Sinceμk+1 sμm t=μk+1 tμm s, the determinant of the upper left hand j×jblock remains nonzero. This establishes the lemma. In order to complete the proof of Lemma 4.4, we will need to describe a process of modifying a given standard basis Bto obtain one with more advantageous features. Specifically, we will transform Binto a standard basis Bk+1 such that if x∈Cis expressed with respect to Bk+1, then the first k+ 1 coefficients of xmust vanish. To this end, suppose fr/∈Cfor r>k. Without loss of generality, r=k+1. By Lemma 4.5, we see that there is an index m<k+1 such that q(fm,f k+1)=0. Since vk+1 is isolated, we have q(v∗ k+1,v∗ m) = 0. Again we write fk+1 =v∗ k+1 + n  s=j+1 μk+1 sv∗ s,f m=v∗ m+ n  t=j+1 μm tv∗ t. Observe that at least one of items 1, 2, or 3 in the proof of Lemma 4.5 above must occur for this pairing to be nonzero. We now proceed to modify Bto obtain a new J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 19 standard basis Bk+1 as follows, according to the reason for which q(fm,f k+1)=0. Namely: (1) If μm t= 0 for some index twith q(v∗ k+1,v∗ t)=0,thenwesetBk+1 =B. (2) If the previous item does not hold but if there exists an index swith μk+1 s=0 and q(v∗ m,v∗ s) = 0 then we substitute v∗ sfor v∗ k+1 to obtain an admissible tuple as in Lemma 4.5. We then set Bk+1 to be the standard basis associated to the corresponding admissible tuple. (3) If both of the previous items do not hold then at least one of the products μk+1 sμm tand μk+1 tμm sis nonzero for suitable choices of indices sand twith q(v∗ s,v∗ t)= 0. We substitute v∗ sfor v∗ k+1. As before, the resulting tuple is admissible. We then write Bk+1 for the corresponding standard basis. As before, these exchanges do not change the size of |E0|.Wenowwrite Bk+1 ={fk+1 1,...,fk+1 j,e j+1,...,e n}, where indices have been renumbered after any substitutions. Note the following observation. Observation 4.6. For r≤jand r=k+1,wehavethatfk+1 rdiffers from frby a (possibly zero) multiple of fk+1,andfk+1 k+1 =fk+1. If x∈C, we write it with respect to this new basis, so that x= j  i=1 λk+1 ifk+1 i+ n  i=j+1 λk+1 iv∗ i. The previous considerations show that λk+1 i=0fori≤k. Lemma 4.7. The following hold. (1) If x∈Cis as above,then λk+1 k+1 =0. (2) For k+1≤r, s ≤j, we have q(fk+1 r,fk+1 s)=0. Proof. Suppose now that λk+1 k+1 = 0, and consider the index mas before which was chosen so that q(fm,f k+1)= 0. Then for a suitable constant α,wehave q(fk+1 m,fk+1 k+1 )=q(fm+αfk+1,f k+1)=q(fm,f k+1)=0. Moreover, q(fk+1 m,fk+1 k+1 ) is supported on the dual vector to the edge {vm,v k+1}or {vt,v k+1}(which was the edge {vm,v s}or the edge {vt,v s}before the vertices were re-indexed in the definition of Bk+1). No other summand making up the vector x (i.e. λifk+1 ifor i≥k+2orλk+1 iv∗ ifor i≥j+ 1) is supported on v∗ k+1. It follows that if λk+1 k+1 =0thenq(x, fk+1 m)= 0, which is a contradiction. We may therefore conclude that λk+1 k+1 =0. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 20 R. Flores, D. Kahrobaei & T. Koberda For the second claim of the lemma, note that for k+1≤r, s ≤j, we have q(fr,f s) = 0 by Lemma 4.5, which implies that q(fk+1 r,fk+1 s)=0aswell since both of these vectors differ from frand fs,respectively, by a multiple of fk+1. Now suppose that fk+1 i/∈Cfor some k+2 ≤i≤j, and without loss of generality we may assume that i=k+ 2. Repeating the procedure for the construction of Bk+1, we may add multiples of fk+1 k+2 to the basis vectors which are distinct from fk+1 k+2 itself in order to obtain a new basis Bk+2 ={fk+2 1,...,fk+2 j,v∗ j+1,...,v∗ n}. Since q(fk+1 k+2 ,fk+2 i)=0fori≥k+1,wemusthavethatq(fk+1 r,fk+1 k+2 )=0forsome r≤k. As before, if x∈C,weexpressxin this basis with coefficients {λk+2 i}1≤i≤n and observe that the coefficients satisfy λk+2 i=0fori≤kand λk+2 k+2 =0.Itis conceivable that in the course of this modification we may find that λk+2 k+1 =0,a conclusion which we wish to rule out. Lemma 4.8. If x∈Cis expressed with respect to the basis Bk+2,then we have λk+2 k+1 =0. Proof. We consider a vector fk+1 mwhich satisfies q(fk+1 m,fk+1 k+1 )= 0, and for suitable constants αand β, we obtain expressions fk+2 m=fk+1 m+αfk+1 k+2 ,f k+2 k+1 =fk+1 k+1 +βfk+1 k+2 . Computing, we have q(fk+2 m,fk+2 k+1 )=q(fk+1 m,fk+1 k+1 )+βq(fk+1 m,fk+1 k+2 ), using the orthogonality of fk+1 k+1 and fk+1 k+2 . It follows that q(fk+2 m,fk+2 k+1 ) is supported on the vector dual to the edge {vk+1,v r}for a suitable r, as this was already true of q(fk+1 m,fk+1 k+1 ). Then, as we argued for Bk+1 in Lemma 4.7, we have that λk+2 k+1 = 0 again. We can now complete the argument. Proof of Lemma 4.4. We inductively construct a sequence of distinct bases for Vand corresponding admissible tuples which we write as {Bk+2,Bk+3,...},{(Ek+2)∗,(Ek+3)∗,...}, which have the property that if x∈Cis written with respect to the basis Bk+s then the coefficients λk+s of fk+s are trivial for ≤k+s. We are able to construct Bk+s+1 from Bk+sprecisely when there is an index k+s≤i≤jsuch that J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 21 fk+s i/∈C.SinceFis finite dimensional, the sequence will terminate after finitely many terms. This will happen either for k+s=jor for some s<j−k. In the first case, we see that C∩F= 0. In the second case, the basis vectors {fk+s k+s+1,...,fk+s j}are orthogonal to F. To complete the proof of the lemma, we set fi=fk+s ifor 1 ≤i≤j,andFis the span of the associated admissible tuple (Ek+s)∗. As in the statement of the lemma, we write Yfor the span of {v∗ j+1,...,v∗ n}.Ifx∈Cthen x= j  i=k+s+1 λk+s ifi+y, for a suitable vector y∈Y. Note that by assumption, we have x−y∈C,which implies that y∈C. This shows that y∈C∩Y,sinceq(y,fi) = 0 for all i≤jand hence q(y,v∗ i)=0fori≤j. It follows that if C∩F=0thenx=y∈C∩Y,and otherwise that x∈(C∩F)+(C∩Y), which completes the proof. 4.2. Proof of the main results Theorems 1.2 and 1.3 now follow almost immediately. The size of the set of vertices of Γitending to infinity is equivalent to the dimension of Vi=H1(A(Γ)) tending to infinity, over any field. Bounded qi-valence of Vi, bounded valence of Γi,and bounded centralizer rank in A(Γ) are all equivalent by Corollary 3.3 and Lemma 3.5. Finally, Theorem 4.1 implies that the Cheeger constant of Γiis equal to the Cheeger constant of the triple (H1(A(Γ)),H2(A(Γ)),q), over any field. This establishes the main results. 4.3. Generalizations to higher dimension By considering cohomology of right-angled Artin groups beyond dimension two, one can use vector space expanders to generalize graph expanders to higher dimensions. Unfortunately, this does not seem to give much new information, as might be expected; indeed, the cohomology of a right-angled Artin group is completely determined by its behavior in dimension one and the cup product pairing therein. This can easily be seen through a suitable generalization of Proposition 3.1 to higher-dimensional cohomology: the cohomology of the right-angled Artin group A(Γ) in each dimension is determined by the corresponding number of cells in the flag complex of Γ (with a dimension shift), and the cup product pairing is determined by the face relation. The flag complex, moreover, is completely determined by its 1-skeleton. In particular, there does not seem to be a meaningful connection to more fruitful notions of higher-dimensional expanders (cf. [25], for instance). J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 22 R. Flores, D. Kahrobaei & T. Koberda 5. A Vector Space Expander Family that Does Not Arise from a Graph Expander Family In this section, we give a method for producing families of vector space expanders that do not arise from the cohomology rings of right-angled Artin groups of graph expanders. Let {Γi}i∈Nbe a family of finite connected simplicial graphs which form a graph expander and let Lbe an arbitrary field. We will write Vi=H1(A(Γi),L),W i=H2(A(Γi),L),q i=, where denotes the cup product in the cohomology ring of the corresponding group. For each i, we choose an arbitrary vertex viof Γi.WesetV i=Vi,and we let Wi=W⊕L, where the summand Lis generated by a vector z∗ i.Weset q i=qi⊕q0,i,whereq0,i((vi)∗,(vi)∗)=z∗ i,andwhereq0,i vanishes on inputs of all other basis vectors arising from duals of vertices, in both arguments. That is, let {vi 1,...,vi n}be the vertices of Γi, and without loss of generality we may assume that vi=vi 1.Wesetq0,i((vi j)∗,(vi k)∗) = 0 unless both vi jand vi kare equal to vi 1, and we extend by bilinearity. Proposition 5.1. If V={(V i,W i,q i)}i≥0is as above then: (1) The family Vis a vector space expander. (2) The family Vdoes not arise from the cohomology of the right-angled Artin groups associated to a sequence of graphs. The second item of Proposition 5.1 means that there is no family of finite connected simplicial graphs {Λi}i∈Nsuch that V i=H1(A(Λi),L),W  i=H2(A(Λi),L),q  i=. Proof of Proposition 5.1. Since V i=Vi,wehavethatdimV i→∞.Now consider q i-valence, which we denote by di, and we compare with the graph valence d(Γi)ofΓ i. By setting B=S= (Vert(Γi))∗in the definition of q i-valence, we see that di(V)≤d(Γi)+1.Thus,Vhas uniformly bounded valence. For each i,the vector space V iis already pairing-connected with respect to the pairing qi,and qi(v,w)= 0 implies q i(v,w)=0,sothatV iis pairing-connected with respect to the pairing q i. We now need to estimate the Cheeger constants of V. We suppress the iindex, and write {v∗ 1,...,v∗ n}for a basis of Vconsisting of dual vectors of vertices of Γ. We assume v1to be the distinguished vertex of Γ such that q0(v∗ 1,v∗ 1)=0.Let 0=F⊂Vbe a subspace of dimension at most (dim V)/2, and let h0be the infimum of the Cheeger constants of the family Vwith respect to q, the usual cup product. We denote by Cqthe orthogonal complement of Fwith respect to q,by C0the orthogonal complement of Fwith respect to q0,andbyCthe orthogonal complement of Fwith respect to q. Clearly, C=Cq∩C0. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 23 Now, let f∈Fbe written as f= n  i=1 μiv∗ i and let x∈Vbe written as x= n  i=1 λiv∗ i. It follows by definition that q0(v∗ i,x)=0fori=1,sothatq0(f,x)=λ1μ1. Thus, the span of {v∗ 2,...,v∗ n}is always contained in C0, and consequently C0has dimension either nor n−1. Thus, dim Cis either equal to dim Cqor dim Cq−1. Similarly, x∈C∩Fif and only if x∈Cq∩C0∩F,sothatdim(C∩F)iseither equal to dim(Cq∩F)ordim(Cq∩F)−1. Suppose that dim(C∩F)=dim(Cq∩F)−1. Then C=Cq,sothatdimC= dim Cq−1. In this case, dim C−dim(C∩F)=dimCq−1−(dim(Cq∩F)−1) = dim Cq−dim(Cq∩F). It follows that dim C−dim(C∩F)≤dim Cq−dim(Cq∩F), and the difference between these is at most 1. Writing N=dimV−dim F, the Cheeger constant of Fsatisfies hF=N−dim C+dim(C∩F) dim F≥N−dim Cq+dim(Cq∩F) dim F. This proves that the Cheeger constant of Vis bounded away from zero, which proves that Vis a vector space expander family. To see that Vdoes not arise from a graph expander family, we note that the cup product satisfies v∗ 1v ∗ 1=0,andqis constructed so that q(v∗ 1,v∗ 1)=0.This establishes the proposition. Many variations on the construction in this section can be carried out, which illustrates the fact that vectors space expander families are indeed significantly more flexible than graph expander families. Acknowledgments The authors would like to thank A. Jaikin and A. Lubotzky for their helpful comments, and are grateful to the anonymous referee for helpful corrections and suggestions. Ram´on Flores is supported by FEDER-MEC grant MTM2016-76453-C21-P and FEDER grant US-1263032 from the Andalusian Government. Delaram Kahrobaei is supported in part by a Canada’s New Frontiers in Research Fund, under the Exploration grant entitled “Algebraic Techniques for Quantum Security”. Thomas Koberda is partially supported by an Alfred P. Sloan Foundation Research Fellowship and by NSF Grants DMS-1711488 and DMS-2002596. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 24 R. Flores, D. Kahrobaei & T. Koberda References 1. N. Alon, Eigenvalues and expanders, Theory of Computing, Vol. 6 (Singer Island, Fla., 1984), pp. 83–96. 2. J. Bourgain, Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009) 357–362. 3. J. Bourgain and A. Yehudayoff, Expansion in SL2(R) and monotone expanders, Geom. Funct. Anal. 23 (2013) 1–41. 4. N. Brady and J. Meier, Connectivity at infinity for right angled Artin groups, Trans. Amer. Math. Soc.353 (2001) 117–132. 5. P. Cartier and D. Foata, Probl`emes Combinatoires de Commutation et R´earrangements, Lecture Notes in Mathematics, Vol. 85 (Springer-Verlag, Berlin, New York, 1969). 6. Denis X. Charles, Kristin E. Lauter and Eyal Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptol.22 (2009) 93–113. 7. R. Charney, An introduction to right-angled Artin groups, Geom. Dedicata 125 (2007) 141–158. 8. J. Crisp, E. Godelle and B. Wiest, The conjugacy problem in subgroups of right-angled Artin groups, J. Topol. 2(2009) 442–460. 9. M. W. Davis, The cohomology of a Coxeter group with group ring coefficients, Duke Math. J. 91 (1998) 297–314. 10. C. Droms, Isomorphisms of graph groups, Proc. Amer. Math. Soc.100 (1987) 407– 408. 11. R. Flores, D. Kahrobaei and T. Koberda, Algorithmic problems in right-angled Artin groups: Complexity and applications, J. Algebra 519 (2019) 111–129. 12. R. Flores, D. Kahrobaei and T. Koberda, An algebraic characterization of kcolorability, Proc.Amer.Math.Soc.149 (2021) 2249–2255. 13. O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan and D. Zuckerman, Security preserving amplification of hardness, in 31st Annual Symp. Foundations of Computer Science, Vol. 1, 2 (St. Louis, MO, 1990) (IEEE Computer Society Press, Los Alamitos, CA, 1990), pp. 318–326. 14. S. Hermiller and J. Meier, Algorithms and geometry for graph products of groups, J. Algebra 171 (1995) 230–257. 15. S. Hermiller and Z. ˇ Suni´c, Poly-free constructions for right-angled Artin groups, J. Group Theory 10 (2007) 117–138. 16. S. Hoory, N. Linial and A. Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. 43 (2006) 439–561. 17. C. Jensen and J. Meier, The cohomology of right-angled Artin groups with group ring coefficients, Bull. London Math. Soc.37 (2005) 711–718. 18. M. Kambites, On commuting elements and embeddings of graph groups and monoids, Proc. Edinb. Math. Soc.52 (2009) 155–170. 19. S.-H. Kim and T. Koberda, Embeddability between right-angled Artin groups, Geom. Topol.17 (2013) 493–530. 20. S.-H. Kim and T. Koberda, Free products and the algebraic structure of diffeomorphism groups, J. Topol. 11 (2018) 1054–1076. 21. T. Koberda, Geometry and combinatorics via right-angled Artin groups, preprint (2003), arXiv:2103.09342. 22. T. Koberda, Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups, Geom.Funct.Anal.22 (2012) 1541–1590. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles. 2nd Reading November 12, 2021 13:13 WSPC/243-JTA 2150059 Expanders and right-angled Artin groups 25 23. E. Kowalski, An introduction to expander graphs, Cours Sp´ecialis´es [Specialized Courses], Vol. 26, Soci´et´eMath´ematique de France, Paris, 2019. 24. A. Lubotzky, Discrete Groups,Expanding Graphs and Invariant Measures,Modern Birkh¨auser Classics (Birkh¨auser Verlag, Basel, 2010). 25. A. Lubotzky, High dimensional expanders, in Proc. Int. Cong. Mathematicians—Rio de Janeiro 2018, Plenary Lectures, Vol. 1 (World Scientific Publication, Hackensack, New Jersey, 2018), pp. 705–730. 26. A. Lubotzky, Ralph Phillips, and Peter Sarnak, Ramanujan graphs, Combinatorica 8 (1988) 261–277. 27. A. Lubotzky and E. Zelmanov, Dimension expanders, J. Algebra 319 (2008) 730–738. 28. L. Sabalka, On rigidity and the isomorphism problem for tree braid groups, Groups Geom. Dyn.3(2009) 469–523. 29. H. Servatius, Automorphisms of graph groups, J. Algebra 126 (1989) 34–60. J. Topol. Anal. Downloaded from www.worldscientific.com by UNIVERSITY OF SEVILLE on 06/30/22. Re-use and distribution is strictly not permitted, except for Open Access articles.