AMENABILITY AND RAMSEY THEORY

JUSTIN TATCH MOORE

Abstract. The purpose of this article is to connect the notion of the amenability of a discrete group with a new form of structural Ramsey theory. The Ramsey theoretic reformulation of amenability constitutes a considerable weakening of the Følner criterion. As a by-product, it will be shown that in any non amenable group G, there is a subset E of G such that no finitely additive probability measure on G measures all translates of E equally. The analysis of discrete groups will be generalized to the setting of automorphism groups of ultrahomogeneous structures.

1. Introduction

A group G is amenable^{1} if there is a finitely additive, translation invariant probability measure defined on all subsets of G. This notion was isolated by von Neumann from the Banach-Tarski paradox. Since then it has played an important role in a diverse cross section of mathematics. It has a large number of seemingly different equivalent formulations (see [17], [23]); two of the most celebrated are: Theorem 1.1. [20] [21] A group G is amenable if and only if there do not exist elements g_{i} (i < k) of G and a partition of G into sets A_{i} (i < k) such that, for some i_{0} < i, both {g_{i}A_{i} : i < i_{0}} and {g_{i}A_{i} : i_{0} ≤ i < k} are partitions of G.

2000 Mathematics Subject Classification. Primary: 05D10, 05C55, 20F38, 20F65, 43A07; secondary: 03C15, 03E02.

Key words and phrases. Amenable, extremely amenable, Fraïssé, Følner criterion, free group, invariant measurability, structural Ramsey theory, Thompson’s group, ultrahomogeneous.

I would also like to thank Paul Larson, Lionel Nguyen van Thé, and Todor Tsankov for reading drafts of this paper and offering comments. I am also grateful to the anonymous referee for their careful reading and suggesting a simplification and improvement to the proof of Theorem 1.4 (and in particular for pointing out that two sets are sufficient). The research presented in this paper was partially supported by NSF grant DMS–0757507. Any opinions, findings, and conclusions or recommendations expressed in this article are those of the author and do not necessarily reflect the views of the National Science Foundation.

1Throughout this paper, the adjective “left” is implicit in the usage of action, amenable, Følner, invariant, and translation unless otherwise stated.

Theorem 1.2. [5] (see also [11]) A group G is amenable if and only if for every finite A ⊆ G and every ϵ > 0 there is a finite B ⊆ G such that (letting △ denote symmetric difference)

∑_{a∈A} |(aB)△B| ≤ ϵ|B|

The set B which satisfies the conclusion of this theorem is said to be ϵ-Følner with respect to A; the assertion that such sets exist for each ϵ > 0 is known as the Følner criterion.

One of the main results of the present article is to formulate a weaker criterion for amenability than the Følner criterion. If A is a set, let Pr(A) denote the collection of all finitely additive probability measures on A. If G is a group, then the operation on G is extended to ℓ^{1}(G) affinely:

μν(A) = ∑_{xy∈A} μ({x})ν({y})

(Here and throughout we identify G with both a subset of ℓ^{1}(G) and a subset of Pr(G) by regarding its elements as point masses.) Observe that gν(E) = ν(g^{−1}E).

If A and B are finite subsets of G and ϵ > 0, then B is ϵ-Ramsey with respect to A if whenever E ⊆ B, there is a ν in Pr(B) such that

• Pr(A)ν ⊆ Pr(B) and

• |μν(E) − μ′ν(E)| ≤ ϵ for all μ and μ′ in Pr(A).

The definition is unchanged if E is allowed to be an arbitrary subset of G (in particular if B is ϵ-Ramsey with respect to A, then so is any finite superset of B). Also, one obtains an equivalent statement if μ ranges over the elements of A — these are the extreme points of Pr(A). Observe that if ν is a finitely supported probability measure on G, then Pr(A)ν can be regarded as a copy of Pr(A). Thus B is ϵ-Ramsey with respect to A if whenever we induce an affine coloring of Pr(B) by assigning the values 0 and 1 to the elements of B, there is a copy of Pr(A) on which the coloring is ϵ-monochromatic.

Theorem 1.3. Let G be a group. The following are equivalent:

(1) For every E ⊆ G and every finite A ⊆ G, there is a μ in Pr(G) such that μ(gE) = μ(E) for all g in A.

(2) For every finite A ⊆ G, there is a finite B which is \frac{1}{2}-Ramsey with respect to A.

(3) For every finite A ⊆ G, there is a finite B which is 0-Ramsey with respect to A.

(4) G is amenable.

The equivalence of (1) and (4) was unexpected and while they are purely global statements about G involving its typically infinite subsets, the proof crucially employs the finitary interpolation provided by (2). Also notice that the only examples of 0-Følner sets are the trivial ones: a finite group is a 0-Følner set in itself. Thus (3) represents a new phenomenon for which the Følner criterion provides no analog. The proof of Theorem 1.3 will also provide a quantitative relationship between ϵ-Ramsey sets and ϵ-Følner sets; this is the content of Section 4.

Let us say that a subset E of a group G is invariantly measurable if there is a μ in Pr(G) such that μ(gE) = μ(E) for all g in G. By the above theorem, a group is amenable exactly when all of its subsets are invariantly measurable. That the invariant measurability of sets can be witnessed by a single measure turns out not to be a phenomenon present in arbitrary groups.

Theorem 1.4. There are two invariantly measurable subsets of 𝔽_{2} which can not be simultaneously measured invariantly.

Theorem 1.3 tells us that if a group G is not amenable, then there is a single set E ⊆ G which can not be measured invariantly. It is natural to ask to what extent E can be specified by a finite amount of information. Let A be a fixed finite subset of G. If E ⊆ G, define

𝒳_{E}^{A} = {Eg^{−1} ∩ A : g ∈ G}.

(When A is clear from the context, the superscript will be suppressed.) Thus if A is a ball about the identity, Eg^{−1} ∩ A is a “picture” of E centered at g where the scope of the image is specified by A. The set 𝒳_{E} is then the collection of all such pictures of E taken from different vantage points in G. If 𝒴 is a collection of subsets of A, then we say that 𝒴 is realized in G if 𝒴 = 𝒳_{E} for some E ⊆ G.

A collection 𝒴 of subsets of a finite set A is ϵ-balanced if there is a probability measure μ on 𝒴 such that

|μ({Y ∈ 𝒴 : a ∈ Y }) − μ({Y ∈ 𝒴 : b ∈ Y })| ≤ ϵ

whenever a and b are in A. Balanced will be taken to mean 0-balanced. It follows from the Hahn-Banach Separation Theorem that a collection 𝒴 is unbalanced if and only if there is an f : A → ℝ such that ∑_{a∈A} f(a) = 0 and for every Y in 𝒴 , ∑_{a∈Y} f(a) > 0.

We will prove the following analog of Theorem 4.2 of [1].

Theorem 1.5. For a group G, the following are equivalent: (1) G is non amenable.

(2) There is a finite A ⊆ G and an unbalanced collection 𝒴 of subsets of A which is realized in G.

(3) There is a finite A ⊆ G for which there is no finite B which is 0-Ramsey with respect to A.

Thus in order to establish the non amenability of a group, it is sufficient to realize a subcollection of

𝒴_{f} = {Y ⊆ A : ∑_{a∈Y} f(a) > 0}

for some f : A → ℝ such that ∑_{a∈A} f(a) = 0. Balanced sets have been studied in game theory (e.g. [18]), although the focus has been on minimal balanced collections rather than the maximal unbalanced collections, which are most relevant to the present discussion.

The above theorems concern the amenability of discrete groups. The amenability of a topological group G can be formulated as follows: whenever G acts continuously on a compact space K, K supports an Borel probability measure which is preserved by the action of G. A strengthening of amenability in this context is that of extreme amenability: every continuous action of G on a compact space has a fixed point. In [9], Kechris, Pestov, and Todorcevic discovered a very general correspondence which equates the extreme amenability of the automorphism group of an ordered Fraïssé structure with the Ramsey Property of its finite substructures.

Theorem 1.6. [9] Let G be a closed subgroup of S_{∞}. The following are equivalent:

(1) G is extremely amenable.

(2) G = Aut(𝔊) where 𝔊 is a Fraïssé structure with an order relation and the finite substructures of 𝔊 have the Ramsey Property.

At the time of [9], it was unclear whether there was an analogous connection between amenability and Ramsey theory. In Section 7 it will be shown that such an analog does exist.

The notation will be mostly standard. Following a set-theoretic convention, I will sometimes abbreviate {0, …, k − 1} with k. The set of natural numbers is taken to include 0 and all counting will begin at 0. The letters i, j, k, l, m, n will be used to denote natural numbers unless otherwise stated. If H ⊆ G, then we will identify Pr(H) with the set of those μ in Pr(G) such that μ(H) = 1.

2. A Ramsey theoretic criterion for amenability

In this section we will prove most of Theorem 1.3, deferring the equivalence of amenability with (3) to the next section. Before we begin, it will be necessary to extend the evaluation map (ν, E) ↦ ν(E) to a bilinear map on Pr(G) × ℓ^{∞}(G) by integration. We will only need this for finitely supported ν in which case

ν(f) = ∑_{g∈B} ν({g})f(g)

We will define f(ν) = ν(f). Observe that the map (ν, f) ↦ ν(f) is bilinear.

When proving the theorem, it will be natural to further divide the task as follows.

Theorem 2.1. Let G be a group and H ⊆ G be closed under products and contain the identity of G. The following are equivalent:

(1) For every E ⊆ G and every finite A ⊆ H, there is a μ in Pr(H) such that μ(g^{−1}E) = μ(E) for every g ∈ A.

(2) For every finite A ⊆ H, there is a finite B ⊆ H such that B is \frac{1}{2}-Ramsey with respect to A.

(3) There is a positive q < 1 such that for every finite A ⊆ H, there is a finite B ⊆ H such that if f : B → [0, 1], then there is a ν in Pr(B) such that for all g, g′ ∈ A, gν is in Pr(B) and

|gν(f) − g′ν(f)| ≤ q.

(4) For every finite A ⊆ H and ϵ > 0, there is a finite B ⊆ H such that if f : B → [0, 1] then there is a ν in Pr(B) such that for all g, g′ ∈ A, gν is in Pr(B) and

|gν(f) − g′ν(f)| < ϵ.

(5) There is a μ ∈ Pr(H) such that for every E ⊆ G, μ(g^{−1}E) = μ(E) whenever g is in H.

Remark 2.2. The above generality allows H to be the positive elements of the group with respect to some generating set. This will be useful below when reformulating the amenability problem for Thompson’s group F.

Proof. Observe that trivially (5⇒1). It is therefore sufficient to prove (1⇒2⇒3⇒4⇒5).

(1⇒2): Suppose that (2) is false for some finite A ⊆ H. I claim there is a set E ⊆ H such that for every μ ∈ Pr(H), there are g, h ∈ A such that |μ(g^{−1}E) − μ(h^{−1}E)| > \frac{1}{2} — a condition which implies the failure of (1). By replacing G by a subgroup if necessary, we may assume that G is generated by A and in particular that G is countable. Let B_{n} (n < ∞) be an increasing sequence of finite sets covering H. Define T_{n} to be the collection of all pairs (n, E) where E is a subset of B_{n} which witness that B_{n} is not \frac{1}{2}-Ramsey with respect to A. Let T = ⋃_{n} T_{n} and if (n, E) and (n′, E′) are in T, define (n, E) <_{T} (n′, E′) if n < n′ and E = E′ ∩ B_{n}. Observe that if (n′, E′) is in T_{n′} and n < n′, then (n, E′ ∩ B_{n}) is in T_{n}. Thus (T, <_{T}) is an infinite finitely branching tree and hence there is an E ⊆ H such that (n, E ∩ B_{n}) is in T_{n} for each n. If there were a measure ν such that |ν(g^{−1}E) − ν(h^{−1}E)| < \frac{1}{2} for all g, h ∈ A, there would exist such a ν which has a finite support S. But this would be a contradiction since then S ∪ (A · S) would be contained in some B_{n} and would witness that (n, E ∩ B_{n}) was not in T_{n}.

(2⇒3): Let A ⊆ H be a given finite set and let B ⊆ H be finite and \frac{1}{2}-Ramsey with respect to A. It suffices to prove that B satisfies the conclusion of (3) with q = 3/4. Let f : B → [0, 1] be given and define E = {b ∈ B : f(b) ≥ 1/2}. By assumption, there is a ν in Pr(B) such that Pr(A)ν ⊆ Pr(B) and for all g, g′ ∈ A, |gν(E) − g′ν(E)| ≤ 1/2. Also

0 ≤ min(gν(f − \frac{1}{2}χ_{E}), g′ν(f − \frac{1}{2}χ_{E}))

max(gν(f − \frac{1}{2}χ_{E}), g′ν(f − \frac{1}{2}χ_{E})) ≤ 1/2

Notice that if 0 ≤ a, b ≤ 1/2, then |a − b| ≤ 1/2. Therefore for all g, g′ ∈ A

|gν(f) − g′ν(f)| =

|\frac{1}{2}(gν(E) − g′ν(E)) + gν(f − \frac{1}{2}χ_{E}) − g′ν(f − \frac{1}{2}χ_{E})|

≤ \frac{1}{2}|gν(E) − g′ν(E)| + |gν(f − \frac{1}{2}χ_{E}) − g′ν(f − \frac{1}{2}χ_{E})|

≤ 1/4 + 1/2.

(3⇒4): Let A ⊆ H and ϵ > 0 be given. Let n be such that q^{n} < ϵ and construct a sequence B_{i} (i ≤ n) such that, setting B_{0} = A, B_{i+1} satisfies the conclusion of (3) with respect to B_{i}. Construct ν_{i} (i < n) by downward recursion such that Pr(B_{i})ν_{i} ⊆ Pr(B_{i+1}) and for all g, g′ ∈ B_{i},

|gν_{i} ⋯ ν_{n−1}(f) − g′ν_{i} ⋯ ν_{n−1}(f)| ≤ q^{n−i}

This is achieved by applying (3) to the function f_{i} defined on B_{i+1} by

f_{n−1} = f

f_{i}(g) = (1/q)^{n−i−1}(gν_{i+1} ⋯ ν_{n−1}(f) − min_{g′∈B_{i+1}} g′ν_{i+1} ⋯ ν_{n−1}(f))

if i < n − 1. Our inductive hypothesis implies that the range of f_{i} is contained within [0, 1]. Therefore there is a ν_{i} such that Pr(B_{i})ν_{i} ⊆ Pr(B_{i+1}) and

|gν_{i}(f_{i}) − g′ν_{i}(f_{i})| ≤ q

holds for every g, g′ ∈ B_{i} and thus

(1/q)^{n−i−1}|gν_{i} ⋯ ν_{n−1}(f) − g′ν_{i} ⋯ ν_{n−1}(f)|
= (1/q)^{n−i−1}|f(gν_{i} ⋯ ν_{n−1}) − f(gν_{i} ⋯ ν_{n−1})|
= |f_{i}(gν_{i}) − f_{i}(g′ν_{i})| = |gν_{i}(f_{i}) − g′ν_{i}(f_{i})| ≤ q.

Multiplying both sides of the inequality by q^{n−i−1}, we see that ν_{i} satisfies the desired inequality. This completes the recursion. If ν = ν_{0} ⋯ ν_{n−1}, then for all g, g′ in A = B_{0} we have that

|gν(f) − g′ν(f)| ≤ q^{n} < ϵ.

(4⇒5): Observe that, by compactness, it is sufficient to prove that for every ϵ > 0, every finite list E_{i} (i < n) of subsets of H, and g_{i} (i < n) in H, there is a finitely supported μ ∈ Pr(H) such that for all i < n

|μ(g_{i}^{−1}E_{i}) − μ(E_{i})| < ϵ.

Set B_{0} = {e_{G}} ∪ {g_{i} : i < n} and construct a sequence B_{i} (i ≤ n) such that B_{i+1} satisfies (4) with B_{i} in place of A and ϵ/2 in place of ϵ. Inductively construct ν_{i} (i < n) by downward recursion on i. If ν_{j} (i < j < n) has been constructed, let ν_{i} ∈ Pr(B_{i+1}) be such that Pr(B_{i})ν_{i} ⊆ Pr(B_{i+1}) and

|μν_{i} ⋯ ν_{n−1}(E_{i}) − μ′ν_{i} ⋯ ν_{n−1}(E_{i})| < ϵ/2

for all μ, μ′ ∈ Pr(B_{i}). Set μ = ν_{0} ⋯ ν_{n−1}. If i < n, then since ν_{0} ⋯ ν_{i−1} and g_{i}^{−1}ν_{0} ⋯ ν_{i−1} are in Pr(B_{i}),

|g_{i}μ(E_{i}) − ν_{i} ⋯ ν_{n−1}(E_{i})| < ϵ/2
|μ(E_{i}) − ν_{i} ⋯ ν_{n−1}(E_{i})| < ϵ/2

and therefore |μ(g_{i}^{−1}E_{i}) − μ(E_{i})| < ϵ. □

I will finish this section with the following basic example, which shows that existence of 0-Ramsey sets for ℤ is just the well known Pigeon Hole Principle. Suppose that A ⊆ ℤ is finite; without loss of generality, A = {0, …, m − 1}. Let B = {1, …, 2^{m} + m + 1} and suppose that E ⊆ B. Notice that {A ∩ (E − i) : i ∈ ℤ} has at most 2^{m} elements and therefore there are 1 ≤ i < j ≤ 2^{m} + 1 such that for all 0 ≤ k < m, k + i is in E if and only if k + j is in E. Let ν be the uniform measure on the interval {i, …, j − 1}. By our choice of i and j,

|E ∩ {i, …, j − 1}| = |E ∩ {i + k, …, j − 1 + k}|

and thus ν(E) = ν(E − k) for all 0 ≤ k < m.

3. The amenability problem for Thompson’s group F

Perhaps the best known problem concerning the amenability of a specific group asks whether Richard Thompson’s group F is amenable. In this section I will discuss how this problem reduces to a natural finite Ramsey-theoretic statement. I will only briefly review the terminology and basic facts about Thompson’s group; the reader is referred to [2] and [10] for further background and justification for some of the statements made below.

Thompson’s group F is the group with generators x_{i} (i < ∞) satisfying the relations x_{i}^{−1}x_{n}x_{i} = x_{n+1} whenever i < n. The positive elements of F are the products of these generators. It is easy to see that x_{0} and x_{1} already generate the group and it is well known (see [2]) that every element of F can be written as a fraction of positive elements. Thus by Ore’s theorem (see [17]), F is amenable if and only if its action on its positive elements is amenable.

The action of F on its positive elements can be described as follows. Let (𝕋, ) denote the free binary system on one generator. The elements of 𝕋 are just formal sums — with associating parentheses — of some number of 1’s. They can naturally be thought of as rooted ordered binary trees in the sense of [2] and the following partial action of F on 𝕋

x_{0} · ((A B) C) = A (B C)
x_{1} · (S ((A B) C)) = S (A (B C))

is equivalent to the partial action of F on its positive elements (see [10]).

By unraveling the definitions, one can reformulate the amenability of F in the following way. Let 𝕋_{n} denote those elements of 𝕋 with n leafs and let 𝔸_{n} denote the set of probability measures on 𝕋_{n}. A copy of 𝕋_{m} in 𝕋_{n} is a collection of the form {T (U_{1}, …, U_{m}) : T ∈ 𝕋_{m}} where U_{i} (1 ≤ i ≤ m) is an ordered sequence of elements of 𝕋 with a total of n leafs. Here T (U_{1}, …, U_{m}) denotes the result of substituting U_{i} for the i^{th} occurrence of the generator in T. A copy of 𝕋_{m} in 𝔸_{n} is a convex combination of copies of 𝕋_{m} in 𝕋_{n} (formally we take a convex combination of maps of the form T ↦ T (U_{1}, …, U_{m}) to obtain a map from 𝕋_{m} into 𝔸_{n} and then collect the range of this map).

Theorem 3.1. The following are equivalent:

(1) Thompson’s group F is amenable.

(2) For every m there is an n such that if f : 𝕋_{n} → {0, 1}, then there is a copy of 𝕋_{m} in 𝔸_{n} on which f is constant.

In order to see the relationship to Ramsey’s theorem, observe that Ramsey’s theorem can be formulated in the following way. If n and k are natural numbers, let n^{[k]} denote all partitions of {1, …, n + 1} into k + 1 intervals. Notice that there are canonical bijections between this set and the k element subsets of {1, …, n} and also with sequences of natural numbers of length k + 1 which add to n + 1. If m ≥ k and X is in n^{[m]}, let X^{[k]} denote all elements of n^{[k]} which are refined by X. In this language, Ramsey’s theorem asserts that for every m and k there is an n such that if n^{[k]} is colored red and blue, there is an X in n^{[m]} such that X^{[k]} is monochromatic.

Let n^{[[k]]} denote all families X of intervals in {1, …, n+1} such that:

• the ⊆-minimal elements of X are the singletons of {1, …, n+1} and the ⊆-maximal elements of X are an element of n^{[k]}.

• any element of X with more than one element is the union of two other elements of X.

• if x, y are in X, then x ⊆ y, y ⊆ x, or x ∩ y = ∅. Thus an element of n^{[[k]]} is the result of starting with {{1}, …, {n+1}} and iteratively joining consecutive pairs of intervals until one obtains a partition of {1, …, n + 1} into k + 1 intervals. There is a canonical correspondence between n^{[[k]]} and sequences from 𝕋 of length k + 1 where the total number of leaves is n + 1.

The amenability of Thompson’s group is now the statement that for every m and k there is an n such that if n^{[[k]]} is colored with red and blue, there is a probability measure Ξ on n^{[[m]]} such that Ξ^{[[k]]} is monochromatic. (As above, Ξ is regarded as a formal convex combination of elements X of n^{[[m]]} and Ξ^{[[k]]} consists of the corresponding convex combinations of the elements of the X^{[[k]]}’s.) Observe that the case k = 1 is the strongest assertion and it is, modulo the definitions, the reformulation given in Theorem 3.1.

4. Comparing the Ramsey and Følner functions

The purpose of this section is to define the Ramsey function of a finitely generated group with respect to a finite generating set and relate it to the Følner function which has been studied in, e.g., [3], [4], [8]. The main result of this section is due to Henry Towsner, answering a question in an early draft of this paper: The Følner function for a given group and generating set can be obtained from the Ramsey function by primitive recursion. It is included with his kind permission.

We will now turn to the definitions of the Følner and Ramsey functions. Let G be a group with a fixed finite generating set S (which is not required to be closed under inversion). Let B_{n} denote the elements of G whose distance from the identity is at most n in the word metric. Define the following functions:

• Føl_{G,S}(k) is the minimum cardinality of a 1/k-Følner set with respect to the generating set S.

• F_{G,S}(m, ϵ) is the minimum n such that there is a ν in Pr(B_{n}) such that Pr(B_{m})ν ⊆ Pr(B_{n}) and ∑_{g∈B_{m}} ||gν − ν||_{ℓ_{1}} < ϵ.

• R_{G,S}(m, ϵ) is the minimum n such that B_{n} is ϵ-Ramsey with respect to B_{m}.

• R̃_{G,S}(m, ϵ, l) is the minimum n such that if f_{i} (i < l) is a sequence of functions from B_{n} into [0, 1], then there is a ν ∈ Pr(B_{n}) such that Pr(B_{m})ν ⊆ Pr(B_{n}) and such that for every g, g′ ∈ B_{m} and i < l,

|gν(f_{i}) − g′ν(f_{i})| < ϵ

Set R_{G,S}(m) = R_{G,S}(m, 1/2) and R̃_{G,S}(m, ϵ) = R̃_{G,S}(m, ϵ, 1). The definition of F_{G,S} is formulated so that it is a triviality that R_{G,S}(m, k) ≤ R̃_{G,S}(m, k) ≤ F_{G,S}(m, k) holds for all m and k. The following relationship holds between F_{G,S} and Føl_{G,S}:

Føl_{G,S}(k) ≤ (2|S| + 1)^{F_{G,S}(1,1/k)}

The reason for this is that the n-ball in G with respect to S contains at most (2|S| + 1)^{n} elements and if ν ∈ ℓ^{1}(G) is such that

∑_{g∈S} ||gν − ν||_{ℓ^{1}} < ϵ

then the support of ν contains an ϵ-Følner set with respect to S [11]. The proof of Theorem 2.1 shows that

R̃_{G,S}(m, ϵ) ≤ R_{G,S}^{p}(m)

whenever (3/4)^{p} < ϵ (here R_{G,S}^{p} denotes the p-fold composition of R_{G,S}). Furthermore, it shows that

R̃_{G,S}(m, ϵ, l) ≤ R̃_{G,S}(R̃_{G,S}(m, ϵ, l − 1), ϵ)
= R̃_{G,S}(R̃_{G,S}(… R̃_{G,S}(m, ϵ) …, ϵ), ϵ) ≤ R_{G,S}^{lp}(m)

whenever l > 1. Finally we have the following proposition.

Proposition 4.1. F_{G,S}(m, 2ϵ|S|) ≤ R̃_{G,S}(m, ϵ, |S|).

Proof. Let B = B_{n} where n = R̃_{G,S}(m, ϵ, |S|). Define

C = {⟨gν − ν : g ∈ S⟩ : ν ∈ Pr(B) and Pr(S)ν ⊆ Pr(B)}.

U = {ξ ∈ (ℓ^{1}(B))^{S} : ∑_{g∈S} ||ξ_{g}||_{ℓ^{1}} < 2ϵ|S|}

Observe that C and U are both convex subsets of (ℓ^{1}(B))^{S} with C being compact and U being open. If C ∩ U is non empty, then there is a ν in Pr(B) such that Pr(S)ν ⊆ Pr(B) and

∑_{g∈S} ||gν − ν||_{ℓ^{1}} < 2ϵ|S|.

In particular, we would have that F_{G,S}(m, 2ϵ|S|) ≤ n = R̃_{G,S}(m, ϵ, |S|).

Now suppose for contradiction that C and U are disjoint. By the Hahn-Banach separation theorem (see [19, 3.4]), there is a linear functional Λ defined on (ℓ^{1}(B))^{S} such that, for some r ∈ ℝ, Λξ < r if ξ ∈ U and r ≤ Λξ if ξ ∈ C. In the present setting, such a functional Λ takes the form

Λξ = ∑_{g∈S} ξ_{g}f_{g}

for some ⟨f_{g} : g ∈ S⟩ ∈ (ℓ^{∞}(B))^{S}. If we give (ℓ^{1}(B))^{S} the norm by identifying it with ℓ^{1}(B × S), then we may assume that Λ has norm 1. Since ℓ^{1}(B × S)^{∗} is isometric to ℓ^{∞}(B × S), it follows that |f_{g}(b)| ≤ 1 for all b and g with equality obtained for some (b, g) ∈ B ×S. It follows that we may take r = ϵ|S|. This is a contradiction, however, since by our choice of B = B_{n}, there is a ν in Pr(B) such that Pr(S)ν ⊆ Pr(B) and for all g ∈ S,

|gν(f_{g}) − ν(f_{g})| < 2ϵ

(the factor of 2 is because f_{g} maps into an interval of length 2) and therefore ∑_{g∈S} |gν(f_{g}) − ν(f_{g})| < 2ϵ|S|. □

Putting this together, we have the following upper bound on the Følner function in terms of the iterated Ramsey function.

Theorem 4.2. Føl_{G,S}(k) ≤ (2s + 1)^{R^{ps}(1)} whenever (3/4)^{p} < 1/(2ks) where s = |S|.

5. Invariantly measurable sets in 𝔽_{2}

In light of the theorem of the previous section, it is natural to define, for an arbitrary group G, the collection ℳ_{G} of subsets of G which are invariantly measurable. It is tempting to suspect that Theorem 1.3 might be subsumed in a more general result which asserts that, in any group G, there is a μ which measures each element of ℳ_{G} invariantly. Theorem 1.4, whose proof we now turn to, asserts that this is not the case.

Proof. Let a and b denote the generators of 𝔽_{2} and let A denote the collection of all elements of 𝔽_{2} whose reduced word begins with a or a^{−1}. Let h : 𝔽_{2} → ℤ be the homomorphism which sends a to 1 and b to −1 and define Z_{k} = {w ∈ 𝔽_{2} : h(w) ≥ k}, setting Z = Z_{0}. Define

A^{+} = {g ∈ A : h(g) > 0} A^{−} = {g ∈ A : h(g) ≤ 0}.

Notice that A can not be measured invariantly since {b^{k}A : k ∈ ℕ} and {a^{k}(𝔽_{2} \ A) : k ∈ ℕ} are both infinite pairwise disjoint families. If μ measured both A^{+} and A^{−} invariantly, it would measure A = A^{+} ∪ A^{−} invariantly.

It therefore suffices to find measures μ_{0} and μ_{1} such that μ_{i}(wZ) = i for i = 0, 1 and w ∈ 𝔽_{2}. Such measures are constructed by extending the families {𝔽_{2} \ Z_{k} : k ∈ ℤ} and {Z_{k} : k ∈ ℤ}, each of which have the finite intersection property, to ultrafilters, and regarding them as elements of Pr(𝔽_{2}). □

Remark 5.1. It is not clear whether 𝔽_{2} can be replaced by an arbitrary non amenable group in Theorem 1.4, even if one allows finitely many invariantly measurable sets in place of two.

6. A criterion for non amenability: unbalanced puzzles

The purpose of this section is to prove Theorem 1.5. The following two simple propositions capture most of what is left to prove.

Proposition 6.1. Let G be a group, ϵ ≥ 0, and A be a finite subset of G. If E ⊆ G, 𝒴 is ϵ-balanced, and B is a finite set such that

𝒴 = {X_{E}(g) : g ∈ B},

then there is a ν ∈ Pr(B) such that |aν(E) − a′ν(E)| ≤ ϵ for all a, a′ ∈ A.

Remark 6.2. Notice that a typical B satisfying the hypothesis of this proposition may well satisfy that it is its own boundary in the Cayley graph, even if ϵ = 0. This is again quite different than what is possible with Følner sets (even if the Følner sets are allowed to be “weighted”).

Proof. Let μ ∈ Pr(𝒴 ) be such that

|μ({X ∈ 𝒴 : a ∈ X}) − μ({X ∈ 𝒴 : a′ ∈ X})| ≤ ϵ

for every a, a′ ∈ A. By replacing B by a subset, we may assume that for each b ≠ b′ in B, X_{E}(b) ≠ X_{E}(b′). Define ν ∈ Pr(B) by ν({b}) = μ({X_{E}(b)}). Now suppose that a ∈ A.

ν(a^{−1}E) = ∑{ν({b}) : b ∈ a^{−1}E}
= ∑{μ({X_{E}(b)}) : ab ∈ E} = μ({X ∈ 𝒴 : a ∈ X})

The conclusion now follows from our choice of μ. □

Proposition 6.3. Let G be a group and A be a finite subset of G. If E ⊆ G and there is a ν ∈ Pr(G) such that

|ν(a^{−1}E) − ν(b^{−1}E)| ≤ ϵ

for every a, b ∈ A, then

{X ∈ 𝒳_{E} : ν({g ∈ G : X_{E}(g) = X}) > 0}

is ϵ-balanced (and in particular 𝒳_{E} is ϵ-balanced).

Proof. Let G, A, E, and ν be given as in the statement of the proposition. For each X in 𝒳_{E}, define

μ({X}) = ν({g ∈ G : X_{E}(g) = X}).

It is sufficient to show that if a is in A, then ∑_{X∋a} μ({X}) = ν(a^{−1}E). To this end

∑_{X∋a} μ({X}) = ν({g ∈ G : a ∈ X_{E}(g)})

= ν({g ∈ G : ag ∈ E}) = ν(a^{−1}E).

□

Now we are ready to prove Theorem 1.5. All implications will be established by proving the contrapositive. The implication (1⇒2) follows from Proposition 6.1 together with the equivalence of (1) and (4) in Theorem 1.3. The implication (2⇒3) is given by Proposition 6.3.

Finally, in order to see the implication (3⇒1), suppose that G is amenable and A ⊆ G is finite. Let ϵ > 0 be such that if 𝒴 is a collection of subsets of A which is ϵ-balanced, then 𝒴 is ϵ′-balanced for all ϵ′ > 0. This is possible since the collection of all families of subsets of A is finite. Let B be ϵ-Ramsey. It suffices to prove that B is ϵ′-Ramsey for each ϵ′ > 0 since it then follows by compactness that B is 0-Ramsey. Suppose that E ⊆ B. By our assumption on B, there is a ν ∈ Pr(B) such that Aν ⊆ Pr(B) and such that

|gν(E) − g′ν(E)| ≤ ϵ

for all g, g′ ∈ A. By Proposition 6.3,

𝒴 = {X_{E}(g) : (g ∈ B) ∧ (Ag ⊆ B)}

is ϵ-balanced. By assumption this collection is ϵ′-balanced for every ϵ′ > 0. Therefore by Proposition 6.1, there is a ν in Pr(B) such that Aν ⊆ Pr(B) and

|gν(E) − g′ν(E)| ≤ ϵ′.

for all g, g′ ∈ A. This finishes the proof of the theorem.

I will finish this section by mentioning an intriguing problem concerning which unbalanced sets are required to witness the non amenability of all non amenable groups.

Problem 6.4. Is there a finite list ℬ of unbalanced families such that any non amenable group contains a realization of an isomorphic copy of an element of ℬ?

Here two unbalanced families are isomorphic if one is the set-wise image of the other under a bijection of the underlying sets.

7. Structural Ramsey theory and KPT Theory

In this section I will place the results of the present paper into the context of the theory of Kechris, Pestov, and Todorcevic developed in [9] which equates the property of extreme amenability of certain automorphism groups to structural Ramsey theory. First we will need to recall some notation and terminology from [9]; further reading can be found there. A Fraïssé structure is a countable relational structure 𝔄 which is ultrahomogeneous — every finite partial automorphism extends to an automorphism of the whole structure. If moreover 𝔄 includes a relation which is a linear order, then 𝔄 is said to be a Fraïssé order structure. Some notable examples of such structures are (ℚ, ≤), the random graph, and rational Urysohn space. If G is a countable group, then we may also associate to G the Fraïssé structure 𝔊 = (G; R_{g} : g ∈ G) where

R_{g} = {(a, b) ∈ G^{2} : ab^{−1} = g}

Observe that the automorphisms of 𝔊 are given by right translation and therefore Aut(𝔊) ≃ G. Since every automorphism of 𝔊 is determined by where it sends the identity, Aut(𝔊) is discrete as a subgroup of the group of all permutations of G equipped with the topology of point-wise convergence.

If 𝔄 is a Fraïssé (order) structure, then Age(𝔄) is the collection of finite substructures of 𝔄. A collection arising in this way is called a Fraïssé (order) class. It should be noted that Fraïssé (order) classes have an intrinsic axiomatization, although this will not be relevant for the present discussion.

If 𝒞 is a Fraïssé class and 𝔅 and 𝔄 are structures in 𝒞, then let \binom{𝔅}{𝔄} denote the collection of all embeddings of 𝔄 into 𝔅. Define ℭ → (𝔅)_{k}^{𝔄} if whenever f : \binom{ℭ}{𝔄} → k, there is a β in \binom{ℭ}{𝔅} such that f is constant on \binom{β}{𝔄} = \{β ∘ α : α ∈ \binom{𝔅}{𝔄}\}. A Fraïssé class 𝒞 has the Ramsey Property if for every 𝔄 and 𝔅 in 𝒞, there is a ℭ in 𝒞 such that ℭ → (𝔅)_{2}^{𝔄}.

The main result of [9] is that, for a Fraïssé order structure 𝔄, Aut(𝔄) is extremely amenable if and only if Age(𝔄) has the Ramsey Property. The power of this theorem comes from the rich literature on the Ramsey Property of Fraïssé classes. That the finite linear orders form a Ramsey class is just a reformulation of the finite form of Ramsey’s theorem. More sophisticated examples are the classes of finite ordered graphs [13] [14], finite naturally ordered Boolean algebras [7], finite ordered metric spaces [12], and finite dimensional naturally ordered vector spaces over a finite field [6]. The branch of mathematics concerned with such results is known as structural Ramsey theory.

If G is a countable group, the collection 𝒢 of finite substructures of 𝔊 will never form a Ramsey class. One reason for this is the result of Veech [22] asserting that a locally compact group can never be extremely amenable. In the case of finitely generated groups, this can be seen explicitly: the failure of the Ramsey property is witnessed by the function f : \binom{𝔊}{𝔢} → 2 defined by

f(g) ≡ d_{S}(e, g) mod 2

where S is a generating set for G, d_{S} is the word metric, and 𝔢 is {e} regarded as a substructure of 𝔊. (Observe that \binom{𝔊}{𝔢} can naturally be identified with the singletons in G.)

We can however modify the Ramsey Property as follows. Let 𝔄 and 𝔅 be substructures of a relational structure 𝔛 with 𝔄 being finite. Define \left⟨{𝔅 \atop 𝔄}\right⟩ to be the collection of all finitely supported probability measures on \binom{𝔅}{𝔄}. If f : \binom{𝔅}{𝔄} → ℝ, then f extends to an affine function defined on the vector space generated by \binom{𝔅}{𝔄}; this extension will also be denoted by f. Extending ∘ bilinearly, we define \binom{β}{𝔄} and \left⟨{β \atop 𝔄}\right⟩ when β is in \left⟨{𝔛 \atop 𝔅}\right⟩.

Define ℭ → ⟨𝔅⟩_{k}^{𝔄} to mean that whenever f : \binom{ℭ}{𝔄} → k, there is a β ∈ \left⟨{ℭ \atop 𝔅}\right⟩ such that if α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩,

|f(α) − f(α′)| ≤ 1/2.

It follows from the definitions that if A and B are finite subsets of a group G, then 𝔅 → ⟨𝔄⟩_{2}^{𝔢} is equivalent to asserting that B is 1/2-Ramsey with respect to A. Therefore, by Theorem 1.3 the amenability of G is equivalent to the following convex Ramsey property of 𝒢: for every 𝔄 and 𝔅 in 𝒢 there is a ℭ in 𝒢 such that ℭ → ⟨𝔅⟩_{2}^{𝔄}. The purpose of the remainder of this section is to prove the following generalization of Theorem 2.1 to the setting of automorphism groups of Fraïssé structures.

Theorem 7.1. If 𝔛 is a Fraïsse structure, then the following are equivalent:

(1) for every 𝔄 and 𝔅 in Age(𝔛), and every f : \binom{𝔛}{𝔄} → \{0, 1\}, there is a β in \left⟨{𝔛 \atop 𝔅}\right⟩ such that for every α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩, |f(α) − f(α′)| ≤ 1/2.

(2) Age(𝔛) satisfies the convex Ramsey property: for every 𝔄 and 𝔅 in Age(𝔛) there is a ℭ in Age(𝔛) such that ℭ → ⟨𝔅⟩_{2}^{𝔄}.

(3) there is a p < 1 such that for every 𝔄 and 𝔅 in Age(𝔛) there is a ℭ in Age(𝔛) such that for every f : \binom{ℭ}{𝔄} → [0, 1], there is a β in \left⟨{ℭ \atop 𝔅}\right⟩ such that for every α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩,

|f(α) − f(α′)| ≤ p.

(4) for every 𝔄 and 𝔅 in Age(𝔛), every ϵ > 0, there is a ℭ in Age(𝔛) such that for every f : \binom{ℭ}{𝔄} → [0, 1], there is a β in \left⟨{ℭ \atop 𝔅}\right⟩ such that for every α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩,

|f(α) − f(α′)| ≤ ϵ.

(5) for every 𝔄 and 𝔅 in Age(𝔛), every ϵ > 0, and n, there is a ℭ in Age(𝔛) such that for every sequence f_{i} (i < n) of functions from \binom{ℭ}{𝔄} to [0, 1], there is a β in \left⟨{ℭ \atop 𝔅}\right⟩ such that for every α in \left⟨{β \atop 𝔄}\right⟩,

|f_{i}(α) − f_{i}(α′)| ≤ ϵ.

(6) Aut(𝔛) is amenable.

Remark 7.2. The equivalence of (5) and (6) was noticed by Todor Tsankov, prior to the results of this paper. I would like to thank him for a helpful conversation in which it became clear that the above theorem should be true.

Proof. I will only prove the implications (1⇒2), (4⇒5), (5⇒6), and (6⇒1). The remaining implications are only notationally different from their counterparts in Theorem 2.1 and the implications which will be proved will demonstrate how these notational adaptations are made.

To see (1⇒2), we will suppose that (2) is false and prove that (1) is false. To this end, let 𝔄 and 𝔅 be given. Let X be the underlying set for the structure 𝔛 and let X_{n} (n < ∞) be an increasing sequence of finite sets whose union is X. For each n, fix a f_{n} : \binom{𝔛_{n}}{𝔄} → 2 such that there is no β ∈ \left⟨{𝔛_{n} \atop 𝔅}\right⟩ such that for all α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩, |f_{n}(α)−f_{n}(α′)| ≤ 1/2. Find a subsequence f_{n_{k}} (k < ∞) such that for every m, if k, k′ ≥ m, then

f_{n_{k}} ↾ \binom{𝔛_{m}}{𝔄} = f_{n_{k′}} ↾ \binom{𝔛_{m}}{𝔄}

Define f : \binom{𝔛}{𝔄} → \{0, 1\} by f(α) = f_{n_{k}}(α) whenever the range of α is contained in 𝔛_{m} and m ≤ k. If there were a β in \left⟨{𝔛 \atop 𝔅}\right⟩ such that for all α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩, |f(α) − f(α′)| ≤ 1/2, then such a β would be contained in \left⟨{𝔛_{m} \atop 𝔅}\right⟩ for some m. Then for any k > m, β would contradict our choice of f_{n_{k}}.

In order to see the implication (4⇒5), let 𝔄, 𝔅, and ϵ > 0 be given. Construct ℭ_{i} (i ≤ n) such that ℭ_{0} = 𝔅 and for all i ≤ n, if f : \binom{ℭ_{i}}{𝔄} → [0, 1], there is a ν ∈ \left⟨{ℭ_{i} \atop ℭ_{i−1}}\right⟩ such that for all α, α′ ∈ \left⟨{ν \atop 𝔄}\right⟩, |f(α)−f(α′)| ≤ ϵ. Define β_{n} = ℭ_{n} and construct β_{i} (i < n) by downward induction such that β_{i} is in \left⟨{β_{i+1} \atop ℭ_{i}}\right⟩ and if α, α′ ∈ \left⟨{β_{i} \atop 𝔄}\right⟩, then |f_{i}(α) − f_{i}(α′)| < ϵ. This is achieved by applying our hypothesis on ℭ_{i+1} to the function f̃_{i} : \binom{ℭ_{i+1}}{𝔄} → [0, 1] defined by f̃_{i}(α) = f_{i}(β_{i+1} ∘ α). If ν_{i} ∈ \left⟨{ℭ_{i+1} \atop ℭ_{i}}\right⟩ is such that for all α, α′ ∈ \left⟨{ℭ_{i+1} \atop 𝔄}\right⟩

|f̃_{i}(α) − f̃_{i}(α′)| ≤ ϵ

then β_{i} = β_{i+1} ∘ ν_{i} is as desired. Since i < j < n implies \left⟨{β_{i} \atop 𝔄}\right⟩ ⊆ \left⟨{β_{j} \atop 𝔄}\right⟩, we have that β = β_{0} satisfies the conclusion of (5).

Next we will prove (5⇒6). We will use the following characterization of amenability of a topological group: G is amenable if and only if whenever G acts continuously on a compact space K, K admits a (countably additive) G-invariant Borel probability measure. To this end, fix a continuous action of Aut(𝔛) on a compact space K. Recall that the Borel probability measures form a weak* compact subset of C(K)^{∗}. Therefore it is sufficient to prove that for every ϵ > 0, every sequence f_{i} (i < n) of elements of C(K), and every sequence g_{i} (i < n) of elements of Aut(𝔛), there is a finitely supported measure ν on X such that for every i < n

|f_{i}(g_{i} · ν)) − f_{i}(ν)| ≤ ϵ.

Let f_{i} (i < n) and g_{i} (i < n) be given and assume without loss of generality that f_{i} maps into [0, 1].

By the compactness of K, there is an open neighborhood U of id_{𝔛} such that if g is in U, then for all i < n

|f_{i}(g · ν) − f_{i}(ν)| ≤ \frac{ϵ}{2}

(Here we have extended the action linearly to an action of Aut(𝔛) on the finitely supported measures. Similarly, elements of C(K) are extended affinely to the finitely supported measures on K.) Therefore there is a finite substructure 𝔄 of 𝔛 such that if g ↾ 𝔄 = id_{𝔄}, then g is in U. Let 𝔅 be the finite substructure of 𝔛 with domain

B = A ∪ ⋃_{i<n} g_{i}^{−1}(A).

Let ℭ be the finite substructure of 𝔛 which satisfies the conclusion of (5) with ϵ/2 in place of ϵ.

Fix an element x_{0} of K. Observe that if i < n and g and h are in Aut(𝔛) are such that g^{−1} ↾ 𝔄 = h^{−1} ↾ 𝔄, then

|f_{i}(g · x_{0}) − f_{i}(h · x_{0})| ≤ \frac{ϵ}{2}

This is because otherwise gh^{−1} ∈ U and x = h · x_{0} would contradict our choice of U.

For each f in C(K), define f̃: \binom{𝔛}{𝔄} → [0, 1] by

f̃(α) = inf{f(h · x_{0}) : h ∈ Aut(𝔛) ∧ h^{−1} ↾ 𝔄 = α}.

By our choice of ℭ, there is a β in \left⟨{ℭ \atop 𝔅}\right⟩ such that for every α, α′ ∈ \left⟨{β \atop 𝔄}\right⟩ and i < n,

|f̃_{i}(α) − f̃_{i}(α′)| ≤ \frac{ϵ}{2}.

Let β_{j} (j < m) be the elements of \binom{ℭ}{𝔅} such that for some choice of positive λ_{j} (j < m), β = ∑_{j<m} λ_{j}β_{j}. For each j < m, fix an h_{j} ∈ Aut(𝔛) such that h_{j} extends β_{j}. This is possible since 𝔛 is ultrahomogeneous. Finally, define

ν = ∑_{j<m} λ_{j}δ_{h_{j}^{−1}·x_{0}}

where δ_{x} denotes the point mass at x. Define α_{i} = g_{i}^{−1} ↾ 𝔄, observing that α_{i} ∈ \binom{𝔅}{𝔄}. Now for each i < n,

|f_{i}(g_{i} · ν) − f(ν)| = |f_{i}(g_{i} ∑_{j<m} λ_{j} · δ_{h_{j}^{−1}·x_{0}}) − f_{i}(∑_{j<m} λ_{j}δ_{h_{j}^{−1}·x_{0}})|

= |f_{i}(∑_{j<m} λ_{j}(g_{i} ∘ h_{j}^{−1}) · δ_{x_{0}}) − f_{i}(∑_{j<m} λ_{j}h_{j}^{−1} · δ_{x_{0}})|

≤ |f̃_{i}(β ∘ α_{i}) − f̃_{i}(β ∘ id_{𝔄})| + \frac{ϵ}{2} ≤ ϵ

which is what we needed to prove.

Finally, we will prove (6⇒1). To this end, let 𝔄 and 𝔅 be given and let f_{0} : \binom{𝔛}{𝔄} → 2 be arbitrary. Observe that 2^{\binom{𝔛}{𝔄}} is a compact space and that Aut(𝔛) acts continuously on 2^{\binom{𝔛}{𝔄}} on the left by g · f(α) = f(g^{−1} ∘ α). Let Z denote the orbit of f_{0} under this action and let K denote the closure of Z. Since Aut(𝔛) is amenable, there is a probability measure μ on K which is invariant under the action. Since μ is invariant, ∫ f(α)dμ(f) does not depend on α ∈ \binom{𝔛}{𝔄}; let r denote the constant value.

Since the collection of all probabilities measures on K whose support is finite and contained in Z is dense, there are γ_{j} (j < m) in Aut(𝔛) and positive λ_{j} (j < m) such that for each α ∈ \binom{𝔅}{𝔄}

| ∑_{j<m} λ_{j}f_{0}(γ_{j} ∘ α) − r| ≤ 1/4.

Now define β_{j} = γ_{j} ↾ 𝔅, β = ∑_{j<m} λ_{j}β_{j} and observe that if α, α′ ∈ \left⟨{𝔅 \atop 𝔄}\right⟩

|f_{0}(β ∘ α) − f_{0}(β ∘ α′)| ≤ |f_{0}(β ∘ α) − r| + |f_{0}(β ∘ α′) − r| ≤ 1/2.

□

References

[1] J. Block and S. Weinberger. Aperiodic tilings, positive scalar curvature and amenability of spaces. J. Amer. Math. Soc., 5(4):907–918, 1992.

[2] J. W. Cannon, W. J. Floyd, and W. R. Parry. Introductory notes on Richard Thompson’s groups. Enseign. Math. (2), 42(3-4):215–256, 1996.

[3] A. Erschler. On isoperimetric profiles of finitely generated groups. Geom. Dedicata, 100:157–171, 2003.

[4] A. Erschler. Piecewise automatic groups. Duke Math. J., 134(3):591–613, 2006.

[5] E. Følner. On groups with full Banach mean value. Math. Scand., 3:243–254, 1955.

[6] R. L. Graham, K. Leeb, and B. L. Rothschild. Ramsey’s theorem for a class of categories. Advances in Math., 8:417–433, 1972.

[7] R. L. Graham and B. L. Rothschild. Ramsey’s theorem for n-parameter sets. Trans. Amer. Math. Soc., 159:257–292, 1971.

[8] M. Gromov. Entropy and isoperimetry for linear and non-linear group actions. Groups Geom. Dyn., 2(4):499–593, 2008.

[9] A. S. Kechris, V. G. Pestov, and S. Todorcevic. Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups. Geom. Funct. Anal., 15(1):106–189, 2005.

[10] J. Tatch Moore. Fast growth in Følner function for Thompson’s group F. ArXiv preprint 0905.1118, Aug. 2009.

[11] I. Namioka. Følner’s conditions for amenable semi-groups. Math. Scand., 15:18–28, 1964.

[12] J. Nešetřil. Metric spaces are Ramsey. European J. Combin., 28(1):457–468, 2007.

[13] J. Nešetřil and V. Rödl. Partitions of finite relational and set systems. J. Combinatorial Theory Ser. A, 22(3):289–312, 1977.

[14] J. Nešetřil and V. Rödl. Ramsey classes of set systems. J. Combin. Theory Ser. A, 34(2):183–201, 1983.

[15] A. Ju. Ol′šanskiĭ. On the question of the existence of an invariant mean on a group. Uspekhi Mat. Nauk, 35(4(214)):199–200, 1980.

[16] A. Yu. Ol′shanskii and Mark V. Sapir. Non-amenable finitely presented torsionby-cyclic groups. Publ. Math. Inst. Hautes Études Sci., (96):43–169 (2003), 2002.

[17] A. L. T. Paterson. Amenability, volume 29 of Mathematical Surveys and Monographs. American Mathematical Society, Providence, RI, 1988.

[18] B. Peleg. An inductive method for constructing minimal balanced collections of finite sets. Naval Res. Logist. Quart., 12:155–162, 1965.

[19] W. Rudin. Functional analysis. International Series in Pure and Applied Mathematics. McGraw-Hill Inc., New York, second edition, 1991.

[20] A. Tarski. Algebraische fassung des massproblems. Fund. Math., 31:47–66, 1938.

[21] A. Tarski. Cardinal Algebras. Oxford University Press, 1969.

[22] W. A. Veech. Topological dynamics. Bull. Amer. Math. Soc., 83(5):775–830, 1977.

[23] S. Wagon. The Banach-Tarski paradox. Cambridge University Press, Cam-

bridge, 1993.

  E-mail address: justin@math.cornell.edu

Justin Moore, 555 Malott Hall, Department of Mathematics, Cornell University, Ithaca, NY 14853-4201