Group Colorings and Bernoulli Subflows
Su Gao, Steve Jackson and Brandon Seward
Abstract
In this paper we study
the dynamics of Bernoulli flows and their subflows
over general countable groups. One of the main themes of this paper is to
establish the correspondence between the topological and the symbolic
perspectives. From the topological perspective, we are particularly interested
in free subflows (subflows
in which every point has trivial stabilizer), minimal subflows,
disjointness of subflows,
and the problem of classifying subflows up to
topological conjugacy. Our main tool to study free subflows will be the notion of hyper aperiodic points; a
point is hyper aperiodic if the closure of its orbit is a free subflow. We show that the notion of hyper aperiodicity
corresponds to a notion of k-coloring on the countable group, a key notion
we study throughout the paper. In fact, for all important topological notions
we study, corresponding notions in group combinatorics
will be established. Conversely, many variations of the notions in group combinatorics are proved to be equivalent to some
topological notions. In particular, we obtain results about the differences in
dynamical properties between pairs of points which disagree on finitely many
coordinates.
Another main theme of
the paper is to study the properties of free subflows
and minimal subflows. Again this is done through
studying the properties of the hyper aperiodic points and minimal points. We
prove that the set of all (minimal) hyper aperiodic points is always dense but
meager and null. By employing notions and ideas from descriptive set theory, we
study the complexity of the sets of hyper aperiodic points and of minimal
points, and completely determine their descriptive complexity. In doing this we
introduce a new notion of countable flecc groups and
study their properties. We also obtain the following results for the
classification problem of free subflows up to
topological conjugacy. For locally finite groups the
topological conjugacy relation for all (free) subflows is hyperfinite and nonsmooth. For nonlocally finite
groups the relation is Borel bireducible
with the universal countable Borel equivalence
relation.
The third, but not the
least important, theme of the paper is to develop constructive methods for the
notions studied. To construct k-colorings on countable groups, a
fundamental method of construction of multi-layer marker structures is
developed with great generality. This allows one to construct an abundance of kcolorings with specific properties. Variations of
the fundamental method are used in many proofs in the paper, and we expect them
to be useful more broadly in geometric group theory. As a special case of such
marker structures, we study the notion of ccc groups
and prove the ccc-ness for countable nilpotent, polycyclic, residually finite,
locally finite groups and for free products.
Table of Contents
Chapter 1. Introduction 1
1.1. Bernoulli flows and subflows 1
1.2. Basic notions 3
1.3. Existence of free subflows 4
1.4. Hyper aperiodic points and k-colorings 6
1.5. Complexity of sets and equivalence relations 9
1.6. Tilings of groups 11
1.7. The almost equality relation 13
1.8. The fundamental method 14
1.9. Brief outline 16
Chapter 2. Preliminaries 19
2.1. Bernoulli flows 19
2.2. 2-colorings 21
2.3. Orthogonality 23
2.4. Minimality 24
2.5. Strengthening and weakening of 2-colorings 27
2.6. Other variations of 2-colorings 30
2.7. Subflows of (2N)G 32
Chapter 3. Basic Constructions of 2-Colorings 35
3.1. 2-Colorings on supergroups of finite index 35
3.2. 2-Colorings on group extensions 39
3.3. 2-Colorings on Z 43
3.4. 2-Colorings on nonabelian free groups 46
3.5. 2-Colorings on solvable groups 48
3.6. 2-Colorings on residually finite groups 51
Chapter 4. Marker Structures and Tilings 53
4.1. Marker structures on groups 53
4.2. 2-Colorings on abelian and FC groups by markers 57
4.3. Some properties of ccc groups 61
4.4. Abelian, nilpotent, and polycyclic groups are ccc 63
4.5. Residually finite and locally finite groups and free products are ccc 70
Chapter 5. Blueprints and Fundamental Functions 77
5.1. Blueprints 77
5.2. Fundamental functions 84
5.3. Existence of blueprints 91
5.4. Growth of blueprints 98
Chapter 6. Basic Applications of the Fundamental Method 103
6.1. The uniform 2-coloring property 103
6.2. Density of 2-colorings 107
6.3. Characterization of the ACP 109
Chapter 7. Further Study of Fundamental Functions 117
7.1. Subflows generated by fundamental functions 117
7.2. Pre-minimality 122
7.3. Δ-minimality 127
7.4. Minimality constructions 131
7.5. Rigidity constructions for topological conjugacy 138
Chapter 8. The Descriptive Complexity of Sets of 2-Colorings 147
8.1. Smallness in measure and category 147
8.2. Σ02-hardness and Π03-completeness 148
8.3. Flecc groups 151
8.4. Nonflecc groups 156
Chapter 9. The Complexity of the Topological Conjugacy Relation 169
9.1. Introduction to countable Borel equivalence relations 169
9.2. Basic properties of topological conjugacy 170
9.3. Topological conjugacy of minimal free subflows 176
9.4. Topological conjugacy of free subflows 185
Chapter 10. Extending Partial Functions to 2-Colorings 205
10.1. A sufficient condition for extendability 205
10.2. A characterization for extendability 207
10.3. Almost equality and cofinite domains 218
10.4. Automatic extendability 229
Chapter 11. Further Questions 233
11.1. Group structures 233
11.2. 2-colorings 234
11.3. Generalizations 235
11.4. Descriptive complexity 236
Bibliography 237
Index 239