\DeclareCaptionType

result[Table][List of Results]

Expanders and right-angled Artin groups

Ramón Flores Ramón Flores, Department of Geometry and Topology, University of Seville, Spain [email protected] , Delaram Kahrobaei Delaram Kahrobaei, Department of Computer Science, University of York, UK, New York University, Tandon School of Engineering, PhD Program in Computer Science, CUNY Graduate Center [email protected], [email protected] and Thomas Koberda Thomas Koberda, Department of Mathematics, University of Virginia, Charlottesville, VA 22904 [email protected]

Abstract.

The purpose of this article is to give a characterization of families of expander graphs via right-angled Artin groups. We prove that a sequence of simplicial graphs $\{\Gamma_{i}\}_{i\in\mathbb{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(\Gamma_{i})\}_{i\in\mathbb{N}}$ agrees 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, and in this context represent a different approach to expanders that those developed by Lubotzky-Zelmanov and Bourgain-Yehudayoff.

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 probabilitstic 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 [23, 1, 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 $\Gamma$ is a finite simplicial graph with vertex set $\mathrm{Vert}(\Gamma)$ and edge set $\mathrm{Edge}(\Gamma)$ , we define the right-angled Artin group on $\Gamma$ by

A(\Gamma)=\langle\mathrm{Vert}(\Gamma)\mid[v_{i},v_{j}]=1\textrm{ if and only if }\{v_{i},v_{j}\}\in\mathrm{Edge}(\Gamma)\rangle.

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 $\Gamma$ should be reflected in the intrinsic algebra of $A(\Gamma)$ [10, 28, 22, 21].

If $A(\Gamma)$ 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 $\Gamma$ and elements of the group $A(\Gamma)$ . Indeed, the vertices of $\Gamma$ are then identified with the generators in the presentation, and the adjacency relation in $\Gamma$ is exactly the commutation relation among generators of $A(\Gamma)$ . The problem with this perspective is that a choice of generators of $A(\Gamma)$ is not canonical. For instance, it is possible to find a generating set of $A(\Gamma)$ that such that commutation relations between generators have nothing to do with the combinatorics of $\Gamma$ . The point of this paper is to translate between the combinatorics of $\Gamma$ and the algebraic structure of $A(\Gamma)$ in a way that is intrinsic to $A(\Gamma)$ . Specifically, we wish to characterize graph expander families in a canonical 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(\Gamma)$ decomposes as a nontrivial direct product if and only if $\Gamma$ is a nontrivial join [29].
(2)

$A(\Gamma)$ decomposes as a nontrivial free product if and only if $\Gamma$ is disconnnected [4, 21].
(3)

$A(\Gamma)$ contains a subgroup isomorphic to a product $F_{2}\times F_{2}$ of nonabelian free groups if and only if $\Gamma$ has a full subgraph which is isomorphic to a square [18, 19].
(4)

The poly-free length of $A(\Gamma)$ is two if and only if $\Gamma$ admits an independent set $D$ of vertices such that every cycle in $\Gamma$ meets $D$ at least twice [15].
(5)

$A(\Gamma)$ is obtained from infinite cyclic groups through iterated free products and direct products if and only if $\Gamma$ contains no full subgraph which is isomorphic to a path of length three [19, 20].
(6)

$A(\Gamma)$ is a semidirect product of two free groups of finite rank if and only if $\Gamma$ is a finite tree or a finite complete bipartite graph [15].
(7)

There is a finite nonabelian group acting faithfully on $A(\Gamma)$ by outer automorphisms if and only if $\Gamma$ admits a nontrivial automorphism [11].
(8)

A graph $\Gamma$ with $n$ vertices is $k$ –colorable if and only if there is a surjective map

$A(\Gamma)\to\prod_{i=1}^{k}F_{i},$

where for $1\leq i\leq k$ the group $F_{i}$ is a free group of rank $m_{i}$ , and where $\sum_{i=1}^{k}m_{i}=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 $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ of finite graphs is called a graph expander family if the number of vertices in $\Gamma_{i}$ tends to infinity as $i$ tends to infinity, if the valence of each vertex of $\Gamma_{i}$ is bounded independently of $i$ , and if a certain isoperimetric invariant called the Cheeger constant (or expansion constant) of each $\Gamma_{i}$ is uniformly bounded away from zero. We refer the reader to Section 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 the present 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 $h_{V}$ of 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

\{(H^{1}(A(\Gamma),L),H^{2}(A(\Gamma),L),\smile)\},

where $H^{i}(A(\Gamma),L)$ is the $i^{th}$ cohomology group of $A(\Gamma)$ with coefficients in a field $L$ , and $\smile$ the cup product restricted to $H^{1}(A(\Gamma),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 $\Gamma$ be a finite simplicial graph, let $h_{\Gamma}$ denote the Cheeger constant of $\Gamma$ , and let $h_{V}$ denote the Cheeger constant of the triple

\{(H^{1}(A(\Gamma),L),H^{2}(A(\Gamma),L),\smile)\}.

Then $h_{\Gamma}=h_{V}$ .

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 $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ be a family of finite simplicial graphs, let $\{A(\Gamma_{i})\}_{i\in\mathbb{N}}$ denote the corresponding family of right-angled Artin groups, and let $L$ be an arbitrary field. Then $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ is a graph expander family if and only if:

(1)

The rank (i.e. size of the smallest generating set) of $A(\Gamma_{i})$ tends to infinity as $i$ tends to infinity.
(2)

The rank of the centralizer of each nontrivial element of $A(\Gamma_{i})$ is bounded independently of $i$ .
(3)

The Cheeger constant of the family

$\{(H^{1}(A(\Gamma_{i}),L),H^{2}(A(\Gamma_{i}),L),\smile)\}_{i\in\mathbb{N}}$

is bounded away from zero.

This result is proved in the more general framework of vector space expanders (with a precise definition in Subsection 2.2 below). This is a certain sequence of triples $\{(V_{i},W_{i},q_{i})\}_{i\in\mathbb{N}}$ , each of which is defined over a fixed field $L$ , where each $V_{i}$ is a finite dimensional vector space such that $\dim V_{i}\to\infty$ as $i\to\infty$ . Each $W_{i}$ is an $L$ –vector space, and $q_{i}$ is a symmetric or anti-symmetric $W_{i}$ –valued bilinear pairing on $V_{i}$ . The family $\{(V_{i},W_{i},q_{i})\}_{i\in\mathbb{N}}$ is a vector space expander family if the pairings $\{q_{i}\}_{i\in\mathbb{N}}$ satisfy certain linear algebraic criteria called bounded $q_{i}$ –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 Subsection 2.2 for details).

In this context, the previous theorem can be restated succinctly as follows:

Theorem 1.3.

Let $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ be a family of finite simplicial graphs, and let $\{A(\Gamma_{i})\}_{i\in\mathbb{N}}$ denote the corresponding family of right-angled Artin groups. Then $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ is a graph expander family if and only if

\{(H^{1}(A(\Gamma_{i}),L),H^{2}(A(\Gamma_{i}),L),\smile)\}_{i\in\mathbb{N}}

is a vector space expander family.

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 $L$ be arbitrary, but it need not be fixed as the index $i$ varies. 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 Subsection 2.2 below). However, the reader will note that the methods in Section 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 [3, 2]. Here, one considers a finite dimensional vector space $V$ and a collection of $k$ linear maps $\{T_{i}\colon V\to V\}_{1\leq i\leq k}$ . This data is called an $\epsilon$ –dimension expander if for all subspaces $W\subset V$ of dimension at most half of that of $V$ , the dimension of

W+\sum_{i=1}^{k}T_{i}(W)

is at least $(1+\epsilon)\dim W$ . The construction of dimension expanders (with $\epsilon$ bounded away from zero, $k$ bounded above, and the dimension of $V$ tending to infinity) is much harder over finite fields than over fields of characteristic zero, whereas the constructions in the present 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 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, pairing–connectedness, $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, 24, 26, 23] and the references therein, for example. For the sake of brevity, we will only discuss the combinatorial definition of an expander family.

Let $\Gamma$ be a finite graph, not necessarily simplicial, with vertex set $\mathrm{Vert}(\Gamma)$ and edge set $\mathrm{Edge}(\Gamma)$ . We assume that $\Gamma$ is undirected. If $A\subset\mathrm{Vert}(\Gamma)$ , we write $\partial A$ for the neighbors of $A$ . That is, $\partial A$ consists of the vertices of $\mathrm{Vert}(\Gamma)$ which are not contained in $A$ but which are adjacent to a vertex in $A$ .

If in addition $|A|\leq|\mathrm{Vert}(\Gamma)|/2$ , we consider the isoperimetric invariant

h_{A}=\frac{|\partial A|}{|A|}.

The Cheeger constant $h_{\Gamma}$ is defined to be

h_{\Gamma}=\min_{A}h_{A},

where the minimum is taken over all subsets of $\mathrm{Vert}(\Gamma)$ satisfying $|A|\leq|\mathrm{Vert}(\Gamma)|/2$ .

Let $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ be a sequence of connected graphs such that $|\mathrm{Vert}(\Gamma_{i})|\to\infty$ , such that each vertex in $\Gamma_{i}$ has valence which is bounded independently of $i$ . We say that $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ is a graph expander family if $\inf_{i}h_{\Gamma_{i}}>0$ .

We note that as is well known, the bound $\inf_{i}h_{\Gamma_{i}}>0$ makes any connectivity assumption of the graphs $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ redundant. Indeed, if $\Gamma$ is disconnected then there is a component $\Lambda$ of $\Gamma$ that contains at most half of the vertices of $\Gamma$ . Setting $A=\mathrm{Vert}(\Lambda)$ , we obtain $\partial A=\varnothing$ , and so $h_{\Gamma}=0$ .

2.2. Vector space expander families

Throughout this section and for the rest of the paper, we fix a field $L$ over which all vector spaces will be defined. All bilinear pairings are assumed to be symmetric or anti-symmetric, so that for all suitable vectors $v$ and $w$ , we have $q(v,w)=\pm 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 $\mathcal{V}$ be a collection $\{(V_{i},W_{i},q_{i})\}_{i\in\mathbb{N}}$ of finite dimensional vector spaces $V_{i}$ equipped with vector space valued bilinear pairings

q_{i}\colon V_{i}\times V_{i}\to W_{i}.

The Cheeger constant of $\mathcal{V}$ is defined by analogy to graphs. To begin, let $V$ be a fixed finite dimensional vector space and let

q\colon V\times V\to W

be a vector space valued bilinear pairing on $V$ . Let $F\subset V$ be a vector subspace such that $0<\dim F\leq(\dim V)/2$ . We write $C$ for the orthogonal complement of $F$ in $V$ , so that

C=\{v\in V\mid q(f,v)=0\textrm{ for all }f\in F\}.

Clearly $C$ is a vector subspace of $V$ . The Cheeger constant of $F$ is defined to be

h_{F}=\frac{\dim V-\dim F-\dim C+\dim(C\cap F)}{\dim F}.

The Cheeger constant of $V$ is defined by

h_{V}=\inf_{\dim F\leq(\dim V)/2}h_{F}.

We will call $h_{V}$ the Cheeger constant of the triple $(V,W,q)$ . We will suppress $W$ and $q$ from the notation for the Cheeger constant if no confusion can arise.

We note that whereas the Cheeger constant $h_{V}$ may 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.

2.2.2. The $q$ –valence of a vector space

Let $V$ be a finite dimensional vector space, and let $q$ be a vector space valued bilinear pairing on $V$ . If $\emptyset\neq S\subset V$ and $B$ is a basis for $V$ , we write

d_{B}(S)=\max_{s\in S}|\{b\in B\mid q(s,b)\neq 0\}|,\quad d(S)=\min_{B\textrm{ a basis}}d_{B}(S),\quad d(V)=\min_{S\textrm{ spans $V$}}d(S).

We call $d(V)$ the $q$ –valence of $V$ .

2.2.3. Pairing–connectedness

Let $V$ and $q$ be as before. We say that $V$ is pairing–connected if whenever $V\cong V_{0}\oplus V_{1}$ is a nontrivial direct sum decomposition of $V$ , then there are vectors $v_{0}\in V_{0}$ and $v_{1}\in V_{1}$ such that $q(v_{0},v_{1})\neq 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 $\mathcal{V}$ is a vector space expander family if the following conditions are satisfied:

(1)

We have

$\lim_{i\to\infty}\dim V_{i}=\infty.$
(2)

There exists an $N$ such that for all $i$ , we have $d(V_{i})\leq N$ .
(3)

We have

$h=\inf_{i}h_{V_{i}}>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 pairing–connectedness of a vector space $V$ is a formal consequence of $h_{V}>0$ . Precisely, we have the following.

Proposition 2.2.

Let $(V,W,q)$ be as above, and suppose $h_{V}>0$ . Then $V$ is pairing–connected.

Proof.

Suppose the contrary, so that $V=V_{0}\oplus V_{1}$ is a nontrivial splitting of $V$ witnessing the failure of pairing–connectedness. Without loss of generality, $\dim V_{0}\leq\dim V/2$ . Set $F=V_{0}$ . Note then that $V_{1}\subset C$ , the orthogonal complement of $F$ . If $C\cap F\neq 0$ then $\dim C\geq\dim V_{1}+\dim(C\cap F)$ . It follows that

\dim V-\dim F-\dim C+\dim(C\cap F)\leq\dim V-\dim V_{0}-\dim V_{1}=0,

which proves the proposition. ∎

As we will show in Section 3, pairing–connectedness for the triple

(H^{1}(A(\Gamma),L),H^{2}(A(\Gamma),L),\smile)

is equivalent to connectedness of $\Gamma$ .

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 $\Gamma$ be a finite simplicial graph and $A(\Gamma)$ the corresponding right-angled Artin group. The group $A(\Gamma)$ is naturally the fundamental group of a locally CAT(0) cube complex, called the Salvetti complex $S(\Gamma)$ of $\Gamma$ . The space $S(\Gamma)$ is a classifying space for $A(\Gamma)$ , so that

H^{*}(S(\Gamma),R)\cong H^{*}(A(\Gamma),R)

over an arbitrary ring $R$ . The complex $S(\Gamma)$ can be built from the unit cube in $\mathbb{R}^{|\mathrm{Vert}(\Gamma)|}$ , with the coordinate directions being identified with the vertices of $\Gamma$ . One includes the face spanned by a collection of edges if the corresponding vertices span a complete subgraph of $\Gamma$ . Finally, one takes the image inside $\mathbb{R}^{|\mathrm{Vert}(\Gamma)|}/\mathbb{Z}^{|\mathrm{Vert}(\Gamma)|}$ , so that $S(\Gamma)$ is a subcomplex of a torus.

With this description, it is clear that one can build $S(\Gamma)$ out of a collection of tori of various dimensions, one for every complete subgraph of $\Gamma$ , 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 $L$ be a field, viewed as a trivial $A(\Gamma)$ –module. We have that

H^{*}((S^{1})^{n},L)\cong\Lambda(L^{n}),

the exterior algebra of $L^{n}$ . Via Poincaré duality, coordinate subtori of tori making up $S(\Gamma)$ 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(\Gamma)$ .

To give slightly more detail, let $\Lambda\subset\Gamma$ be a subgraph. For us, a subgraph is always full, in the sense that if $\lambda_{1},\lambda_{2}\in\mathrm{Vert}(\Lambda)$ and $\{\lambda_{1},\lambda_{2}\}\in\mathrm{Edge}(\Gamma)$ then $\{\lambda_{1},\lambda_{2}\}\in\mathrm{Edge}(\Lambda)$ . Full subgraphs are sometimes called induced. It is a well-known and standard fact that $A(\Lambda)$ is naturally a subgroup of $A(\Gamma)$ [7]. It is not difficult to see that $A(\Lambda)$ is in fact a retract of $A(\Gamma)$ . The homology of $A(\Gamma)$ is easy to compute from the Salvetti complex, and the cohomology with trivial coefficients in a field can be easily computed using the Universal Coefficient Theorem. Each complete subgraph $\Lambda$ of $\Gamma$ gives an exterior algebra as a subring of $H^{*}(A(\Gamma),L)$ via pullback along the retraction map $A(\Gamma)\to A(\Lambda)$ , and a dimension count shows that this accounts for all the cohomology of $A(\Gamma)$ .

We are mostly concerned with $H^{1}(A(\Gamma),L)$ and $H^{2}(A(\Gamma),L)$ , together with the cup product pairing on $H^{1}(A(\Gamma),L)$ . We remark that the cohomology of right-angled Artin groups and related groups with nontrivial coefficient modules has been investigated extensively (see [9, 17] for example), but for our purposes we do not need any machinery beyond trivial coefficients. The next proposition follows easily from the description of the cohomology of the Salvetti complex above, and from the structure of exterior algebras.

Proposition 3.1.

Let $\Gamma$ be a finite simplicial graph.

(1)

We have isomorphisms of vector spaces:

$H^{1}(A(\Gamma),L)\cong L^{|\mathrm{Vert}(\Gamma)|},\quad H^{2}(A(\Gamma),L)\cong L^{|\mathrm{Edge}(\Gamma)|}.$
(2)

There is a basis $\{v_{1}^{*},\ldots,v_{|\mathrm{Vert}(\Gamma)|}^{*}\}$ for $H^{1}(A(\Gamma),L)$ which is in bijection with the set $\{v_{1},\ldots,v_{|\mathrm{Vert}(\Gamma)|}\}$ of vertices of $\Gamma$ , and there is a basis $\{e_{1}^{*},\ldots,e_{|\mathrm{Edge}(\Gamma)|}^{*}\}$ of $H^{2}(A(\Gamma),L)$ which is in bijection with the set $\{e_{1},\ldots,e_{|\mathrm{Edge}(\Gamma)|}\}$ of edges of $\Gamma$ .
(3)

The bases in the previous item can be chosen to have the following property: if $e=\{v_{i},v_{j}\}\in\mathrm{Edge}(\Gamma)$ then $v_{i}^{*}\smile v_{j}^{*}=\pm e^{*}$ , and if $\{v_{i},v_{j}\}\notin\mathrm{Edge}(\Gamma)$ then $v_{i}^{*}\smile v_{j}^{*}=0$ .

If $\{e_{1},\ldots,e_{s}\}$ denotes the set of edges of $\Gamma$ , then Proposition 3.1 implies that $H^{2}(A(\Gamma))$ is generated (over any field) by the dual vectors $\{e^{*}_{1},\ldots,e^{*}_{s}\}$ , and that these vectors are linearly independent. We fix the basis $\{e^{*}_{1},\ldots,e^{*}_{s}\}$ for $H^{2}$ once and for all, so that if $d$ is a $2$ –cohomology class then

d=\sum_{i=1}^{s}\lambda_{i}e_{i}^{*}.

With respect to this fixed basis, we call the elements $e_{i}^{*}$ for which $\lambda_{i}\neq 0$ the support of $d$ , so that $d$ is supported on the $e_{i}^{*}$ for which $\lambda_{i}\neq 0$ . We will also fix the basis $\{v_{1}^{*},\ldots,v_{|\mathrm{Vert}(\Gamma)|}^{*}\}$ for $H^{1}$ once and for all, and all computations involving cohomology classes will implicitly be with respect to these bases unless explicitly noted to the contrary.

3.2. Centralizers in right-angled Artin groups

Recall that a graph $J$ is called a join if its complement is disconnected. Equivalently, there are two nonempty subgraphs $J_{1}$ and $J_{2}$ of $J$ which partition the vertices of $J$ , and such that every vertex in $J_{1}$ is adjacent to every vertex in $J_{2}$ . We write $J=J_{1}*J_{2}$ .

Let $\Gamma$ be a finite simplicial graph and let $1\neq x\in A(\Gamma)$ be a nontrivial element, which is expressed as a word in the vertices $\{v_{1},\ldots,v_{|\mathrm{Vert}(\Gamma)|}\}$ of $\Gamma$ and their inverses. We say that $x$ is reduced if it is freely reduced with respect to the operation of commuting adjacent vertices. That is, $x$ cannot be shortened by applying moves of the form:

•

Free reduction: $\cdots a\cdot v_{i}^{\pm 1}v_{i}^{\mp 1}\cdot b\cdots\longrightarrow\cdots a\cdot b\cdots$ ;
•

Commutation of adjacent vertices: $\cdots v_{i}^{\pm 1}v_{j}^{\pm 1}\cdots\longrightarrow\cdots v_{j}^{\pm 1}v_{i}^{\pm 1}\cdots$ , provided $\{v_{i},v_{j}\}$ spans an edge of $\Gamma$ .

An element of $A(\Gamma)$ is nontrivial if and only if it cannot be reduced to the identity via applications of these two moves [5, 8, 14]. We say that $x$ is cyclically reduced if all cyclic permutations of $x$ are also freely reduced. The centralizer of $x$ is described by a theorem of Servatius [29]:

Theorem 3.2.

Suppose that $x$ is nontrivial, cyclically reduced, and has non-cyclic centralizer. Then there is a join $J=J_{1}*J_{2}*\cdots*J_{n}\subset\Gamma$ such that $x\in A(J)<A(\Gamma)$ , and such that $J_{i}$ does not decompose as a nontrivial join for $1\leq i\leq n$ . Moreover:

(1)

The element $x$ can be uniquely represented as a product $x_{1}x_{2}\cdots x_{n}$ where $x_{i}\in A(J_{i})$ .
(2)

Up to re-indexing, the centralizer of $x$ is given by

$\mathbb{Z}^{k}\times A(J_{k+1})\times\cdots\times A(J_{n}),$

where $x_{i}$ is nontrivial for $i\leq k$ and trivial for $i>k$ .

Let $J=J_{1}*J_{2}*\cdots*J_{n}$ be a join and let $v$ be a vertex in $J_{1}$ . Then $v$ is adjacent to each vertex of $J_{i}$ for $i\geq 2$ , whence it follows that the valence of $v$ is at least

\sum_{i=2}^{n}|J_{i}|.

The following consequence is now straightforward:

Corollary 3.3.

Let $N$ denote the maximum valence of a vertex in $\Gamma$ and let $R(x)$ denote the rank of the centralizer of a nontrivial element of $x\in A(\Gamma)$ . Then

N+1=\max_{1\neq x\in A(\Gamma)}R(x).

In Corollary 3.3, the rank of a group is the minimal cardinality of a set of generators.

Remark 3.4.

Note that Corollary 3.3 gives an intrinsic bound on valence of vertices in the defining graph of a right-angled Artin group without any reference to a set of generators.

3.3. Centralizers and $q$ –valence

Let $L$ be a fixed field. In this subsection we prove the following linear algebraic version of valence in a graph:

Lemma 3.5.

Let $V=H^{1}(A(\Gamma),L)$ , let $W=H^{2}(A(\Gamma),L)\}$ , and let $q$ denote the cup product pairing

\smile\colon H^{1}(A(\Gamma),L)\times H^{1}(A(\Gamma),L)\to H^{2}(A(\Gamma),L)

Then the $q$ –valence $d(V)$ coincides with the maximum valence of a vertex in $\Gamma$ .

Proof.

We write $d(\Gamma)$ for the maximum valence of a vertex in $\Gamma$ . Let

B=S=\{v_{1}^{*},\ldots,v_{|\mathrm{Vert}(\Gamma)|}^{*}\}

be the basis for $V$ furnished by Proposition 3.1. Then clearly

d(\Gamma)=\max_{s\in S}|\{b\in B\mid q(s,b)\neq 0\}|,

whence it follows that $d(V)\leq d(\Gamma)$ .

We now consider the reverse inequality. Note first that we need only consider sets $S$ which are bases for $V$ , since if $B$ is fixed and if $S\subset S^{\prime}$ then $d_{B}(S)\leq d_{B}(S^{\prime})$ .

Let $S$ be an arbitrary basis for $V$ , and let $v_{1}$ be the vertex of $\Gamma$ with highest valence. If $s\in S$ then we may write $s$ in terms of the basis $\{v_{1}^{*},\ldots,v_{|\mathrm{Vert}(\Gamma)|}^{*}\}$ . Since $S$ forms a basis for $V$ , there is some $s\in S$ such that the corresponding coefficient for $v_{1}^{*}$ is nonzero. We fix such an $s$ for the remainder of the proof.

Write $\{w_{1},\ldots,w_{k}\}$ for the vertices of $\Gamma$ which are adjacent to $v_{1}$ , with corresponding duals $\{w_{1}^{*},\ldots,w_{k}^{*}\}$ , and let $B$ be another arbitrary basis for $V$ . Observe first that $q(v_{1}^{*},w_{i}^{*})\neq 0$ for $\{1\leq i\leq k\}$ . Moreover, the set

\{q(v_{1}^{*},w_{i}^{*})\}_{1\leq i\leq k}

is linearly independent in $W$ . It follows that the set

\{q(s,w_{i}^{*})\}_{1\leq i\leq k}

is linearly independent in $W$ .

Thus, we may consider the linear map

q_{s}\colon V\to W

given by $q_{s}(v)=q(s,v)$ . Clearly this is a linear map and its image is a vector subspace of $W$ . The considerations of the previous paragraph show that the dimension of $q_{s}(V)$ is at least $k$ , which coincides with the valence of $v_{1}$ and hence with $d(\Gamma)$ . Suppose that there were fewer than $k$ elements $b\in B$ for which $q(s,b)\neq 0$ . Then $q_{s}(B)\subset W$ would span a subspace of dimension strictly less than $k$ . However, $B$ is a basis, so that the span of $q_{s}(B)$ coincides with $q_{s}(V)$ , which is a contradiction. Thus, we have that $d_{B}(S)\geq d(\Gamma)$ . Since $B$ and $S$ were arbitrary, we have $d(V)\geq d(\Gamma)$ . ∎

3.4. Pairing–connectedness

In this subsection, we show that pairing–connectedness, which was already shown to be implied by positive Cheeger constant $h_{V}>0$ by Proposition 2.2, is equivalent to the connectedness of $\Gamma$ under the assumptions

V=H^{1}(A(\Gamma),L),\quad W=H^{2}(A(\Gamma),L),\quad q=\smile.

Lemma 3.6.

Let $\Gamma$ be a finite simplicial graph, let $V=H^{1}(A(\Gamma),L)$ , and let $q$ be the cup product pairing on $V$ . The vector space $V$ is pairing–connected if and only if the graph $\Gamma$ is connected.

Proof.

Let $\{v_{1},\ldots,v_{n}\}$ be the vertices of $\Gamma$ , so that the dual vectors $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ form a basis for $V$ . Suppose that $\Gamma$ is not connected. Then after reindexing, we may write $B_{0}=\{v_{1}^{*},\ldots,v_{j}^{*}\}$ and $B_{1}=\{v_{j+1}^{*},\ldots,v_{n}^{*}\}$ with $j<n$ , and where there is no edge in $\Gamma$ of the form $\{v_{i},v_{k}\}$ with $i\leq j$ and $k>j$ . We let $V_{0}$ be the span of $B_{0}$ and $V_{1}$ be the span of $B_{1}$ . Note that $V=V_{0}\oplus V_{1}$ . It is clear that if $w_{0}\in V_{0}$ and $w_{1}\in V_{1}$ then $q(w_{0},w_{1})=0$ , so that $V$ is not pairing–connected.

Conversely, suppose that $\Gamma$ is connected, and suppose that $V\cong V_{0}\oplus V_{1}$ is an arbitrary nontrivial direct sum decomposition. We assume for a contradiction that for all pairs $w_{0}\in V_{0}$ and $w_{1}\in V_{1}$ , we have $q(w_{0},w_{1})=0$ . We argue by induction that either $V_{0}=0$ or $V_{1}=0$ , using a sequence $\{b_{1},\ldots,b_{m}\}$ of vertices of $\Gamma$ , such that each vertex of $\Gamma$ appears in this sequence, and such that for all $i<m$ we have $\{b_{i},b_{i+1}\}$ spans an edge of $\Gamma$ . We write $b_{i}^{*}\in V$ for the vector dual to the vertex $b_{i}$ . Note that it is possible for there to be repeats on the list $\{b_{1},\ldots,b_{m}\}$ , since $\Gamma$ may not contain a Hamiltonian path.

Before starting the induction, we explain the inductive step. Let $w_{0}\in V_{0}$ and $w_{1}\in V_{1}$ , and write

w_{0}=\sum_{i=1}^{n}\lambda_{i}v_{i}^{*},\quad w_{1}=\sum_{i=1}^{n}\mu_{i}v_{i}^{*}.

Suppose that $\{v_{i},v_{j}\}$ spans an edge in $\Gamma$ . By expanding the cup product $q(w_{0},w_{1})=0$ , we see that we must have $\lambda_{i}\mu_{j}=\lambda_{j}\mu_{i}$ . If these products are nonzero, it follows that the pairs $(\lambda_{i},\lambda_{j})$ and $(\mu_{i},\mu_{j})$ must satisfy a proportionality relation (i.e. there is a nonzero $\alpha$ such that $(\lambda_{i},\lambda_{j})=(\alpha\mu_{i},\alpha\mu_{j})$ ). The vector space $V$ is a free $L$ –module on $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ , so that there are vectors in $V$ whose coefficients do not satisfy this proportionality relation. Therefore there exist vectors

w_{0}^{\prime}=\sum_{i=1}^{n}\lambda_{i}^{\prime}v_{i}^{*}\in V_{0}\quad\textrm{or}\quad w_{1}^{\prime}=\sum_{i=1}^{n}\mu_{i}^{\prime}v_{i}^{*}\in V_{1}

such that $(\lambda_{i}^{\prime},\lambda_{j}^{\prime})$ is not proportional to $(\lambda_{i},\lambda_{j})$ or $(\mu_{i}^{\prime},\mu_{j}^{\prime})$ is not proportional to $(\mu_{i},\mu_{j})$ . Indeed, since $V$ is spanned by $V_{0}$ and $V_{1}$ , if there were no such vectors in both $V_{0}$ and $V_{1}$ then every vector in $V$ would satisfy this proportionality relation, which is not the case. We then see that either $q(w_{0}^{\prime},w_{1})\neq 0$ or $q(w_{0},w_{1}^{\prime})\neq 0$ , which contradicts the assumption that $q(w_{0},w_{1})=0$ for all $w_{0}\in V_{0}$ and $w_{1}\in V_{1}$ . It follows that $\lambda_{i}\mu_{j}=\lambda_{j}\mu_{i}=0$ .

We can now begin the induction. Suppose that $w_{0}\in V_{0}$ is expressed with respect to the basis $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ . After relabeling, we may assume $v_{1}=b_{1}$ and $v_{2}=b_{2}$ . Assume that the coefficient $\lambda_{1}$ of $v_{1}^{*}=b_{1}^{*}$ is nonzero; if no such vector exists then we simply choose one in $V_{1}$ and proceed in the following argument with the roles of $V_{0}$ and $V_{1}$ switched. Let $w_{1}\in V_{1}$ be similarly expressed, and suppose that the coefficient $\mu_{2}$ corresponding to $b_{2}^{*}$ is nonzero. Then we must have $\lambda_{1}\mu_{2}=\lambda_{2}\mu_{1}$ , and these products are both nonzero. The argument of the inductive step shows that since $V_{0}\oplus V_{1}=V$ , we cannot have $\lambda_{1}\mu_{2}=\lambda_{2}\mu_{1}\neq 0$ . It follows that $\mu_{2}=0$ . Since $w_{1}$ was arbitrary, the vanishing of this coefficient holds for all vectors in $V_{1}$ . Again using the fact that $V_{0}$ and $V_{1}$ span $V$ , there is a vector $w_{0}^{\prime}\in V_{0}$ which has a nonzero coefficient $\lambda_{2}^{\prime}$ for $b_{2}^{*}$ . Arguing symmetrically shows that the coefficient $\mu_{1}$ of $b_{1}^{*}$ vanishes for all vectors in $V_{1}$ .

By induction on $m$ and using the fact that each vertex of $\Gamma$ occurs on the list $\{b_{1},\ldots,b_{m}\}$ , it follows that if $w_{1}\in V_{1}$ then all coefficients of $w_{1}$ with respect to the basis $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ vanish, so that $V_{1}$ is the zero vector space. This contradicts the assumption that $V\cong V_{0}\oplus V_{1}$ was a nontrivial direct sum decomposition. ∎

4. Graph and vector space Cheeger constants

In this section we show that a vector space equipped with a vector space valued bilinear pairing can compute the Cheeger constant of a graph, which will allow us to establish Theorem 1.3 and its consequences.

4.1. Comparing Cheeger constants

The main technical result of this section is the following, which provides a precise correspondence between Cheeger constants in the combinatorial and linear algebraic contexts:

Theorem 4.1.

Suppose that $\Gamma$ is a connected simplicial graph and let $A(\Gamma)$ be the corresponding right-angled Artin group. Let $h_{\Gamma}$ denote the Cheeger constant of $\Gamma$ , and let $h_{V}$ denote the Cheeger constant of the triple $(V,W,q)$ , where $V=H^{1}(A(\Gamma),L)$ , where $W=H^{2}(A(\Gamma),L)$ , and where $q$ denotes the cup product. Then $h_{\Gamma}=h_{V}$ .

The proof of Theorem 4.1 is rather involved, and so will be broken up into several more manageable lemmata. We begin by proving that the Cheeger constant associated to a subspace $F\subset V$ generated by duals of the vertex generators is given by the Cheeger constant associated to the corresponding subgraph. To fix notation, let $\{v_{1},\ldots,v_{n}\}$ denote the vertices of $\Gamma$ , and let $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ be the corresponding dual generators of $V$ . If $B=\{v_{1},\ldots,v_{j}\}$ , we write $B^{*}=\{v_{1}^{*},\ldots,v_{j}^{*}\}$ and use $\partial B$ to denote the vertices $\Gamma$ which do not lie in $B$ but which are adjacent to vertices in $B$ .

Lemma 4.2.

Let $0\neq F\subset V$ be generated by $B^{*}=\{v_{1}^{*},\ldots,v_{j}^{*}\}$ . Then

h_{F}=\frac{|\partial B|}{|B|}.

Proof.

Recall that we use the notation $C$ for the orthogonal complement of $B^{*}$ with respect to $q$ . The subspace $C\subset V$ is generated by vertex duals $\{y_{1}^{*},\ldots,y_{m}^{*}\}$ , where for each $i$ either $y_{i}\notin B\cup\partial B$ or $y_{i}$ is an isolated vertex of $B$ (i.e. $y_{i}$ is not adjacent to any other vertex of $B$ ).

To see this, note that $\{y_{1}^{*},\ldots,y_{m}^{*}\}\subset C$ . Conversely, suppose that $x\in C$ and write

x=a_{1}v_{1}^{*}+\cdots+a_{n}v_{n}^{*},

where $a_{1}\neq 0$ . If $v_{1}$ is adjacent to a vertex $w\in B$ then clearly $q(x,w^{*})\neq 0$ , since the resulting cohomology class will be supported on the dual of the edge connecting $v_{1}$ and $w$ (see Subsection 3.1 for a discussion of the definition of support). It follows that if $x\in C$ then $v_{1}$ is either an isolated vertex of $B$ or $v_{1}\notin B\cup\partial B$ .

We now claim that

h_{F}=\frac{|\partial B|}{|B|}.

To establish this claim, note that $C\cap F$ is generated by the duals $\{v_{1}^{*},\ldots,v_{\ell}^{*}\}$ of singleton vertices of $B$ . Write $|\partial B|=k$ . It follows now that

\dim C-\dim(C\cap F)=n-|B\cup\partial B|=n-k-j.

We thus obtain the string of equalities

\frac{|\partial B|}{|B|}=\frac{k}{j}=\frac{n-j-(n-k-j)}{j}=\frac{\dim V-\dim F-\dim C+\dim(C\cap F)}{\dim F}=h_{F},

which establishes the lemma. ∎

The following lemma clearly implies Theorem 4.1.

Lemma 4.3.

Let $0\neq F\subset V$ be of dimension $j$ . Then there exists a subspace $F^{\prime}\subset V$ of dimension $j$ with a basis contained in $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ , and such that $h_{F^{\prime}}\leq h_{F}$ .

Observe that in order to establish Lemma 4.3, if we write $C^{\prime}$ for the complement of $F^{\prime}$ with respect to $q$ , it suffices to show that

\dim C-\dim(C\cap F)\leq\dim C^{\prime}-\dim(C^{\prime}\cap F^{\prime}).

Proving Lemma 4.3 is also rather complicated, so we will gather some preliminary results and terminology first. We will call a $j$ –tuple $\{v^{*}_{i_{1}},\ldots,v^{*}_{i_{j}}\}$ admissible if for each index $i_{k}$ , there is a vector $w_{i_{k}}$ contained in the linear span of

\{v_{1}^{*},\ldots,v_{n}^{*}\}\setminus\{v^{*}_{i_{1}},\ldots,v^{*}_{i_{j}}\}

so that the vectors of the form $f_{i_{k}}=v^{*}_{i_{k}}+w_{i_{k}}$ form a basis for $F$ . Such bases for $F$ will be called admissible bases. Note that if $\{v^{*}_{i_{1}},\ldots,v^{*}_{i_{j}}\}$ is admissible then the vectors $w_{i_{k}}$ are uniquely determined for $1\leq k\leq 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}^{*},\ldots,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\times j$ minor is invertible.

Let

E^{*}=\{v_{1}^{*},\ldots,v_{j}^{*}\}\subset\{v_{1}^{*},\ldots,v_{n}^{*}\}

be admissible, and let $E=\{v_{1},\ldots,v_{j}\}$ be the corresponding set of vertices. We write $\Gamma_{E}$ for the subgraph of $\Gamma$ spanned by $E$ , and $E_{0}$ for 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 $|E_{0}|$ 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 $\Gamma$ if necessary, we will fix a basis for $V$ now of the form

\{f_{1},\ldots,f_{j},v_{j+1}^{*},\ldots,v_{n}^{*}\},

where $f_{i}=v_{i}^{*}+w_{i}$ as before. Such a basis for $V$ will be called standard relative to $F$ , and $E^{*}$ will be the corresponding admissible tuple.

We will fix the following notation in the sequel. Suppose $F\subset V$ has dimension $j$ . If $\{f_{1},\ldots,f_{j},v_{j+1}^{*},\ldots,v_{n}^{*}\}$ is a standard basis of $V$ relative to $F$ , write $F^{\prime}$ for the span of $\{v_{1}^{*},\ldots,v_{j}^{*}\}$ , write $C^{\prime}$ for its orthogonal complement with respect to $q$ , and let $Y$ denote the span of $\{v_{j+1}^{*},\ldots,v_{n}^{*}\}$ .

We will in fact prove the following lemma, which implies Lemma 4.3.

Lemma 4.4.

If $F\subset V$ has dimension $j$ then there exists a standard basis

\{f_{1},\ldots,f_{j},v_{j+1}^{*},\ldots,v_{n}^{*}\}

of $V$ relative to $F$ such that if $x\in C$ and $F\cap C=0$ then $x\in C^{\prime}\cap Y$ , and if $F\cap C\neq 0$ then

x\in(C\cap F)+(C^{\prime}\cap Y).

Lemma 4.4 implies Lemma 4.3, since then

\dim C\leq\dim C^{\prime}-\dim(C^{\prime}\cap F^{\prime})+\dim(C\cap F).

We first establish it in the simpler cases where $\dim F=1$ and in the case where there exists an admissible basis for $F$ with $E_{0}=\emptyset$ .

Proof of Lemma 4.4 when $\dim F=1$ .

Clearly we may assume that $\dim V\geq 2$ . Suppose $F$ is the span of $a\in V$ . Observe that $F\subset C$ . We write $\{f_{1},v_{2}^{*},\ldots,v_{n}^{*}\}$ for a standard basis for $V$ relative to $F$ . We have that $a$ is a nonzero multiple of $f_{1}$ , and $F^{\prime}$ is the span of $v_{1}^{*}$ . If $x\in C$ then we may write

x=\lambda_{1}f_{1}+\sum_{i=2}^{n}\lambda_{i}v_{i}^{*}.

We write $w=x-\lambda_{1}f_{1}$ and we assume $\lambda_{m}\neq 0$ for some $m\geq 2$ . Note that $q(f_{1},x)=q(f_{1},w)$ . If $q(v_{1}^{*},v_{m}^{*})\neq 0$ then $q(f_{1},x)$ has $\lambda_{1}\lambda_{m}$ as the coefficient appearing before the vector dual to the edge $\{v_{1},v_{m}\}$ . So, if $x\in C$ then $q(v_{1}^{*},v_{m}^{*})=0$ , whence it follows that $v_{m}^{*}\in C^{\prime}$ . Since $m$ was chosen arbitrarily subject to the condition $\lambda_{m}\neq 0$ , we have that $w\in C^{\prime}\cap Y$ , where $Y$ is the span of $\{v_{2}^{*},\ldots,v_{n}^{*}\}$ . This establishes the lemma in this case. ∎

Proof of Lemma 4.4 when $E_{0}=\emptyset$ .

Let $\{f_{1},\ldots,f_{j},v_{j+1}^{*},\ldots,v_{n}^{*}\}$ be a standard basis relative to $F$ , where the admissible tuple $E^{*}$ satisfies $E_{0}=\emptyset$ . Each component of $\Gamma_{E}$ consists of at least two vertices. We write $\{F^{\prime},C^{\prime},Y\}$ as before. Let $x\in C$ be written as

\sum_{i=1}^{j}\lambda_{i}f_{i}+\sum_{i=j+1}^{n}\lambda_{i}v_{i}^{*}.

Suppose first that $\lambda_{m}\neq 0$ for some $m\leq j$ . The vertex $v_{m}\in E$ is adjacent to a vertex $v_{k}\in E$ , so that $q(\lambda_{m}f_{m},f_{k})\neq 0$ , whence it follows that $q(x,f_{k})\neq 0$ , contradicting the fact that $x\in C$ . We conclude that $\lambda_{m}=0$ for $m\leq j$ , so that we may write

x=\sum_{i=j+1}^{n}\lambda_{i}v_{i}^{*}.

Mimicking the proof in the case $\dim F=1$ , we have that $x\in C^{\prime}\cap Y$ , as desired. ∎

Now let us consider a standard basis

B=\{f_{1},\ldots,f_{k},f_{k+1},\ldots,f_{j},v_{j+1}^{*},\ldots,v_{n}^{*}\}

relative to $F$ , where the vertices in the admissible tuple $E$ with indices $1\leq i\leq k$ are precisely those which are not isolated in $\Gamma_{E}$ . We remind the reader that we assume here and henceforth that $B$ is chosen in such a way that $|E_{0}|$ is minimized.

By the proofs of the cases of Lemma 4.4 given so far, we may assume that $k<j$ . Let $x\in C$ as before, and write

x=\sum_{i=1}^{j}\lambda_{i}f_{i}+\sum_{i=j+1}^{k}\lambda_{i}v_{i}^{*}.

As argued in the proof in the case $E_{0}=\emptyset$ , we have that $\lambda_{m}=0$ for $m\leq k$ .

Lemma 4.5.

Let $B$ be as above. If $k+1<m\leq j$ then $q(f_{k+1},f_{m})=0$ .

Proof.

Write

f_{k+1}=v_{k+1}^{*}+\sum_{s=j+1}^{n}\mu^{k+1}_{s}v_{s}^{*},\quad f_{m}=v_{m}^{*}+\sum_{t=j+1}^{n}\mu^{m}_{t}v_{t}^{*}.

By assumption, we have that $q(v_{k+1}^{*},v_{m}^{*})=0$ , since the corresponding vertices are isolated. If $q(f_{k+1},f_{m})\neq 0$ then one of the three following cases must occur.

(1)

The coefficient $\mu_{s}^{k+1}$ is nonzero for a suitable $s>j$ with $q(v_{s}^{*},v_{m}^{*})\neq 0$ .
(2)

The coefficient $\mu_{t}^{m}$ is nonzero for a suitable $t>j$ with $q(v_{k+1}^{*},v_{t}^{*})\neq 0$ .
(3)

We have $\mu_{s}^{k+1}\mu_{t}^{m}\neq\mu_{t}^{k+1}\mu_{s}^{m}$ for suitable indices $s,t>j$ with $s\neq t$ and $q(v_{s}^{*},v_{t}^{*})\neq 0$ .

In the first of these possibilities, we write

E^{\prime}=(E\setminus\{v_{k+1}\})\cup\{v_{s}\}.

We claim that $(E^{\prime})^{*}$ remains admissible. This is straightforward to check. Indeed, we record an $n\times n$ matrix $M$ whose columns are labelled by $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ , whose rows are labelled by $\{f_{1},\ldots,f_{j},v_{j}^{*},\ldots,v_{n}^{*}\}$ , and whose entries are the $v_{\ell}^{*}$ coefficient $m_{i,\ell}$ of the $i^{th}$ row basis element. We have that the $j\times j$ block in the upper left hand corner is the identity matrix. Exchanging $v_{k+1}$ for $v_{s}$ corresponds to switching the $(k+1)^{st}$ and $s^{th}$ columns of $M$ . The $(k+1)^{st}$ row of the $s^{th}$ column reads $\mu_{s}^{k+1}\neq 0$ . Thus after exchanging these two columns, the upper left hand $j\times j$ block remains invertible. Moreover, $q(v_{s}^{*},v_{m}^{*})\neq 0$ , whence $v_{s}$ and $v_{m}$ are no longer isolated vertices. It follows that $|E^{\prime}_{0}|<|E_{0}|$ , which contradicts the minimality of $|E_{0}|$ . 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^{\prime\prime}=E\setminus\{v_{k+1},v_{m}\}\cup\{v_{s},v_{t}\}$ . It suffices to show that $(E^{\prime\prime})^{*}$ is admissible, since $v_{s}$ and $v_{t}$ are adjacent in $\Gamma$ under the assumptions of the third item. We switch the columns with labels $k+1$ and $s$ , and with labels $m$ and $t$ . Since $\mu_{s}^{k+1}\mu_{t}^{m}\neq\mu_{t}^{k+1}\mu_{s}^{m}$ , the determinant of the upper left hand $j\times j$ block 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 $B$ to obtain one with more advantageous features. Specifically, we will transform $B$ into a standard basis $B^{k+1}$ such that if $x\in C$ is expressed with respect to $B^{k+1}$ , then the first $k+1$ coefficients of $x$ must vanish. To this end, suppose $f_{r}\notin C$ for $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(f_{m},f_{k+1})\neq 0$ . Since $v_{k+1}$ is isolated, we have $q(v_{k+1}^{*},v_{m}^{*})=0$ . Again we write

f_{k+1}=v_{k+1}^{*}+\sum_{s=j+1}^{n}\mu^{k+1}_{s}v_{s}^{*},\quad f_{m}=v_{m}^{*}+\sum_{t=j+1}^{n}\mu^{m}_{t}v_{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 $B$ to obtain a new standard basis $B^{k+1}$ as follows, according to the reason for which $q(f_{m},f_{k+1})\neq 0$ . Namely:

(1)

If $\mu_{t}^{m}\neq 0$ for some index $t$ with $q(v_{k+1}^{*},v_{t}^{*})\neq 0$ , then we set $B^{k+1}=B$ .
(2)

If the previous item does not hold but if there exists an index $s$ with $\mu_{s}^{k+1}\neq 0$ and $q(v_{m}^{*},v_{s}^{*})=0$ then we substitute $v_{s}^{*}$ for $v_{k+1}^{*}$ to obtain an admissible tuple as in Lemma 4.5. We then set $B^{k+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 $\mu_{s}^{k+1}\mu_{t}^{m}$ and $\mu_{t}^{k+1}\mu_{s}^{m}$ is nonzero for suitable choices of indices $s$ and $t$ with $q(v_{s}^{*},v_{t}^{*})\neq 0$ . We substitute $v_{s}^{*}$ for $v_{k+1}^{*}$ . As before, the resulting tuple is admissible. We then write $B^{k+1}$ for the corresponding standard basis.

As before, these exchanges do not change the size of $|E_{0}|$ . We now write

B^{k+1}=\{f_{1}^{k+1},\ldots,f_{j}^{k+1},e_{j+1},\ldots,e_{n}\},

where indices have been renumbered after any substitutions. Note the following.

Observation 4.6.

For $r\leq j$ and $r\neq k+1$ , we have that $f_{r}^{k+1}$ differs from $f_{r}$ by a (possibly zero) multiple of $f_{k+1}$ , and $f_{k+1}^{k+1}=f_{k+1}$ .

If $x\in C$ , we write it with respect to this new basis, so that

x=\sum_{i=1}^{j}\lambda_{i}^{k+1}f_{i}^{k+1}+\sum_{i=j+1}^{n}\lambda_{i}^{k+1}v_{i}^{*}.

The previous considerations show that $\lambda_{i}^{k+1}=0$ for $i\leq k$ .

Lemma 4.7.

The following hold.

(1)

If $x\in C$ is as above, then $\lambda^{k+1}_{k+1}=0$ .
(2)

For $k+1\leq r,s\leq j$ , we have $q(f_{r}^{k+1},f_{s}^{k+1})=0$ .

Proof.

Suppose now that $\lambda_{k+1}^{k+1}\neq 0$ , and consider the index $m$ as before which was chosen so that $q(f_{m},f_{k+1})\neq 0$ . Then for a suitable constant $\alpha$ , we have

q(f_{m}^{k+1},f_{k+1}^{k+1})=q(f_{m}+\alpha f_{k+1},f_{k+1})=q(f_{m},f_{k+1})\neq 0.

Moreover, $q(f_{m}^{k+1},f_{k+1}^{k+1})$ is supported on the dual vector to the edge $\{v_{m},v_{k+1}\}$ or $\{v_{t},v_{k+1}\}$ (which was the edge $\{v_{m},v_{s}\}$ or the edge $\{v_{t},v_{s}\}$ before the vertices were re-indexed in the definition of $B^{k+1}$ ). No other summand making up the vector $x$ (i.e. $\lambda_{i}f_{i}^{k+1}$ for $i\geq k+2$ or $\lambda_{i}^{k+1}v_{i}^{*}$ for $i\geq j+1$ ) is supported on $v_{k+1}^{*}$ . It follows that if $\lambda_{k+1}^{k+1}\neq 0$ then $q(x,f_{m}^{k+1})\neq 0$ , which is a contradiction. We may therefore conclude that $\lambda^{k+1}_{k+1}=0$ .

For the second claim of the lemma, note that for

k+1\leq r,s\leq j,

we have $q(f_{r},f_{s})=0$ by Lemma 4.5, which implies that $q(f_{r}^{k+1},f_{s}^{k+1})=0$ as well since both of these vectors differ from $f_{r}$ and $f_{s}$ respectively by a multiple of $f_{k+1}$ . ∎

Now suppose that $f_{i}^{k+1}\notin C$ for some $k+2\leq i\leq j$ , and without loss of generality we may assume that $i=k+2$ . Repeating the procedure for the construction of $B^{k+1}$ , we may add multiples of $f_{k+2}^{k+1}$ to the basis vectors which are distinct from $f_{k+2}^{k+1}$ itself in order to obtain a new basis

B^{k+2}=\{f_{1}^{k+2},\ldots,f_{j}^{k+2},v_{j+1}^{*},\ldots,v_{n}^{*}\}.

Since $q(f_{k+2}^{k+1},f_{i}^{k+2})=0$ for $i\geq k+1$ , we must have that $q(f_{r}^{k+1},f_{k+2}^{k+1})\neq 0$ for some $r\leq k$ . As before, if $x\in C$ , we express $x$ in this basis with coefficients $\{\lambda_{i}^{k+2}\}_{1\leq i\leq n}$ and observe that the coefficients satisfy $\lambda_{i}^{k+2}=0$ for $i\leq k$ and $\lambda^{k+2}_{k+2}=0$ . It is conceivable that in the course of this modification we may find that $\lambda_{k+1}^{k+2}\neq 0$ , a conclusion which we wish to rule out.

Lemma 4.8.

If $x\in C$ is expressed with respect to the basis $B^{k+2}$ , then we have $\lambda^{k+2}_{k+1}=0$ .

Proof.

We consider a vector $f_{m}^{k+1}$ which satisfies $q(f_{m}^{k+1},f_{k+1}^{k+1})\neq 0$ , and for suitable constants $\alpha$ and $\beta$ , we obtain expressions

f_{m}^{k+2}=f_{m}^{k+1}+\alpha f_{k+2}^{k+1},\qquad f_{k+1}^{k+2}=f_{k+1}^{k+1}+\beta f_{k+2}^{k+1}.

Computing, we have

q(f_{m}^{k+2},f_{k+1}^{k+2})=q(f_{m}^{k+1},f_{k+1}^{k+1})+\beta q(f_{m}^{k+1},f_{k+2}^{k+1}),

using the orthogonality of $f_{k+1}^{k+1}$ and $f_{k+2}^{k+1}$ .

It follows that $q(f_{m}^{k+2},f_{k+1}^{k+2})$ is supported on the vector dual to the edge $\{v_{k+1},v_{r}\}$ for a suitable $r$ , as this was already true of $q(f_{m}^{k+1},f_{k+1}^{k+1})$ . Then, as we argued for $B^{k+1}$ in Lemma 4.7, we have that $\lambda^{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 $V$ and corresponding admissible tuples which we write as

\{B^{k+2},B^{k+3},\ldots\},\qquad\{(E^{k+2})^{*},(E^{k+3})^{*},\ldots\},

which have the property that if $x\in C$ is written with respect to the basis $B^{k+s}$ then the coefficients $\lambda^{k+s}_{\ell}$ of $f_{\ell}^{k+s}$ are trivial for $\ell\leq k+s$ . We are able to construct $B^{k+s+1}$ from $B^{k+s}$ precisely when there is an index $k+s\leq i\leq j$ such that $f_{i}^{k+s}\notin C$ . Since $F$ is finite dimensional, the sequence will terminate after finitely many terms. This will happen either for $k+s=j$ or for some $s<j-k$ .

In the first case, we see that $C\cap F=0$ . In the second case, the basis vectors $\{f_{k+s+1}^{k+s},\ldots,f_{j}^{k+s}\}$ are orthogonal to $F$ . To complete the proof of the lemma, we set $f_{i}=f_{i}^{k+s}$ for $1\leq i\leq j$ , and $F^{\prime}$ is the span of the associated admissible tuple $(E^{k+s})^{*}$ . As in the statement of the lemma, we write $Y$ for the span of $\{v_{j+1}^{*},\ldots,v_{n}^{*}\}$ . If $x\in C$ then

x=\sum_{i=k+s+1}^{j}\lambda_{i}^{k+s}f_{i}+y

for a suitable vector $y\in Y$ . Note that by assumption, we have $x-y\in C$ , which implies that $y\in C$ . This shows that $y\in C^{\prime}\cap Y$ , since $q(y,f_{i})=0$ for all $i\leq j$ and hence $q(y,v_{i}^{*})=0$ for $i\leq j$ . It follows that if $C\cap F=0$ then $x=y\in C^{\prime}\cap Y$ , and otherwise that $x\in(C\cap F)+(C^{\prime}\cap Y)$ , which completes the proof. ∎

4.2. Proof of the main results

Theorem 1.2 and Theorem 1.3 now follow almost immediately. The size of the set of vertices of $\Gamma_{i}$ tending to infinity is equivalent to the dimension of $V_{i}=H^{1}(A(\Gamma))$ tending to infinity, over any field. Bounded $q_{i}$ –valence of $V_{i}$ , bounded valence of $\Gamma_{i}$ , and bounded centralizer rank in $A(\Gamma)$ are all equivalent by Corollary 3.3 and Lemma 3.5. Finally, Theorem 4.1 implies that the Cheeger constant of $\Gamma_{i}$ is equal to the Cheeger constant of the triple $(H^{1}(A(\Gamma)),H^{2}(A(\Gamma)),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(\Gamma)$ in each dimension is determined by the corresponding number of cells in the flag complex of $\Gamma$ (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).

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 $\{\Gamma_{i}\}_{i\in\mathbb{N}}$ be a family of finite connected simplicial graphs which form a graph expander and let $L$ be an arbitrary field. We will write

V_{i}=H^{1}(A(\Gamma_{i}),L),\quad W_{i}=H^{2}(A(\Gamma_{i}),L),\quad q_{i}=\smile,

where $\smile$ denotes the cup product in the cohomology ring of the corresponding group. For each $i$ , we choose an arbitrary vertex $v^{i}$ of $\Gamma_{i}$ . We set $V_{i}^{\prime}=V_{i}$ , and we let $W_{i}=W\oplus L$ , where the summand $L$ is generated by a vector $z_{i}^{*}$ . We set $q_{i}^{\prime}=q_{i}\oplus q_{0,i}$ , where $q_{0,i}((v^{i})^{*},(v^{i})^{*})=z_{i}^{*}$ , and where $q_{0,i}$ vanishes on inputs of all other basis vectors arising from duals of vertices, in both arguments. That is, let $\{v_{1}^{i},\ldots,v_{n}^{i}\}$ be the vertices of $\Gamma_{i}$ , and without loss of generality we may assume that $v^{i}=v_{1}^{i}$ . We set $q_{0,i}((v_{j}^{i})^{*},(v_{k}^{i})^{*})=0$ unless both $v_{j}^{i}$ and $v_{k}^{i}$ are equal to $v_{1}^{i}$ , and we extend by bilinearity.

Proposition 5.1.

If $\mathcal{V}^{\prime}=\{(V_{i}^{\prime},W_{i}^{\prime},q_{i}^{\prime})\}_{i\geq 0}$ is as above then:

(1)

The family $\mathcal{V}^{\prime}$ is a vector space expander.
(2)

The family $\mathcal{V}^{\prime}$ 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 $\{\Lambda_{i}\}_{i\in\mathbb{N}}$ such that

V_{i}^{\prime}=H^{1}(A(\Lambda_{i}),L),\quad W_{i}^{\prime}=H^{2}(A(\Lambda_{i}),L),\quad q_{i}^{\prime}=\smile.

Proof of Proposition 5.1.

Since $V_{i}^{\prime}=V_{i}$ , we have that $\dim V_{i}^{\prime}\to\infty$ . Now consider $q_{i}^{\prime}$ –valence, which we denote by $d_{i}$ , and we compare with the graph valence $d(\Gamma_{i})$ of $\Gamma_{i}$ . By setting $B=S=(\mathrm{Vert}(\Gamma_{i}))^{*}$ in the definition of $q_{i}^{\prime}$ –valence, we see that $d_{i}(V)\leq d(\Gamma_{i})+1$ . Thus, $\mathcal{V}^{\prime}$ has uniformly bounded valence. For each $i$ , the vector space $V_{i}^{\prime}$ is already pairing–connected with respect to the pairing $q_{i}$ , and $q_{i}(v,w)\neq 0$ implies $q_{i}^{\prime}(v,w)\neq 0$ , so that $V_{i}^{\prime}$ is pairing–connected with respect to the pairing $q_{i}^{\prime}$ .

We now need to estimate the Cheeger constants of $\mathcal{V}^{\prime}$ . We suppress the $i$ index, and write $\{v_{1}^{*},\ldots,v_{n}^{*}\}$ for a basis of $V^{\prime}$ consisting of dual vectors of vertices of $\Gamma$ . We assume $v_{1}$ to be the distinguished vertex of $\Gamma$ such that $q_{0}(v_{1}^{*},v_{1}^{*})\neq 0$ . Let $0\neq F\subset V^{\prime}$ be a subspace of dimension at most $(\dim V^{\prime})/2$ , and let $h_{0}$ be the infimum of the Cheeger constants of the family $\mathcal{V}^{\prime}$ with respect to $q$ , the usual cup product. We denote by $C_{q}$ the orthogonal complement of $F$ with respect to $q$ , by $C_{0}$ the orthogonal complement of $F$ with respect to $q_{0}$ , and by $C$ the orthogonal complement of $F$ with respect to $q^{\prime}$ . Clearly, $C=C_{q}\cap C_{0}$ .

Now, let $f\in F$ be written as

f=\sum_{i=1}^{n}\mu_{i}v_{i}^{*},

and let $x\in V$ be written as

x=\sum_{i=1}^{n}\lambda_{i}v_{i}^{*}.

It follows by definition that $q_{0}(v_{i}^{*},x)=0$ for $i\neq 1$ , so that $q_{0}(f,x)=\lambda_{1}\mu_{1}$ . Thus, the span of $\{v_{2}^{*},\ldots,v_{n}^{*}\}$ is always contained in $C_{0}$ , and consequently $C_{0}$ has dimension either $n$ or $n-1$ . Thus, $\dim C$ is either equal to $\dim C_{q}$ or $\dim C_{q}-1$ . Similarly, $x\in C\cap F$ if and only if $x\in C_{q}\cap C_{0}\cap F$ , so that $\dim(C\cap F)$ is either equal to $\dim(C_{q}\cap F)$ or $\dim(C_{q}\cap F)-1$ .

Suppose that $\dim(C\cap F)=\dim(C_{q}\cap F)-1$ . Then $C\neq C_{q}$ , so that $\dim C=\dim C_{q}-1$ . In this case,

\dim C-\dim(C\cap F)=\dim C_{q}-1-(\dim(C_{q}\cap F)-1)=\dim C_{q}-\dim(C_{q}\cap F).

It follows that $\dim C-\dim(C\cap F)\leq\dim C_{q}-\dim(C_{q}\cap F)$ , and the difference between these is at most $1$ . Writing $N=\dim V^{\prime}-\dim F$ , the Cheeger constant of $F$ satisfies

h_{F}=\frac{N-\dim C+\dim(C\cap F)}{\dim F}\geq\frac{N-\dim C_{q}+\dim(C_{q}\cap F)}{\dim F}.

This proves that the Cheeger constant of $\mathcal{V}^{\prime}$ is bounded away from zero, which proves that $\mathcal{V}^{\prime}$ is a vector space expander family.

To see that $\mathcal{V}^{\prime}$ does not arise from a graph expander family, we note that the cup product satisfies $v_{1}^{*}\smile v_{1}^{*}=0$ , and $q^{\prime}$ is constructed so that $q^{\prime}(v_{1}^{*},v_{1}^{*})\neq 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.

Acknowledgements

The authors thank A. Jaikin and A. Lubotzky for helpful comments, and are grateful to the anonymous referee for helpful corrections and suggestions. Ramón Flores is supported by FEDER-MEC grant MTM2016-76453-C2-1-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.

References

[1] Noga Alon, Eigenvalues and expanders, vol. 6, 1986, Theory of computing (Singer Island, Fla., 1984), pp. 83–96. MR 875835
[2] Jean Bourgain, Expanders and dimensional expansion, C. R. Math. Acad. Sci. Paris 347 (2009), no. 7-8, 357–362. MR 2537230
[3] Jean Bourgain and Amir Yehudayoff, Expansion in ${\rm SL}_{2}(\mathbb{R})$ and monotone expanders, Geom. Funct. Anal. 23 (2013), no. 1, 1–41. MR 3037896
[4] Noel Brady and John Meier, Connectivity at infinity for right angled Artin groups, Trans. Amer. Math. Soc. 353 (2001), no. 1, 117–132. MR 1675166
[5] P. Cartier and D. Foata, Problèmes combinatoires de commutation et réarrangements, Lecture Notes in Mathematics, No. 85, Springer-Verlag, Berlin-New York, 1969. MR 0239978
[6] Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren, Cryptographic hash functions from expander graphs, J. Cryptology 22 (2009), no. 1, 93–113. MR 2496385
[7] Ruth Charney, An introduction to right-angled Artin groups, Geom. Dedicata 125 (2007), 141–158. MR 2322545
[8] John Crisp, Eddy Godelle, and Bert Wiest, The conjugacy problem in subgroups of right-angled Artin groups, J. Topol. 2 (2009), no. 3, 442–460. MR 2546582
[9] Michael W. Davis, The cohomology of a Coxeter group with group ring coefficients, Duke Math. J. 91 (1998), no. 2, 297–314. MR 1600586
[10] Carl Droms, Isomorphisms of graph groups, Proc. Amer. Math. Soc. 100 (1987), no. 3, 407–408. MR 891135
[11] Ramón Flores, Delaram Kahrobaei, and Thomas Koberda, Algorithmic problems in right-angled Artin groups: complexity and applications, J. Algebra 519 (2019), 111–129. MR 3874519
[12] by same author, An algebraic characterization of $k$ –colorability, Proc. Amer. Math. Soc. 149 (2021), no. 5, 2249–2255. MR 4232214
[13] Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, and David Zuckerman, Security preserving amplification of hardness, 31st Annual Symposium on Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990), IEEE Comput. Soc. Press, Los Alamitos, CA, 1990, pp. 318–326. MR 1150704
[14] Susan Hermiller and John Meier, Algorithms and geometry for graph products of groups, J. Algebra 171 (1995), no. 1, 230–257. MR 1314099 (96a:20052)
[15] Susan Hermiller and Zoran Šunić, Poly-free constructions for right-angled Artin groups, J. Group Theory 10 (2007), 117–138. MR 2288463
[16] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bull. Amer. Math. Soc. (N.S.) 43 (2006), no. 4, 439–561. MR 2247919
[17] Craig Jensen and John Meier, The cohomology of right-angled Artin groups with group ring coefficients, Bull. London Math. Soc. 37 (2005), no. 5, 711–718. MR 2164833
[18] Mark Kambites, On commuting elements and embeddings of graph groups and monoids, Proc. Edinb. Math. Soc. (2) 52 (2009), no. 1, 155–170. MR 2475886
[19] Sang-Hyun Kim and Thomas Koberda, Embeddability between right-angled Artin groups, Geom. Topol. 17 (2013), no. 1, 493–530. MR 3039768
[20] by same author, Free products and the algebraic structure of diffeomorphism groups, J. Topol. 11 (2018), no. 4, 1054–1076. MR 3989437
[21] Thomas Koberda, Geometry and combinatorics via right-angled Artin groups, preprint, arXiv:2103.09342.
[22] by same author, Right-angled Artin groups and a generalized isomorphism problem for finitely generated subgroups of mapping class groups, Geom. Funct. Anal. 22 (2012), no. 6, 1541–1590. MR 3000498
[23] Emmanuel Kowalski, An introduction to expander graphs, Cours Spécialisés [Specialized Courses], vol. 26, Société Mathématique de France, Paris, 2019. MR 3931316
[24] Alexander Lubotzky, Discrete groups, expanding graphs and invariant measures, Modern Birkhäuser Classics, Birkhäuser Verlag, Basel, 2010, With an appendix by Jonathan D. Rogawski, Reprint of the 1994 edition. MR 2569682
[25] by same author, High dimensional expanders, Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, World Sci. Publ., Hackensack, NJ, 2018, pp. 705–730. MR 3966743
[26] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak, Ramanujan graphs, Combinatorica 8 (1988), no. 3, 261–277. MR 963118
[27] Alexander Lubotzky and Efim Zelmanov, Dimension expanders, J. Algebra 319 (2008), no. 2, 730–738. MR 2381805
[28] Lucas Sabalka, On rigidity and the isomorphism problem for tree braid groups, Groups Geom. Dyn. 3 (2009), no. 3, 469–523. MR 2516176
[29] Herman Servatius, Automorphisms of graph groups, J. Algebra 126 (1989), no. 1, 34–60. MR 1023285 (90m:20043)

Expanders and right-angled Artin groups

Abstract.

1. Introduction

Proposition 1.1 (cf. Theorem 4.1).

Theorem 1.2.

Theorem 1.3.

2. Graph and vector space expanders

2.1. Graph expander families

2.2. Vector space expander families

2.2.1. The Cheeger constant

2.2.2. The qq–valence of a vector space

2.2.3. Pairing–connectedness

2.2.4. Defining vector space expanders

Definition 2.1.

Proposition 2.2.

Proof.

3. Cohomology, qq–valence and pairing–connectedness

3.1. The cohomology ring of a right-angled Artin group

Proposition 3.1.

3.2. Centralizers in right-angled Artin groups

Theorem 3.2.

Corollary 3.3.

Remark 3.4.

3.3. Centralizers and qq–valence

Lemma 3.5.

Proof.

3.4. Pairing–connectedness

Lemma 3.6.

Proof.

4. Graph and vector space Cheeger constants

4.1. Comparing Cheeger constants

Theorem 4.1.

Lemma 4.2.

Proof.

Lemma 4.3.

Lemma 4.4.

Proof of Lemma 4.4 when dimF=1\dim F=1.

Proof of Lemma 4.4 when E0=∅E_{0}=\emptyset.

Lemma 4.5.

Proof.

Observation 4.6.

Lemma 4.7.

Proof.

Lemma 4.8.

Proof.

Proof of Lemma 4.4.

4.2. Proof of the main results

4.3. Generalizations to higher dimension

5. A vector space expander family that does not arise from a graph expander family

Proposition 5.1.

Proof of Proposition 5.1.

Acknowledgements

References

2.2.2. The $q$ –valence of a vector space

3. Cohomology, $q$ –valence and pairing–connectedness

3.3. Centralizers and $q$ –valence

Proof of Lemma 4.4 when $\dim F=1$ .

Proof of Lemma 4.4 when $E_{0}=\emptyset$ .