Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees
161
0
0.0
(
0
)
Authors
Natasha Dobrinen
Ask ChatGPT about the research
No Arabic abstract
Building on previous work of the author, for each finite triangle-free graph $mathbf{G}$, we determine the equivalence relation on the copies of $mathbf{G}$ inside the universal homogeneous triangle-free graph, $mathcal{H}_3$, with the smallest number of equivalence classes so that each one of the classes persists in every isomorphic subcopy of $mathcal{H}_3$. This characterizes the exact big Ramsey degrees of $mathcal{H}_3$. It follows that the triangle-free Henson graph is a big Ramsey structure.
rate research
Read More
We formulate a property strengthening the Disjoint Amalgamation Property and prove that every Fraisse structure in a finite relational language with relation symbols of arity at most two having this property has finite big Ramsey degrees which have a simple characterization. It follows that any such Fraisse structure admits a big Ramsey structure. Furthermore, we prove indivisibility for every Fraisse structure in an arbitrary finite relational language satisfying this property. This work offers a streamlined and unifying approach to Ramsey theory on some seemingly disparate classes of Fraisse structures. Novelties include a new formulation of coding trees in terms of 1-types over initial segments of the Fraisse structure, and a direct characterization of the degrees without appeal to the standard method of envelopes.
Given a countable set S of positive reals, we study finite-dimensional Ramsey-theoretic properties of the countable ultrametric Urysohn space with distances in S.
We build a collection of topological Ramsey spaces of trees giving rise to universal inverse limit structures, extending Zhengs work for the profinite graph to the setting of Fra{i}ss{e} classes of finite ordered binary relational structures with the Ramsey property. This work is based on the Halpern-L{a}uchli theorem, but different from the Milliken space of strong subtrees. Based on these topological Ramsey spaces and the work of Huber-Geschke-Kojman on inverse limits of finite ordered graphs, we prove that for each such Fra{i}ss{e} class, its universal inverse limit structures has finite big Ramsey degrees under finite Baire-measurable colourings. For finite ordered graphs, finite ordered $k$-clique free graphs ($kgeq 3$), finite ordered oriented graphs, and finite ordered tournaments, we characterize the exact big Ramsey degrees.
As a result of 33 intercontinental Zoom calls, we characterise big Ramsey degrees of the generic partial order in a similar way as Devlin characterised big Ramsey degrees of the generic linear order (the order of rationals).
Analogues of Ramseys Theorem for infinite structures such as the rationals or the Rado graph have been known for some time. In this context, one looks for optimal bounds, called degrees, for the number of colors in an isomorphic substructure rather than one color, as that is often impossible. Such theorems for Henson graphs however remained elusive, due to lack of techniques for handling forbidden cliques. Building on the authors recent result for the triangle-free Henson graph, we prove that for each $kge 4$, the $k$-clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramseys Theorem. We develop a method for coding copies of Henson graphs into a new class of trees, called strong coding trees, and prove Ramsey theorems for these trees which are applied to deduce finite big Ramsey degrees. The approach here provides a general methodology opening further study of big Ramsey degrees for ultrahomogeneous structures. The results have bearing on topological dynamics via work of Kechris, Pestov, and Todorcevic and of Zucker.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
