We investigate two combinatorial properties of classes of finite structures, as well as related applications to topological dynamics. Using the Hrushovski property of classes of finite structures -- a finite extension property of homomorphisms -- we can show the existence of ample generics. For example, Solecki proved the existence of ample generics in the context of finite metric spaces that do indeed possess this extension property. Furthermore, Kechris, Pestov and Todorcevic have shown that the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the corresponding Fraisse limit is extremely amenable, i.e., it possesses a very strong fixed point property.
Gromov and Milman had shown that the unitary group of the infinite-dimensional separable Hilbert space is extremely amenable using non-combinatorial methods. This result encourages a deeper look into structural Euclidean Ramsey theory, i.e., Euclidean Ramsey theory in which we colour more than just points. In particular, we look at complete finite labeled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. We prove "Ramsey-type" and "Hrushovski-type" theorems for linearly ordered metric subspaces of "sufficiently" orthogonal sets. In particular, the latter is used to show a "Hrushovski version" of the Ramsey-type Matousek-Rodl theorem for simplices.
It is known that the square root of the metric induced by the distance between vertices in graphs produces a metric space embeddable in a Euclidean space if and only if the graph is a metric subgraph of the Cartesian product of three types of graphs. These three are the half-cube graphs, the so-called cocktail party graphs, and the Gosset graph. We show that the class of metric spaces related to half-cube graphs -- metric spaces on sets with the symmetric difference metric -- satisfies the Hrushovski property up to 3 points, but not more. Moreover, the amalgamation in this class can be too restrictive to permit the Ramsey Property.
Finally, following the work of Fouche, we compute the Ramsey degrees of structures induced by the leaf sets of boron trees. Also, we briefly show that this class does not satisfy the full Hrushovski property. Fouche's trees are in fact related to ultrametric spaces, as was observed by Lionel Nguyen van The. We augment Fouche's concept of orientation so that it applies to these boron tree structures. The upper bound computation of the Ramsey degree in this case, turns out to be an "asymmetric" version of the Graham-Rothschild theorem. Finally, we extend these structures to "oriented" ones, yielding a Ramsey class and a corresponding Fraisse limit whose automorphism group is extremely amenable.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/29762 |
| Date | 31 August 2011 |
| Creators | Jasinski, Jakub |
| Contributors | Todorcevic, Stevo |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0024 seconds