Borel chromatic numbers and a result of Palamourdas

Let’s say you have a graph G=(V,E).  Here we don’t want loops or multiple edges.  You may or may not want the edges to be directed.  It doesn’t really matter for this post, which will be about the chromatic number of G.  Recall that a coloring of G is a map c:V\rightarrow X such that if (v_0,v_1)\in E then c(v_0)\neq c(v_1).  The minimum cardinality of a space X such that c:V\rightarrow X is a coloring is called the chromatic number of G and generally denoted \chi(G).  It’s a well-studied notion.

You could put restrictions on the sort of colorings you’ll allow.  In descriptive set theory, we like to talk about colorings with some sort of “niceness” restrictions, like measurability, Baire measurability (meaning the inverse image of every open set has the property of Baire), or just Borelness.  Of course this sort of thing only makes sense if V and X have the appropriate structure (i.e. are measure spaces, Baire topological spaces, or standard Borel spaces).  You’d also want the edge relation to be sufficiently nice (say Borel), since otherwise trivial issues can arise.  So assume these things as necessary.  Then you can define the measurable (Baire measurable, Borel) chromatic number as above.  We’ll be concerned mainly with the Borel chromatic number here, which we write \chi_B(G).

Why bother?  Maybe it’s best to start with a striking fact.

Theorem (Kechris, Solecki, Todorcevic): There is an acyclic graph G (so \chi(G)=2) with \chi_B(G)>\aleph_0.

A couple of remarks.  First, they actually show that the Baire measurable chromatic number of this G is >\aleph_0, and since every Borel map is Baire measurable, you get the above result.  They also mention that Thomas had shown earlier that there is a bipartite (but not acyclic) graph with \chi_B(G)>\aleph_0 (this time using measure), so the difference between the two types of chromatic number wasn’t unnoticed before.

Think about how you would 2-color an acyclic graph.  (Let’s say the colors are R and B.) You would pick a vertex, color it R, color its neighbors B, color their neighbors R, etc.  (Of course you would have to do this in each connected component of G.)  The acyclicity of G ensures that this is a coloring.  But notice that the first thing you have to do is make a choice of vertex, and when there are infinitely many connected components of G, this would seem to require the Axiom of Choice.  The above theorem more or less confirms this suspicion: you can’t do this in a Borel way, which to descriptive set theorists means you have to use the Axiom of Choice.  (Technically, this is perhaps a bit strong, but not much.  At the very least, we know it doesn’t increase the consistency strength of ZF+dependent choice to also assume that every set of reals is Baire measurable, so if you can’t do something in a Baire measurable way, you really do need Choice!)

So there’s one reason to care about these restricted colorings: it gives you insight into when the Axiom of Choice is necessary.  Contrary to popular belief, however, logicians aren’t particularly obsessed with the Axiom of Choice.  Instead, we think of “Borel” as a synonym for “explicit” (there are reasons related to definability that provide some justification for this), and everybody is interested when things can be done explicitly, right?  Another reason (which would take me pretty far on a tangent to explain fully) is that these chromatic numbers are an area where we can actually tease apart distinctions between the measurable, Baire measurable, and Borel contexts, and this actually turns out to be somewhat tricky in general.

At this point, it is probably reasonable to ask when one can do things in a Borel way.  Here’s an example.

Theorem (KST): If there is a k\in\mathbb{N} such that every vertex in G has degree \leq k, then \chi_B(G)\leq k+1.

This is really the best you could do even for \chi(G), since it covers the case of complete graphs on k+1 vertices and disjoint unions thereof.  The result is not obvious, but not too hard.  Some basic descriptive set theory results allow one to prove that such a graph has \chi_B(G)\leq\aleph_0.  Then you can do the standard algorithm for this sort of thing, by which I mean the following:

We know we have a Borel \aleph_0-coloring of G, say with colors c_0,c_1,c_2,\ldots.  We want to find a Borel (k+1)-coloring, say with colors 0,1,\ldots,k.  We begin by assigning all of the vertices colored c_0 the color 0.  Then we look at the vertices colored c_1 and assign them the least color possible, so they will be colored 0 unless they have a neighbor which was initially colored c_0.  And so on and so forth inductively.  Since each vertex has k neighbors, there will always be a color from 0,\ldots,k available for any vertex you look at in this process.  Thus after completing the induction, G has been (k+1)-colored.

By the way, this is Borel.  Technically you want to appeal to the Feldman-Moore theorem to ensure that quantifying over a vertex’s neighbors isn’t causing you problems (there are only finitely many, it shouldn’t, right?), but you should just think, “That’s an explicit algorithm, so it must be Borel.”  Note the difference between this and the “algorithm” for coloring an acyclic graph.  There was something which wasn’t explicit, and that was where to start coloring.  That’s why Choice was necessary, to find a starting point.  But in this case, we have a starting point: using a coloring we already knew existed we had a set of vertices to begin our algorithm on, those that were initially colored c_0.  This is a common feature of arguments in Borel combinatorics (especially when the graphs are locally countable and so Feldman-Moore is available): if you can find a way to get started which is Borel, then often old proofs of coloring properties can be carried out in a Borel way.  We’ll see this idea put to use again in a minute.

Graphs generated by functions

Suppose we have a (let’s say finite) set of functions \{f_1,\ldots,f_n\} such that each f_i is a function from X to X, where X is a Polish space (or just a standard Borel space).  Then there is a natural way to define a (directed) graph G_{\{f_1,\ldots ,f_n\}} with vertex set X:

(x,y) \in G_{\{f_1,\ldots ,f_n\}} iff there is some f_i such that f_i(x)=y.

This is something like the Schreier graph (as the term is used in Definition 2 here) associated to the semigroup generated by \{f_1,\ldots,f_n\}, acting in the obvious way, though I’ve only seen the term “Schreier graph” used in the context of group actions, so there may be a different term when we’ve just got a semigroup action.  If the f_i are all Borel, then the edge relation of G_{\{f_1,\ldots ,f_n\}} is Borel as well, so we’re in our desired context.  We’ll go ahead and call these graphs “Schreier graphs” (in quotes, just to be safe).

Kechris, Solecki, and Todorcevic proved a number of results about “Schreier graphs”.  The main one of interest here is the following.

Theorem (KST): If F\colon X\to X is Borel, then \chi_B(G_{\{F\}})\in\{1,2,3,\aleph_0\}.  Each value is possible.

It’s a nice proof, but I won’t get into it here.  Note that \chi(G_{\{F\}})\leq 3 (you can make an odd cycle this way, so 3 colors may be necessary), so the theorem essentially says that while sure, in the Borel context you may need infinitely many colors to color such a graph, if you only need finitely many, then the bound you get for number of colors possibly needed is the same as in the non-Borel context!

What if you use more functions?  The above result immediately gives that \chi_B(G_{\{f_1,\ldots,f_n\}})\leq 3^n whenever it is finite (just think of G_{\{f_1,\ldots,f_n\}} as n G_{\{F\}}s with the same vertex set).  On the other hand, one can show that \chi(G_{\{f_1,\ldots,f_n\}})\leq 2n+1.  This raises the question: can this be matched in the Borel case?

A result of Palamourdas

In 2012 at UCLA, Palamourdas wrote a thesis attacking this problem.  As far as I know, his results were not published in any journal, though the thesis is available online.  I’m going to discuss the following result from his thesis (Theorem 3.1, to be precise).

Theorem (Palamourdas): Suppose \{f_1,\ldots,f_n\} are Borel and commute (i.e. f_i(f_j(x))=f_j(f_i(x)) for all 1\leq i,j\leq n.  If \chi_B(G_{\{f_1,\ldots,f_n\}})<\aleph_0, then \chi_B(G_{\{f_1,\ldots,f_n\}})\leq 2n+1.

So in the case that \{f_1,\ldots,f_n\} generate a commutative semigroup, we do get the classical bound for the chromatic number of G_{\{f_1,\ldots,f_n\}} (assuming it’s finite).  What follows is a proof of this.  The main ideas are exactly those from Palamourdas’ thesis, but teased apart a bit differently than he presented them.  It was an interesting exercise doing this, and I thought I might share it on the blog.

Throughout, we’ll refer to the semigroup generated by \{f_1,\ldots,f_n\} as S, and think of it as acting on the vertex set X in the obvious way (on the left).  We’ll also just refer to our graph simply as G.  We note that given a vertex x\in X, its m-neighborhood in G can be defined as

\{ y\in X \mid \exists w\in S (|w|\leq m \wedge (w\cdot y = x \vee w\cdot x = y)) \}

(here |w| refers to the word length of w).

Note that if S is in fact a group (abelian or otherwise), then every vertex in G has degree \leq 2n (the inverses of \{f_1,\ldots,f_n\} may not be included in that set, whence the factor of 2), so we get our desired upper bound on its Borel chromatic number.  Thus this result is only interesting if S is not a group.

By assumption, we know there is a coloring c\colon X\to k for some k\in\mathbb{N}.  As in our last example, we will alter this coloring and eventually come up with a new coloring using \leq 2n+1 colors.  I’m going to split this into two lemmas.

Lemma 1: If w\in S is central, then the map d\colon X\to k defined by d(x)=c(w\cdot x) is also a coloring.

Proof: Suppose that (x,y)\in G, so there is some f_i such that f_i\cdot x=y.  Then

d(y) = d(f_i\cdot x) \\ = c(w f_i \cdot x) \\ = c(f_i w \cdot x) \\ \neq c(w\cdot x) \\ = d(x). \,\, \Box

This is notable mainly in light of the next lemma.

Lemma 2: Fix a w\in S (not necessarily central) and define d as in Lemma 1.  Suppose there are v, w_v\in S such that w_v v = w, and define Y_{v,x} = \{ y \mid v \cdot y = x\}.  Then d(Y_{v,x}) is a singleton.

Proof: Suppose v\cdot y = x.  Then

d(y) = c(w\cdot y) \\ =c(w_v v\cdot y) \\ =c(w_v\cdot x). \,\, \Box

This lets us reason about the colors of the neighbors of a given vertex x!  We know that there are at most n colors represented among the vertices f_i\cdot x.  If we have a w which can be written as w_{f_i} f_i for each i and we use d to assign colors to the vertices, then we also know that the number of colors used on \cup_i Y_{f_i,x} is at most n as well.  (We couldn’t necessarily say this about c.)  But this is true for any vertex x, so it seems that if we start with d and go through and recolor the vertices somehow, we should only need to use 2n+1 colors, since the neighbors of any vertex can only have used up at most 2n colors as we go through the process.  Of course we need to be a little more precise to be sure we can do this in a Borel way.

At this point, we’ve basically got it.  We’re in a commutative semigroup, so we can use any w\in S to define d and still get a k-coloring of G.  Again by commutativity we can rearrange the element f_1 f_2\ldots f_n so that any of the f_i appears at the end, so that seems like a good candidate for our w.  We do things like we did with bounded degree graphs and start by keeping the things with color 0 as color 0, then move through giving vertices the least available color.  (This is where it’s important that d is actually a coloring; what we get out of this process is only guaranteed to be a coloring if we start with one.)  There is one catch though.

Think about what happens, say, when you look to recolor a vertex x that d has given the color 2.  If none of its neighbors have color 0, then you give it color 0.  But to know if this happened, you need to know if its neighbors had neighbors with color 0, since they may have been initially assigned color 1 by d but then changed to color 0.  So it’s not enough to know the 1-neighborhood of x, you also need to know its 2-neighborhood.  In general, since we’ll be working our way through k many colors, we need to know the k-neighborhood of x.  This isn’t an issue in this case though; just let w=(f_1\ldots f_n)^k.  Clearly every word in S with length \leq k can be written as the rightmost portion of a word equal to w.

A few lingering thoughts

When split into the two lemmas above, it’s easy to see that the argument may apply to some \{f_1,\ldots,f_n\} which generate a non-commutative semigroup $S$ as well.  Given a k-coloring of the “Schreier graph”, you would need a central element of the semigroup S which could also be written as w_v v for any v\in S of length \leq k.  I don’t think this describes a particularly nice class of semigroups though, so saying “commutative semigroup” probably gets all of the interesting cases.  Still, I might be wrong!  I thought perhaps growth conditions on S might help (since then pigeonhole arguments would give elements of S which can be written as w_v v for many different vs), but this doesn’t seem to be enough.  Simply having a nontrivial center also seems to not be enough either.  But maybe I’m overlooking a neat argument.

Also, the similarity to the bounded-degree case also strikes me as worth looking at a little more.  I tried for a little bit to cast the argument above as finding some sort of auxiliary graph which had degree \leq 2n at each vertex whose coloring would tell us how to color the initial graph, but I couldn’t figure out how and so I set that aside.  If that approach did work it might give the result for some other non-abelian “Schreier graphs”.

Finally, I should mention that Palamourdas was able to lower the upper bound on \chi_B(G_{\{f_1,\ldots,f_n\}}) (assuming it’s finite) to something O(n^2) in the general case through a different argument.  I won’t go through it here, but it’s very nice.  Maybe in another post?  We’ll see.

Leave a comment

Filed under Uncategorized

The elementary classes of elementary amenable groups

The collection of elementary amenable groups EG is the smallest collection of groups which contains the finite groups and the abelian groups and is closed under taking subgroups, quotients, extensions, and direct unions.  The point of this definition is that these are those groups which are “obviously” amenable.  Finite groups are clearly amenable, and a little more work will show that abelian groups are amenable.  A little further work will show that the amenable groups are closed under everything I listed above.

This sort of definition is common in mathematics, and is sort of “top-down”: there are many collections, and the smallest one is what you want, whatever that happens to be.  As is often the case, one can make a more “bottom-up” definition.  This just requires a little transfinite induction, but hey, how else do you build things up in stages if there are more than countably many stages?

Let EG_0 be the collection of finite groups and countable abelian groups.  (In general, one wants to include all abelian groups, but we’re only interested in countable amenable groups, so this will be all that we need.)  If \alpha is a limit ordinal and EG_\beta has been defined for all \beta<\alpha, then let EG_\alpha = \cup_{\beta<\alpha} EG_\beta.  Finally, if EG_\beta has been defined, let EG_{\beta+1} be those groups which can be written as either a directed union of groups from EG_\beta or as an extension of groups from EG_\beta.  (In fact, one may assume the quotient in the extension is from EG_0, though this is not important for this post.)  Then the countable elementary amenable groups are \cup_{\alpha<\omega_1} EG_\alpha.  This is not immediately obvious, but it’s not too hard to show, and was first done by Chou in 1980.  The question is whether this collection is closed under subgroups and quotients (it’s clearly closed under the other two operations).  In fact, each EG_\alpha is closed under subgroups and quotients.  If G\in EG, we call the least \alpha such that G\in EG_\alpha the elementary class of G and write c(G)=\alpha.

Something that is not clear, and was not shown by Chou, is that you in fact need to do the induction up to \omega_1 to get every countable elementary amenable group.

Theorem: For every \alpha<\omega_1, there is a countable elementary amenable group G with c(G)\geq\alpha.

We’ll prove this by induction on \alpha.  This is just a slight streamlining of an argument from Olshanskii and Osin; they prove more than this so they use a little more.  First, the theorem is clearly true for \alpha=0.  Suppose that \alpha is a limit ordinal.  Then let \beta_0<\beta_1<\beta_2<\ldots be a sequence of ordinals with supremum \alpha.  (This always exists since \alpha is countable.)  Let G_0,G_1,G_2,\ldots be elementary amenable groups such that c(G_i)\geq\beta_i.  Then the direct sum G=\sum_{i\in\omega} G_i is elementary amenable, since it is the increasing union of the groups \sum_{i=0}^n G_i, which are themselves repeated extensions of elementary amenable groups.  Further, c(G)\geq\alpha, since each EG_\beta is closed under subgroups.

Thus it remains to show that if \alpha=\beta+1, then there is a group of elementary class at least \beta+1.  We may assume that there is a group K of elementary class \beta, since by our induction we know there is a group of elementary class \geq\beta, and if it has elementary class >\beta we are done.  We will need the following theorem:

Theorem: Every countable (elementary) amenable group embeds into a 2-generated (elementary) amenable group.

This really just uses a slight modification of the Neumann-Neumann construction mentioned in this previous post, as explained by Osin over at MathOverflow.  Even the lemma by Hall mentioned over there is really just noticing something about part of the Neumann-Neumann construction.  A much stronger version of the above theorem is in the Olshanskii and Osin paper I mentioned, proven by further modifying the Neumann-Neumann construction, but that isn’t necessary here.

We see that c(K\times K)\leq\beta+1, and if it is in fact \beta+1 we are done.  If it is not, we look at K wr K, where wr denotes the restricted wreath product.  The base group B of K wr K is isomorphic to the direct sum \sum_{i\in\omega} K, which is the increasing union of \sum_{i=0}^n K, so c(B)\leq\beta+1.  As before, we may assume that c(B)=\beta.  Then there is a short exact sequence

1 \rightarrow B \rightarrow K wr K \rightarrow K \rightarrow 1

so c(K wr K)\leq\beta+1.  We will show that in fact equality is achieved.  By the above theorem, we may assume that K is finitely generated, and so K wr K is as well.  This means that K wr K can not be written as the increasing union of groups with smaller elementary class, so we need not consider that case.  Suppose that there is a short exact sequence

1 \rightarrow N \rightarrow K wr K \rightarrow Q \rightarrow 1

with c(N),c(Q)<\beta.  Let K'\cong K be the copy of K in K wr K which acts on B.  Since Q can not contain a subgroup isomorphic to K, it must be that N\cap K' \neq \{e\}.

Let k\in N\cap K' be nontrivial.  Let K_0 be the coordinate subgroup of B at e_K.  Then [k, K_0]\leq N since N is normal, so c([k,K_0])<\beta.  Note that the generators of [k,K_0] are functions in B which take nontrivial values at the e_K and k coordinates, and are trivial elsewhere.  Call the generator with value a at its e_K coordinate f_a.  Then f_a \mapsto a extends to a surjective homomorphism of [k,K_0] onto K, which is impossible since c(K)=\beta.  Thus c(K wr K)=\beta+1, as desired.

Leave a comment

Filed under Uncategorized

Commensurability of finitely generated groups

Let’s begin with a definition.

Definition: Two groups G,H are commensurable, which we’ll write G\approx H, if there exist subgroups G_0 \leq G, H_0 \leq H such that [G \colon G_0],[H \colon H_0]<\infty and G_0 \cong H_0.

This relation pops up in geometric group theory (among other places, I’m sure); for example the index in De La Harpe’s book lists about a dozen entries for “commensurable groups”.  Groups which are commensurable are easily seen to be quasi-isometric, and classifying groups up to quasi-isometry is a main focus in geometric group theory.

Commensurability of finitely generated groups is a countable Borel equivalence relation.  At some point, one begins to take the Borelness of these sorts of things for granted, so that part isn’t so surprising.  But the fact that the relation is countable is, I think.  It’s easy to see that a finitely generated group only has countably many finite-index subgroups; any finite-index subgroup is also finitely generated, and a finitely generated group only has countably many finitely generated subgroups.  But for this equivalence relation to be countable, one also needs to know that a given finitely generated group can only be a finite-index subgroup of countably many finitely generated subgroups.  This is not immediately obvious (at least, not to me).  As far as I can tell, the easiest way to see this is by appealing to the following theorem, due to Kaloujnine and Krasner:

Theorem (Kaloujnine-Krasner): Every extension of a group N by a group H is embeddable in the unrestricted wreath product N \mathbin{Wr} H.

So say that N is a finite-index normal subgroup of a group G.  Then G is the extension of N by some finite group H, and so G embeds into N \mathbin{Wr} H = N \mathbin{wr} H, since H is finite.  Since N \mathbin{wr} H is countable, it contains only countably many finitely generated subgroups, so there are only countably many possibilities for G given H.  There are also only countably many possibilities for H, so there are only countably many groups which N for which can be a finite-index normal subgroup.  What if N is not a normal subgroup?  Then it contains a finite-index normal subgroup, so everything still works out.

Recall the terminology from the last post.  We’re going to look at the proof of the following result.

Theorem (Thomas): Commensurability of finitely generated groups is a universal countable Borel equivalence relation.

Note that it’s easy to see that commensurability is weakly universal, since it contains isomorphism of finitely generated groups as a subequivalence relation, and isomorphism is universal.  So this proof makes exactly the leap from weakly universal to universal that we’d like to make with the theorems I discussed last time.

The proof proceeds by creating a reduction from isomorphism to commensurability.  In fact, the reduction is easy to write down.  Let S be your favorite infinite, finitely generated simple group, and let A_5 denote the alternating group on 5 elements.  Then the map

G \mapsto W_G = (A_5 \mathbin{wr} G) \mathbin{wr} S

is our reduction.  Clearly isomorphic groups will be sent to commensurable (in fact, isomorphic) groups.  The trick, of course, is to verify that this sends nonisomorphic groups to non-commensurable groups.

— Showing W_A \approx W_B implies that particular subgroups are isomorphic —

Suppose that W_A \approx W_B.  We want to show that A \cong B.  It is enough to show that (A_5 \mathbin{wr} A) \cong (A_5 \mathbin{wr} B), by a result of P.M. Neumann which states that A \mathbin{wr} B \cong A' \mathbin{wr} B' iff A\cong A' and B\cong B'.  The idea of the proof is to show that given a finite index subgroup of W_A , one must be able to somehow recover (A_5 \mathbin{wr} A).

A priori this could be quite difficult.  Suppose that you know two groups G,H are isomorphic, say via \pi.  Say K is a subgroup of G that is somehow special or contains information you’ve coded into the construction of G, and H also contains a special subgroup L.  There is no reason that \pi(K) should have anything to do with L, and so there is no reason to expect the information you’ve coded in K is the same as the information you’ve coded in L.

Let K_A denote the base group of W_A.  Then other results of P.M. Neumann show that W'_A=[S,K_A]S.  This characterization, combined with a few other P.M. Neumann results (and here is where we use that S is infinite and simple) tells us that if H_A is a finite-index subgroup of W_A, then W'_A=H'_A.  So indeed, we can try and use the commutator subgroup of W_A to recover A.  (All of these P.M. Neumann results are from the same paper, On the structure of standard wreath products of groups, which is a very thorough account of properties of wreath products.) This is great, because if H_A \cong H_B, then the isomorphism must send H'_A to H'_B. So if we’ve coded information into H'_A it must be the same as the information in H'_B. In this case, we’re hoping to be able to recover A from H'_A.

— Finding A in H'_A

So if W_A \approx W_B, we know that [S,K_A]S\cong [S,K_B]S.  We want to keep peeling away until we can see A and B.  It seems intuitively obvious that we can get rid of the S‘s, but how?  Let sf\in [S,K_A]S be such that f\in[S,K_A], and s\in S, and let \pi(sf)=s'f'\in[S,K_B]S with f'\in[S,K_B] and 1\neq s'\in S.  We’d like to show that s\neq 1 iff s'\neq 1, since this implies [S,K_A]\cong [S,K_B].

We again look for certain subgroups that we know any isomorphism must preserve.  It would be nice to prove something like the following: C_{W'_A}(sf) is cyclic iff s\neq 1.  Then since C_{W'_B}(s'f')\cong C_{W'_A}(sf), we’d be done.  Unfortunately, things aren’t quite so easy.  Define L_{sf} to be the normal closure of sf in W'_A, and R_{sf}=\langle (sf)^{L_{sf}} \rangle (i.e. R_{sf} is the normal closure of sf in L_{sf}).  Then one can show that C_{L_{sf}}(R_{sf})=1 iff s=1.  Since all of these groups are preserved under isomorphism, we now know [S,K_A] \cong [S,K_B].

I don’t really have a good idea of how one decides to look at these groups beyond trial and error.  The one thing I’ll note is that centralizers are relatively easy to understand in wreath products A \mathbin{wr} B, since conjugating elements of the base group K by elements of B just shifts them around, and understanding conjugation by elements of K is really only as difficult as understanding conjugation in A.  In particular, clearly C_{A \mathbin{wr} B}(K)=\{e\}, and so any subgroup containing K will have trivial centralizer with respect to the whole group.  So it makes sense to look at centralizers.

For X\subseteq S, let K^X_A=\{f\in K_A \mid \sigma(f)\subseteq X\}, where \sigma(f) denotes the support of f.  Now by a result of P.M. Neumann (again, I know), [S,K_A]=W'_A\cap K_A.  Obviously if |X|=1 we have K^X_A\cong A_5 \mathbin{wr} A, so if K^X_A \leq W'_A \cap K_A, we’d be well on our way to being done.  But in general this doesn’t happen.  We can do almost as well though.  Call A_5 \mathbin{wr} A=\hat{A}.  Using the P.M. Neumann result, it’s not too hard to check that if s\neq t\in S, (W'_A\cap K_A^{\{s,t\}})/(W'_A\cap K_A^{\{s\}}) \cong \hat{A}, and the analogous statements are true for W_B.  (Obviously K_A^{\{s,t\}}/K_A^{\{s\}} \cong \hat{A}, so this is just a matter of checking that enough of these groups are contained in W'_A for such an isomorphism to still exist.)  So it is enough to show that there are some a,b,c\in S with a\neq b such that \pi(W'_A \cap K_A^{\{c\}})=W'_B \cap K_B^{\{a\}} and \pi(W'_A \cap K_A^{\{1,c\}})=W'_B \cap K_B^{\{a,b\}}.

For f\in [S,K_A], let L_f=\langle f^{[S,K_A]} \rangle, and define R_f = C_{[S,K_A]}(L_f).  Note the similarity to the groups looked at couple of paragraphs ago.  A quick calculation shows that every element of L_f has support contained in \sigma(f), so L_f \leq W'_A \cap K_A^{\sigma(f)}.  We also note that since A_5 is simple and nonabelian, \hat{A} has a unique nontrivial minimal normal subgroup, its base group \hat{K}_A.  Minimality is easy to check.  For uniqueness, since C_{\hat{A}}(\hat{K}_A)=\{e\}, we find that any normal subgroup of \hat{A} must contain \hat{K}_A.  That second fact can be used to show that L_f contains all the elements of K_A with support contained in \sigma(f) and range contained in \hat{K}_A.  It’s easy to see what happens to these functions under conjugation, and so after further calculation we find that C_{[S,K_A]}(R_f)=W'_A \cap K_A^{\sigma(f)}.  We now know that |\sigma(f)|=1 iff C_{[S,K_A]}(R_f) is minimal among all groups of the form C_{[S,K_A]}(R_h) with h\in [S,K_A], and since similar results hold in [S,K_B], we get our desired result.

To sum up, I think the main insight is that some subgroups don’t really change under isomorphism. (There is a little work to get from asking about commensurability to asking about isomorphism, but this is taken care of by P.M. Neumann’s results.) Derived subgroups map to derived subgroups; centralizers map to centralizers. This means that we can try and use those subgroups to encode the information we’re interested in preserving. Perhaps it’s an obvious idea, but until I actually wrote out what was happening, I hadn’t thought of things in those terms.

Leave a comment

Filed under Uncategorized

Universal countable Borel equivalence relations with an eye toward finitely generated groups

In the previous post, I discussed a technique due to Neumann and Neumann for embedding any countable group into a 2-generated group, and mentioned in passing that they used the same ideas to create a finitely generated 3-solvable non-Hopfian group.  This construction turned out to be very useful to my own research, but to describe how requires a few definitions, which I’ll get to in a moment.  The aim of this post is not really to discuss my research, but instead to gear up to look at a related result, which I hope to understand better.  That will be the subject of the next post.  Perhaps it will help with my research again.

I’ve previously mentioned Borel equivalence relations in passing.  Let’s talk about them in a bit more detail.

Definition: If X is a Polish space (or more generally, a standard Borel space) and E is an equivalence relation on X, then we say E is Borel if E is Borel as a subset of X\times X.

Definition: We call an equivalence relation countable if all of its equivalence classes are countable.

My research focuses on countable Borel equivalence relations.  Many interesting equivalence relations are countable Borel; for example Turing equivalence, eventual equality of infinite binary sequences (known as E_0, which you may have seen in a hat problem), isomorphism of finitely generated groups, or orbit equivalence relations arising from Borel actions of countable groups.  (In fact, a theorem of Feldman and Moore says that every countable Borel equivalence relation can be realized as the orbit equivalence relation arising from a Borel action of a countable group!)  When discussing Borel equivalence relations, we are mainly interested in comparing them using the notion of a Borel reduction.

Definition: Suppose E and F are Borel equivalence relations on Polish spaces X,Y.  Then a Borel homomorphism from E to F is a Borel map f\colon X \rightarrow Y such that

\displaystyle x \mathbin{E} y \,\, \Rightarrow \,\, f(x) \mathbin{F} f(y)

Borel reduction from E to F is a map f\colon X \rightarrow Y such that

\displaystyle x \mathbin{E} y \,\, \Leftrightarrow \,\, f(x) \mathbin{F} f(y)

If E Borel reduces to F, we write E \leq_B F.

The idea behind a Borel reduction is that if E \leq_B F, then F is at least as complicated as F.  If one could classify the elements of Y up to F-equivalence, then using the Borel reduction you could also classify the elements of X up to E-equivalence.  (Note that this is not so different from the justification for using poly-time reductions in complexity theory to compare the difficulty of decision problems.)  The point of keeping things Borel that Borel objects are in some sense explicit.  Using the axiom of choice one can show there exist reductions between any two equivalence relations with the same number of equivalence classes, but the reductions are in general not Borel.  In fact, there are a whole host of results establishing non-reducibility of certain Borel equivalence relations.  A relatively simple example is that equality on 2^\mathbb{N} Borel reduces to E_0, but not vice versa, as can be seen using Baire category or measure arguments.

Definition: A countable Borel equivalence relation E is universal (or complete) if for any countable Borel equivalence relation F, F\leq_B E.

To extend the analogy with complexity theory, a universal countable Borel equivalence relation (if it exists) relates to countable Borel equivalence relations in the same way an NP-complete decision problem relates to NP decision problems; it’s as complicated as it possibly could be given its complexity.  Note that one could easily make a similar definition for any class of Borel equivalence relations.  Indeed, this is done.  Some classes have universal equivalence relations and some don’t.

Theorem (Dougherty-Jackson-Kechris): There is a universal countable Borel equivalence relation.

Once one has one example of universal countable equivalence relation E_\infty, then one can show another countable Borel equivalence relation E is universal simply by showing E_\infty \leq_B E, and indeed this is how most proofs of universality proceed.

Theorem (Thomas-Velickovic): Isomorphism of finitely generated groups is a universal countable Borel equivalence relation.

There are many other examples, but this is the one which interests us in this post.  Finitely generated groups can be quite complicated, and this result puts some rigor behind that intuition.  The proof rather heavily uses free products with amalgamation.  These are “large” from a group-theoretic standpoint (for example, they all contain free non-abelian subgroups), and so seen as complicated in and of themselves.  So it’s not surprising that isomorphism of these sorts of groups is complicated.  But what about finitely generated groups which are not as complicated?  Is the isomorphism relation still complex?  There has been some progress towards answering this, but we need one more definition.

Definition: A countable Borel equivalence relation E is weakly universal if for any countable Borel equivalence relation F there is a countable-to-1 Borel homomorphism from F to E.  Equivalently (this is not obvious), E is weakly universal if it contains a universal countable equivalence relation.

Clearly every universal countable Borel equivalence relations is weakly universal.  The idea behind looking at countable-to-1 Borel homomorphisms from an equivalence relation E to another equivalence relation F is that although these are not necessarily Borel reductions, they can’t fail too badly to be such, sending at most countably many E-inequivalent elements to F-equivalent elements .  Compare this with E_0 and equality on 2^\mathbb{N}; every Borel homomorphism from E_0 to equality must send a measure 1 set to the same point!

Whether or not every weakly universal equivalence relation is in fact universal is a notorious open problem.  A positive answer would make many proofs of universality trivial (or at least much simpler); creating Borel homomorphisms from a universal E to another Borel equivalence relation F is always the easy part, it’s making these maps reductions which is trickier.  A negative answer follows from Martin’s Conjecture, a stubbornly open conjecture in its own right, but which seems to provide excellent tools for analyzing weakly universal equivalence relations.  In any event, weakly universal equivalence relations are pretty high up in the \leq_B-hierarchy (which is not at all linear, so this should be understood as an imprecise-but-ultimately-mathematically-defensible statement).

So, back to isomorphism of finitely generated groups.  We have the following:

Theorem (Thomas-Williams): Isomorphism of Kazhdan groups is weakly universal.

Theorem (Williams): Isomorphism of finitely generated 3-solvable groups is weakly universal.

In both of these cases, we expect that the relations are in fact universal, but as I mentioned, making Borel reductions is a bit trickier than making Borel homomorphisms, which is all that is needed to prove weak universality.  My proof of the second theorem makes use of a modification of the Neumann and Neumann construction mentioned at the beginning of this post; in fact to modern eyes their construction already showed that E_0 Borel reduces to isomorphism of finitely generated 3-solvable groups, a non-trivial lower bound on the complexity.  It is known that E_0 is strictly below any weakly universal equivalence relation with respect to Borel complexity, so my result is a stronger lower bound than Neumann and Neumann’s.

It would be nice to make the leap from weak universality to universality.  In the next post, we’ll look at how a different group-theoretic equivalence relation was shown to be universal in the hopes of learning something we can use.

1 Comment

Filed under Uncategorized

Three ways of embedding a countable group in a 2-generated group

Let me start off by saying that between travel and life intervening (stolen laptop, good times), I haven’t devoted much time to the paper I discussed in the last post.  What’s more, it seems I bit off a bit more than I could chew; I’m quite familiar with amenability from the point of view of Følner sequences and finitely additive probability measures, but the paper comes at it from a much more dynamical systems/functional analysis point of view.  One of the great strengths of the concept of amenability is that it can be defined in so many disparate ways, tying together several fields, but it can make for situations like I just had, where I couldn’t make it even halfway through the second section of the paper without learning a lot of new (albeit straightforward) mathematics.  Of course, I do want to learn some new things, that’s the whole point, but it got a bit overwhelming.  So I’m setting that aside that for now and getting back to something a bit closer to my research.

It’s a well-known fact that any countable group can be embedded into a 2-generated group.  Heck, I’ve mentioned it previously.  I’m going to go through three different proofs of this result, which each have some interesting consequences.

The original proof

The original proof of this result is due to Higman, Neumann, and Neumann, and uses what are now known as HNN extensions.  Here’s a quick refresher:

Definition: Suppose G is a group with subgroups A,B such that A is isomorphic to B, as witnessed by \phi\colon A\rightarrow B.  Then the HNN extension of G relative to this information is the group

\langle G, t \mid t^{-1}at = \phi(a), a\in A \rangle

The key result is that the above group behaves the way that you hope it would given the definition.  By this I mean the following: we can call a word in G and t reduced if it does not contain a subword of the form t^{-1} a t or t b t^{-1}, where a\in A and b\in B.  (Such subwords could obviously be replaced by a single element of B or A, respectively.)  Then reduced words which aren’t literally the identity do not represent the identity in the above group.  Note that this immediately implies that G embeds into the above group.

Given this, how do we get the theorem?  Suppose C is a countable group with elements c_1, c_2, c_3,\ldots.  Let F = C * \langle a, b\rangle, i.e. the free product of C and the free group on two generators.  Note that \langle a,b \rangle contains the free group on countably many generators as a subgroup, e.g. the group A generated by \{ a, b^{-1}ab, b^{-2}ab^2,\ldots\} is free.  (For the topologically inclined, this is easy to see using covering spaces.  Otherwise just proving it combinatorially is easy enough.)  What’s more, the group B\leq F generated by \{b, c_1 a^{-1} b a, c_2 a^{-2} b a^2, \ldots\} is free.

So now we have isomorphic subgroups A,B of F, so we can take the HNN extension

\langle F, t \mid t^{-1} a t = b, t^{-1} b^{-i} a b t = c_i a^{-i} b a^i \rangle

This embeds F and so it embeds C.  It’s easy to see from the presentation that the group is generated by t and a.  So there you have it.

The HNN extension continues to lead an illustrious life in group theory, getting used in all sorts of embedding results, as well as playing a prominent role in Bass-Serre theory.  But this is where it all began.

Using wreath products

Later, Neumann and Neumann did a proof completely avoiding HNN extensions.  To understand it, we need to be familiar with wreath products.  Somewhat annoyingly, there are several slight variations on the definition, so let’s be clear about what we’re looking at here.

Definition: Let G and H be groups, and let $math B$ denote the set of functions from H to G.  Note that this is a group under pointwise multiplication, i.e. \alpha\beta(x)=\alpha(x)\beta(x).  Note also that H acts on B by shift: h\cdot f(x)=f(h^{-1}x).  This is an action by automorphisms, so we may define the semidirect product B \rtimes H.  It is this group which we call the (unrestricted) wreath product G \mathbin{\mathrm{Wr}} H.

A few remarks.  First, note that the if G and H are countably infinite, then the cardinality of G \mathbin{\mathrm{Wr}} H is that of the continuum.  One can instead define the restricted wreath product by starting with the group of functions from G to H having finite support and obtain a countable group.  This is often denoted G \mathbin{\mathrm{wr}} H or G \wr H.  Second, people have a tendency to define the semidirect product in a few different (but isomorphic) ways, so let’s go ahead and be explicit about the group operation here:

(h, f)(h', f')=(hh', (h'\cdot f) f'),

where h,h'\in H and f,f'\in B.  Finally, I should mention one other construction commonly referred to as a wreath product.  Suppose that Y is a set on which a group H acts by permutations.  Then we can let B be the group of functions from Y to G, on which H acts by shift, and again set up the semidirect product.  Most frequently this happens with Y=\{1,2,\ldots,n\} and H the symmetric group on n elements.  If you’re lucky, the authors will write this like G \mathbin{\mathrm{Wr}}_Y H or G\wr_Y H, but don’t count on it.

So where were we?  Right, suppose we have a countable group C=\{c_1,c_2,\ldots\}.  We wish to embed it into a 2-generated group.  It’s unclear at first how the wreath product could help, since it’s too big to be finitely generated.  We’ll get around this by embedding C into a 2-generated subgroup of a wreath product.

Let Z=\langle z \rangle be the infinite cyclic group, and define P = C \mathbin{\mathrm{Wr}} Z.  We’ll focus on the elements (0, g_i)\in P, where g_i(z^t)=c_i^{-t}.  So in some sense g_i keeps track of the powers of the ith element of C.  Now look at k_i = [(0,g_i), (z, id)]:

[(0,g_i), (z, id)]=(0,g_i^{-1})(-z,id)(0,g_i)(z, id)

=(0,g_i^{-1})(-z,id)(z,z\cdot g_i)

=(0,g_i^{-1})(0, z\cdot g_i)

=(0, g_i^{-1} (z\cdot g_i))

Since z shifts the values of g_i over one spot, we see that g_i^{-1} (z\cdot g_i) is just the function which is constantly c_i.  The group of constant functions is clearly isomorphic to C, but P is not finitely generated, so we’re not done yet.

Now let D=\langle d \rangle be another infinite cyclic group.  We single out elements d_i = d^{2^i-1}\in D, for every i\in\mathbb{N}.  A good way to think of these elements are as those numbers written in binary using only 1s.  The reason for choosing these is that the sum of any two such elements never makes a third (or the identity in D).  Certainly there are other choices for such a set, but this is of no importance.

Let Q = P \mathbin{\mathrm{Wr}} D.  Let q\in Q be the function from D to P defined by q(0)=z, q(d_i^{-1})=g_i, and q(y)=id_P for other values of y.  So q has information about every g_i.  Now look at h_i = [d_i \cdot q, q].

[d_i \cdot q, q](0)=[d_i \cdot q(0), q(0)]

= [q(d_i^{-1}), q(0)]

= [g_i, z] = k_i

Also, [d_i \cdot q, q](d_j^{-1})=[d_i \cdot q(d_j^{-1}), q(d_j^{-1})]

= [q((d_i d_j)^{-1}), q(d_j^{-1})] = id_P,

since d_i d_j \neq d_k for any k\in\mathbb{N}.  Similarly we find that h_i(y)=id_P for any other value of y.

So it’s now clear that the group generated by the h_i is isomorphic to that generated by the k_i, which is isomorphic to C.  What’s more, the h_i are all just products of q and d.  So we have embedded C into the subgroup of Q generated by q and d.

In fact, we can say more.  Suppose that C is a solvable group of class k.  Then C^\mathbb{Z} is also solvable of class k, and so P is solvable of class at most k+1.  Similarly, Q is solvable of class at most k+2, and thus so are its subgroups.  So we’ve shown that any countable solvable group of class k embeds into a 2-generated solvable group of class k+2.

One can show this is tight; there is a countable abelian group (i.e. a countable solvable group of class 1) which does not embed into any finitely generated metabelian group (i.e. a solvable group of class 2).  You can say even more if you’re willing to talk about varieties of groups, but let’s not get into that.  This construction can also be used to create a finitely generated solvable group which is non-Hopfian.  Pretty neat!

Subgroups of symmetric groups

The last proof is due to Galvin, but in his own words, it’s just the Neumann-Neumann proof, done from a slightly different point of view.  The coding involved is more transparent, but you lose the nice structural properties (e.g. there’s no guarantee that solvable groups will be embedded in solvable groups).

So suppose we have a countable group G.  We may assume that G is a subgroup of Sym(\mathbb{N}).  We’ll show there is a 2-generator subgroup of Sym(\mathbb{Z}\times\mathbb{Z}\times\mathbb{N}) into which G embeds.  The picture I have in my head of \mathbb{Z}\times\mathbb{Z}\times\mathbb{N} is of an infinite grid (that’s the \mathbb{Z}\times\mathbb{Z} part) with infinite columns on top of each point in the grid (that’s the \mathbb{N} part).  So I’ll talk about x-columns in the grid when I mean a set of the form (x,-,-), and I’ll just call something a column when it’s a set of the form (m,n,-).  The basic idea is to define a permutation which encodes information about the ith element of G in what it does to the (i, n, -) column for each n\geq 0.  In reality we have to do a little extra, but it’s not too complex.

We will enumerate G as \{g_1,g_3,g_5,\ldots\}.  Let a be the permutation sending (m,n,k) to (m+1,n,k).  Let b be the permutation defined by

b((0,n,k)) = (0,n+1,k)

b((2m+1,n,k)) = (2m+1,n,g_{2m+1}(k)) for m>0 and n\geq 0

b(m,n,k) =(m,n,k) otherwise

So by looking at b acting on, say, the (2m+1, 0,-) column, we can tell exactly how g_{2m+1} acts on \mathbb{N}.  We want, given some j, to be able to somehow isolate just the g_{2j+1} information.

First, we conjugate b by a power of a to shift it.  For i odd and positive, let b_i = a^{-i} b a^i.  If we conjugate b_i^{-1} by b, what happens?  Well, b_i^{-1} permutes around (some) even-indexed x-columns but leaves the odd-indexed x-columns alone, while b does the opposite, except at the (0, n, -) columns.  Thus b b_i^{-1} b^{-1} behaves like b_i^{-1} everywhere except possibly the (0,n,-) columns.  We see that b_i^{-1} acts like g_i^{-1} on each (0,n,-) column with n\geq 0, but b sends (0,n,p) to (0,n+1,p), so b b_i^{-1} b^{-1} acts like g_i^{-1} on each (0,n,-) column with n>0.  Thus, when we look at c_i=(b b_i^{-1} b^{-1}) b_i, there is cancellation everywhere but the (0,0,-) column, i.e. c_i(0,0,p) = g_i(p) for all p\in\mathbb{N}, and c_i is the identity everywhere else.  So clearly the group generated by the c_i is isomorphic to G.  Further, it’s a subgroup of the group generated by a and b.


One thing one notices about all these proofs is that you must choose an enumeration for your countable group G, or at least its generators.  But different enumerations will, in general, give rise to different groups.  So one might wish for a construction which does not depend on the enumeration you choose, so it would be less set-theoretic and more purely group-theoretic.  Alas, it is not to be.

Theorem (Simon Thomas): Let \mathcal G denote the space of countable groups, and \mathcal G_{fg} denote the space of finitely generated groups.  There is no Borel map \phi\colon \mathcal G \rightarrow \mathcal G_{fg} such that

  • G \hookrightarrow \phi(G), and
  • G\cong H implies that \phi(G) \cong \phi(H).

Borel maps should be thought of as “explicit” maps.  In fact, in the context of group-theoretic constructions, nearly everything induces a continuous map on the above spaces.  So ruling out Borel maps is the same as ruling out group-theoretic constructions.  The choice of an enumeration is unavoidable!

However, if you restrict yourself, you can get by without an enumeration.  Using Galvin’s above construction to modify a proof of Harvey Friedman’s, Thomas was able to show the following:

Theorem: Let \mathcal G_2 denote the space of 2-generated groups.  Then there is a Borel map \psi\colon\mathcal G_{fg} \rightarrow \mathcal G_2 such that

  • G \hookrightarrow \psi(G), and
  • G\cong H implies that \psi(G)\cong\psi(H).

The map doesn’t seem purely group-theoretic, as it uses ideas from computability theory, and Galvin’s coding is pretty much just combinatorics, but it does avoid the use of Choice.  Ultimately the difference between the two situations comes down to results from Borel equivalence relations, but that’s another post altogether.


Filed under Uncategorized

A new method for showing groups are amenable

Extensions of amenable groups by recurrent groupoids

Kate Juschenko (Vanderbilt), Volodymyr Nekrashevych (Texas A&M), Mikael De La Salle (ENS de Lyon)

This paper introduces a new framework to prove that certain groups are amenable.  There is an important distinction to make when talking about amenable groups: there are the elementary amenable groups, which are roughly speaking the groups which are obviously amenable, and then there are the nonelementary amenable groups.  It took about 25 years to show that nonelementary amenable groups exist, with the first example due to Grigorchuk.  It’s a very nice group, which can be defined in terms of measure-preserving transformations of [0,1], or automorphisms of the complete binary tree, or even in terms of finite automata.  Other examples of nonelementary amenable groups followed, with various methods used to prove their amenability.  The main theorem of this paper can be used to show that any previously-known (to me, at least) example of a nonelementary amenable group is amenable.  That is, this one theorem implies the amenability of several different groups.  It also implies the amenability of groups not previously known to be amenable.

The main theorem is actually somewhat involved to state.  It says that if you have groups G and H of a certain type, and they satisfy four or five different conditions between them, then you can conclude that G and the topological full group [[G]] are amenable.

I’ve decided to do something a little different.  (What the heck, it’s the summer.)  I’m going to go through this paper and post a little bit as I do.  I’m not quite sure what I’ll write; it’s a bit silly to just reproduce the proofs in the paper, but it will be nice to sketch out the high points at least.  Tentatively: my next post will cover some of the background material used, the one after that will cover the main theorem, and the last post will show how various examples satisfy the conditions of the main theorem.  Let’s see how it goes.

Leave a comment

Filed under Uncategorized

Topological generators and full groups

The number of topological generators for full groups of ergodic equivalence relations

François Le Maître, UMPA-ENSL

This paper relates two important invariants associated to orbit equivalence relations.  So let’s define what types of equivalence relations we’re talking about (and a related group), what the two invariants are, and then we’ll say what the main result of the paper actually is.

Suppose we have a countable group \Gamma acting on a probability space (X,\mu).  Then the action is measure-preserving, well, if it preserves the measure.  So \mu(g\cdot B)=\mu(B) for any g\in\Gamma and measurable B\subseteq X.  The orbit equivalence relation E_\Gamma on X is defined by

x E_\Gamma y \Leftrightarrow \exists g\in\Gamma (g\cdot x = y)

We call the equivalence relation probability measure-preserving if it arises from a measure-preserving action.  We call it ergodic if every measurable union of E_\Gamma-classes is either measure 0 or measure 1.  This means, for instance, that if C\subseteq X has positive measure and we look at O=\cup_{g\in\Gamma} g\cdot C (i.e. the union of the E_\Gamma-classes which meet C), then \mu(O)=1.  So in some sense, group actions which give rise to ergodic equivalence relations (unsurprisingly called ergodic group actions) must move things around a lot, since sets of positive measure will cover the whole space (except for a null set) when you act on them by the group.  Of course, there are stronger mixing properties out there, but that doesn’t concern us presently.

Given a probability measure preserving equivalence relation E, one can talk about all measure-preserving automorphisms T of (X,\mu) for which T(x) E x for \mu-a.e.  x\in X.  This forms a group [E], called the full group of E.  Note that if E=E_\Gamma for \Gamma acting on X in a measure-preserving way, then \Gamma\leq [E].

The full group of E can be turned into a topological group without too much trouble (the metric is the obvious one, where the distance between two functions is the measure of the elements on which they differ), and then we can bring topological group theory to bear when we talk about it.  The structure of [E] is related to properties of E in ways that we’re still exploring.  One fact is that [E] is topologically simple (i.e. it has no nontrivial closed normal subgroups) iff E is ergodic.

The invariants in question

Suppose we have a measure-preserving equivalence relation E.  We extend our viewpoint beyond even [E] to look at partial Borel automorphisms of (X,\mu, E).  By this I mean Borel bijections of the form f\colon A\rightarrow B, where A,B\subseteq X are Borel, f(x) E x for \mu-a.e. x\in X, and f preserves the measures induced on A and B.  We write this set as [[E]].

So suppose we have a collection F=\{f_1,f_2,\ldots\}\subseteq [[E]].  We can define a graph G_F by x G_F y \Leftrightarrow \exists f_i\in F (f^{\pm 1}(x)=y).  If the connected components of G_F are the equivalence classes of E we call F a graphing of E.  Then the cost of F is

\sum_i \mu(\text{dom}(f_i)),

which one can check is the same as the average degree of a vertex in G_F.  The cost of E is the infimum of the costs of its graphings.  We’ll write it C_\mu(E).  (The standard reference for this stuff, by the way, is Topics in Orbit Equivalence, by Kechris and Miller.)

The other invariant we’ll look at is the number of topological generators of [E].  We say \{g_1, g_2,\ldots\}\subseteq [E] is a set of topological generators of [E] if the group generated by \{g_1,g_2,\ldots\} is dense in [E].  We write t([E]) for the least number of elements in a set of topological generators for [E].

The main theorem

If E is a probability measure-preserving ergodic equivalence relation, then t([E])=\lfloor C_\mu(E) \rfloor + 1.

The proof itself is fairly short, although it does rely on some earlier results on cost and full groups.  Really, this is as nice a relationship as one could hope for.  The author mentions that they are currently working on a paper in the case of non-ergodic equivalence relations, and have some similar results there.

1 Comment

Filed under Uncategorized