Oct

26

Wednesday, November 10, 2010, 9:00 - 9:50 a.m., in BA 6183, 40 St. George Street PhD Candidate: Jakub Jasinski PhD Advisor: Stevo Todorcevic Thesis Title: Hrushovski and Ramsey Properties of Classes of Finite Inner Product Structures, Finite Euclidean Metric Spaces, and Boron Trees (http://www.math.toronto.edu/jasinski/thesis.pdf) Thesis Abstract: We look at 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, the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the Fraisse limit of this class 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 labelled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. This leads to a Ramsey result for linearly ordered metric subspaces of sufficiently orthogonal sets. We also construct Ramsey and Hrushovski classes of metric spaces corresponding to spreads used by Matousek and Rodl in their paper on colouring points in spheres. The square root of the metric induced by the distance between vertexes 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 which correspond 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 lower 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. REFERENCES: Deza, M.; Laurent, M. Geometry of Cuts and Metrics, Springer (1996). Fouche, W. L. Symmetries and Ramsey properties of trees, Discrete Mathematics 197/198 (1999) 325--330. Fraisse, R. Theory of Relations, Elsevier, (2000) Rev. ed. Gromov, M.; Milman V.D. A topological application of the isoperimetric inequality, Amer. J. Math. 105 (1983), 843--854. Hrushovski, E. Extending partial isomorphisms of graphs, (English summary) Combinatorica 12 (1992), no. 4, 411--416. Herwig B.; Lascar, D. Extending partial automorphisms and the profinite topology on free groups, Trans. Amer. Math. Soc. 352 (1999), 19852021. Kechris, A. S.; Pestov, V. G.; Todorcevic, S. Fraisse limits, Ramsey theory, and topological dynamics of automorphism groups, Geom. Funct. Anal. 15 (2005), no. 1, 106--189. Kechris, A.; Rosendal, C. Turbulence, Amalgamation, and Generic automorphisms of Homogeneous Structures, Proc. Lond. Math. Soc. (3) 94 (2007), no. 2, 302--350. Matousek, J.; Rodl, V. On Ramsey sets in spheres, Journal of Combinatorial Theory, Series A Volume 70, Issue 1, (April, 1995), Pages 30-44. Nesetril, J. Ramsey Theory, Handbook of Combinatorics (R. Graham, et al., eds.), Elsevier (1995), 1331--1403 (1363). Nguyen Van The, L. Ramsey degrees of finite ultrametric spaces, ultrametric Urysohn spaces and dynamics of their isometry groups, European J. Combin. 30 (2009), no. 4, 934--945. Solecki, S. Extending partial isometries, Israel J. Math. 150 (2005), 315--332.Everyone welcome. Coffee will be served in the Math Lounge before the exam.

## no comment as of now