Graduate Blog

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.