Suppose $G$ is a finitely generated discrete group and that there is a subset $E$ of $G$ such that if
$\mu$ is a finitely additive probability measure on $G$, then there is a
$g$ in $G$ such that $\mu(E \cdot g) \ne \mu(E)$.
Certainly $G$ is non amenable.
Can more be said about $G$?
Must $G$ contain $\mathbb{F}\_2$?


It should be noted that the above situation can happen:
let $E$ be all elements of $\mathbb{F}\_2$ which ``begin'' with $a$ or $a^{-1}$.
Then both $E$ and its complement have infinitely many disjoint translates (by powers of $b$ and $a$, respectively).



When is non amenablity witnessed by a single non measurable set?
The answer is that the above is equivalent to non amenability.
Fix a group $(G,\*)$.
Since $(G,\*)$ is non amenable if and only if every finitely generated subgroup is non amenable,
we may assume that $G$ is finitely generated.


If $\mu$ and $\nu$ are finitely supported probability measures on $G$,
define
$$
\mu \* \nu (Z) = \sum\_{x \* y \in Z} \mu (\{x\}) \nu (\{y\})
$$
Observe that $g \* \nu (E) = \nu ( g^{-1} \* E)$.
If $S$ is a subset of $S$, let $P(S)$ denote all probability measures on $S$
(which are identified with probability measures on $G$ which are supported on $S$).
I will identify $G$ with the point masses in $P(G)$.


If $A$ and $B$ are subsets of $G$ and $A$ is finite, we say that
$B$ is $\epsilon$-Ramsey with respect to $A$ if for every $E \subseteq B$,
then there is a $\nu$ in $P(B)$ such that $P(A) \* \nu \subseteq P(B)$ and
$$
|\mu \* \nu (E) - \nu (E)| < \epsilon
$$
for all $\mu$ in $P(A)$.
Notice that in some sense $E$ is defining a partition of $P(B)$ and we are
postulating the existence of a copy of $P(A)$ in $P(B)$ which is homogeneous for $E$ up to
an error of $\epsilon$.


It can be shown with an argument similar to the one below that if $B$ is $\epsilon$-Ramsey with respect to $A$, then for every $f:B \to [0,1]$
there is a $\nu$ in $P(B)$ such that
$$
|f(\mu \* \nu) - f(\nu)| < \epsilon
$$
where $f$ has been extended linearly to $P(B)$.


We say that $(G,\*)$ is Ramsey if for every finite subset $A \subseteq G$ and every $\epsilon > 0$,
there is a finite subset $B$ of $G$ with is $\epsilon$-Ramsey with respect to $A$.
Notice that if $B$ satisfies that for every $E \subseteq B$ there is a $\nu$ in $P(B)$ such that
$$
|g \* \nu (E) - \nu (E)| < \epsilon
$$
for all $g$ in $A$, then $B$ is contained in a finite set which is $\epsilon$-Ramsey
(we need only to replace $B$ by $A \* B \cup B$).


To connect this to the question, suppose that $G$ is not Ramsey, as witnessed by a finite
$A \subseteq G$ and $\epsilon > 0$.
I claim there is a set $E \subseteq G$ such that for every $\mu \in P(G)$, there is a $g \in A$
such that $|\mu(E \cdot g) - \mu (E)| \geq \epsilon/2$.
Let $B\_n$ $(n < \infty)$ be an increasing sequence of finite sets covering $G$.
Let $T\_n$ be the set of all subsets $E$ of $B\_n$ which witness that
$B\_n$ is not $\epsilon$-Ramsey with respect to $A$.
Observe that if $E$ is in $T\_{n+1}$, then $E \cap B\_n$ is in $T\_n$.
Otherwise there would be a $\nu$ in $P(B\_n)$ such that $g \* \nu$ is in $P(B\_n)$ for each 
$g$ in $A$ and
$$
|g \* \nu (E \cap B\_n) - \nu (E \cap B\_n)| < \epsilon
$$
Such a $\nu$ would also witness that $E$ is not in $T\_{n+1}$.
Define $T = \bigcup\_n T\_n$ and order $E \leq\_T E'$ if $E = E' \cap B\_m$ where $E$ is in $T\_n$.
This order makes $T$ into an infinite finitely branching tree.
By König's lemma, $T$ has an infinite path whose union is
some $E \subseteq G$.
If there were a measure $\mu$ which was $\epsilon/2$-invariant for $E$ with respect to translates by elements of $A$,
there would be a finitely supported $\nu$ which was $\epsilon$-invariant for $E$ with respect to translates
in $A$.
But this would be a contradiction since then the support of $\nu$ would be contained in some $B\_n$
and $\nu$ would witness that $E \cap B\_n$ was not in $T$.


Now the claim is that the Ramsey property of a discrete group is equivalent to its amenability.
That amenability implies the Ramsey property follows from Følner's characterization of amenability.
Also observe that $G$ is amenable provided that for every $\epsilon > 0$, every
finite list $E\_i$ $(i < n)$ of subsets of $G$, and
$g\_i$ $(i < n)$ in $G$, there is a finitely supported $\mu$ such that
$$
|\mu (g\_i \* E\_i) - \mu (E\_i) | < \epsilon.
$$
Set $B\_{-1} = \{1\_G\} \cup \{g^{-1}\_i :i < n\}$ and construct a sequence
$B\_i$ $(i < n)$ such that $B\_{i+1}$ is $\epsilon/2$-Ramsey with respect to $B\_i$.


Now inductively construct $\nu\_i$ $(i < n)$ by downward recursion on $i$.
If $\nu\_j$ $(i < j)$ has been constructed, let $\nu\_i \in P(B\_i)$ be such that
$$
|\mu \* \nu\_{i} \* \ldots \* \nu\_{n-1} (E\_i) - \nu\_i \* \ldots \* \nu\_{n-1} (E\_i)| < \epsilon/2
$$
for all $\mu$ in $P(B\_{i-1})$.
Set $\mu = \nu\_0 \* \ldots \* \nu\_{n-1}$.
If $i < n$, then since $\nu\_0 \* \ldots \* \nu\_{i-1}$ and
$g\_i^{-1} \* \nu\_0 \* \ldots \* \nu\_{i-1}$ are in $P(B\_{i-1})$,
$$
|g\_i^{-1} \* \mu (E\_i) - \nu\_i \* \ldots \* \nu\_{n-1} (E\_i)| < \epsilon/2
$$
$$
|\mu (E\_i) - \nu\_i \* \ldots \* \nu\_{n-1} (E\_i)| < \epsilon/2
$$
and therefore
$|\mu (g\_i \* E\_i) - \mu (E\_i)| < \epsilon$.


