Source author record

Natasha Dobrinen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO math.CO math.GN

Catalog footprint

Research overview

23works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

The Halpern--Läuchli Theorem at singular cardinals and failures of weak versions

This paper continues a line of investigation of the Halpern--Läuchli Theorem at uncountable cardinals. We prove in ZFC that the Halpern--Läuchli Theorem for one tree of height $κ$ holds whenever $κ$ is strongly inaccessible and the coloring takes less than $κ$ colors. We prove consistency of the Halpern--Läuchli Theorem for finitely many trees of height $κ$ , where $κ$ is a strong limit cardinal of countable cofinality. On the other hand, we prove failure of weak forms of Halpern--\Lauchli\ for trees of height $κ$ , whenever $κ$ is a strongly inaccessible, non-Mahlo cardinal or a singular strong limit cardinal with cofinality the successor of a regular cardinal. We also prove failure in $L$ of a weak version for all strongly inaccessible, non-weakly compact cardinals.

preprint2022arXiv

Big Ramsey degrees in universal inverse limit structures

We build a collection of topological Ramsey spaces of trees giving rise to universal inverse limit structures,extending Zheng's work for the profinite graph to the setting of Fra\"ıssé classes of finite ordered binary relational structures with the Ramsey property. This work is based on the Halpern-Lä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\"ıssé class, its universal inverse limit structure has finite big Ramsey degrees under finite Baire-measurable colorings. For such \Fraisse\ classes satisfying free amalgamation as well as finite ordered tournaments and finite partial orders with a linear extension, we characterize the exact big Ramsey degrees.

preprint2022arXiv

Fraisse Structures with SDAP+, Part I: Indivisibility

This is Part I of a two-part series regarding Ramsey properties of Fraisse structures satisfying a property called SDAP+, which strengthens the Disjoint Amalgamation Property. We prove that every Fraisse structure in a finite relational language with relation symbols of any finite arity satisfying this property is indivisible. Novelties include a new formulation of coding trees in terms of 1-types over initial segments of the Fraisse structure, and a direct proof of indivisibility which uses the method of forcing to conduct unbounded searches for finite sets. In Part II, we 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. Part II utilizes a theorem from Part I as a pigeonhole principle for induction arguments. This work offers a streamlined and unifying approach to Ramsey theory on some seemingly disparate classes of Fraisse structures.

preprint2022arXiv

Fraisse structures with SDAP+, Part II: Simply characterized big Ramsey structures

This is Part II of a two-part series regarding Ramsey properties of Fraisse structures satisfying a property called SDAP+, which strengthens the Disjoint Amalgamation Property. In Part I, we prove that every Fraisse structure in a finite relational language with relation symbols of any finite arity satisfying this property is indivisible. In Part II, we 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. Part II utilizes the notion of coding trees of 1-types developed in Part I and a theorem from Part I which functions as a pigeonhole principle for induction arguments in this paper. Our approach yields a direct characterization of the degrees without appeal to the standard method of "envelopes". This work offers a streamlined and unifying approach to Ramsey theory on some seemingly disparate classes of Fraisse structures.

preprint2022arXiv

The Ramsey Theory of Henson graphs

Analogues of Ramsey's 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 author's recent result for the triangle-free Henson graph, we prove that for each $k\ge 4$ , the $k$ -clique-free Henson graph has finite big Ramsey degrees, the appropriate analogue of Ramsey's 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.

preprint2020arXiv

Perfect Tree Forcings for Singular Cardinals

We investigate forcing properties of perfect tree forcings defined by Prikry to answer a question of Solovay in the late 1960's regarding first failures of distributivity. Given a strictly increasing sequence of regular cardinals $\langle κ_n: n< ω\rangle$ , Prikry defined the forcing $\mathbb{P}$ all perfect subtrees of $\prod_{n<ω}κ_n$ , and proved that for $κ=\sup_{n<ω}κ_n$ , assuming the necessary cardinal arithmetic, the Boolean completion $\mathbb{B}$ of $\mathbb{P}$ is $(ω,μ)$ -distributive for all $μ<κ$ but $(ω,κ,δ)$ -distributivity fails for all $δ<κ$ , implying failure of the $(ω,κ)$ -d.l. These hitherto unpublished results are included, setting the stage for the following recent results. $\mathbb{P}$ satisfies a Sacks-type property, implying that $\mathbb{B}$ is $(ω,\infty,<κ)$ -distributive. The $(\mathfrak{h},2)$ -d.l. and the $(\mathfrak{d},\infty,<κ)$ -d.l. fail in $\mathbb{B}$ . $\mathcal{P}(ω)/\mbox{Fin}$ completely embeds into $\mathbb{B}$ . Also, $\mathbb{B}$ collapses $κ^ω$ to $\mathfrak{h}$ . We further prove that if $κ$ is a limit of countably many measurable cardinals, then $\mathbb{B}$ adds a minimal degree of constructibility for new $ω$ -sequences. Some of these results generalize to cardinals $κ$ with uncountable cofinality.

preprint2020arXiv

Ramsey Theory on Infinite Structures and the Method of Strong Coding Trees

This article discusses some recent trends in Ramsey theory on infinite structures. Trees and their Ramsey theory have been vital to these investigations. The main ideas behind the author's recent method of trees with coding nodes are presented, showing how they can be useful both for coding structures with forbidden configurations as well as those with none. Using forcing as a tool for finite searches has allowed the development of Ramsey theory on such trees, leading to solutions for finite big Ramsey degrees of Henson graphs as well as infinite dimensional Ramsey theory of copies of the Rado graph. Possible future directions for applications of these methods are discussed.

preprint2020arXiv

The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees

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.

preprint2019arXiv

Forcing in Ramsey theory

Ramsey theory and forcing have a symbiotic relationship. At the RIMS Symposium on Infinite Combinatorics and Forcing Theory in 2016, the author gave three tutorials on Ramsey theory in forcing. The first two tutorials concentrated on forcings which contain dense subsets forming topological Ramsey spaces. These forcings motivated the development of new Ramsey theory, which then was applied to the generic ultrafilters to obtain the precise structure Rudin-Keisler and Tukey orders below such ultrafilters. The content of the first two tutorials has appeared in an expository article submitted to the SEALS 2016 Proceedings. The third tutorial concentrated on uses of forcing to prove Ramsey theorems for trees which are applied to determine big Ramsey degrees of homogeneous relational structures. This is the focus of this paper.

preprint2019arXiv

The Ramsey theory of the universal homogeneous triangle-free graph

The universal homogeneous triangle-free graph, constructed by Henson and denoted $\mathcal{H}_3$ , is the triangle-free analogue of the Rado graph. While the Ramsey theory of the Rado graph has been completely established, beginning with Erdős-Hajnal-Posá and culminating in work of Sauer and Laflamme-Sauer-Vuksanovic, the Ramsey theory of $\mathcal{H}_3$ had only progressed to bounds for vertex colorings (Komjáth-Rödl) and edge colorings (Sauer). This was due to a lack of broadscale techniques. We solve this problem in general: For each finite triangle-free graph $G$ , there is a finite number $T(G)$ such that for any coloring of all copies of $G$ in $\mathcal{H}_3$ into finitely many colors, there is a subgraph of $\mathcal{H}_3$ which is again universal homogeneous triangle-free in which the coloring takes no more than $T(G)$ colors. This is the first such result for a homogeneous structure omitting copies of some non-trivial finite structure. The proof entails developments of new broadscale techniques, including a flexible method for constructing trees which code $\mathcal{H}_3$ and the development of their Ramsey theory.

preprint2016arXiv

Creature forcing and topological Ramsey spaces

This article introduces a line of investigation into connections between creature forcings and topological Ramsey spaces. Three examples of sets of pure candidates for creature forcings are shown to contain dense subsets which are actually topological Ramsey spaces. A new variant of the product tree Ramsey theorem is proved in order to obtain the pigeonhole principles for two of these examples.

preprint2015arXiv

Infinite dimensional Ellentuck spaces and Ramsey-classification theorems

We extend the hierarchy of finite-dimensional Ellentuck spaces to infinite dimensions. Using uniform barriers $B$ on $ω$ as the prototype structures, we construct a class of continuum many topological Ramsey spaces $\mathcal{E}_B$ which are Ellentuck-like in nature, and form a linearly ordered hierarchy under projection. We prove new Ramsey-classification theorems for equivalence relations on fronts, and hence also on barriers, on the spaces $\mathcal{E}_B$ , extending the Pudlak-Rodl Theorem for barriers on the Ellentuck space. The inspiration for these spaces comes from continuing the iterative construction of the forcings $\mathcal{P}([\om]^k)/\Fin^{\otimes k}$ to the countable transfinite. The $σ$ -closed partial order $(\mathcal{E}_B, \sse^{\Fin^{B}})$ is forcing equivalent to $\mathcal{P}(B)/\Fin^{B}$, which forces a non-p-point ultrafilter $\mathcal{G}_B$ . The present work forms the basis for further work classifying the Rudin-Keisler and Tukey structures for the hierarchy of the generic ultrafilters $\mathcal{G}_B$ .

preprint2015arXiv

Spectra of Tukey types of ultrafilters on Boolean algebras

Extending recent investigations on the structure of Tukey types of ultrafilters on $\mathcal{P}(ω)$ to Boolean algebras in general, we classify the spectra of Tukey types of ultrafilters for several classes of Boolean algebras, including interval algebras, tree algebras, and pseudo-tree algebras.

preprint2015arXiv

Topological Ramsey spaces from Fraïssé classes, Ramsey-classification theorems, and initial structures in the Tukey types of p-points

A general method for constructing a new class of topological Ramsey spaces is presented. Members of such spaces are infinite sequences of products of Fraïssé classes of finite relational structures satisfying the Ramsey property. The Product Ramsey Theorem of Sokič is extended to equivalence relations for finite products of structures from Fraïssé classes of finite relational structures satisfying the Ramsey property and the Order-Prescribed Free Amalgamation Property. This is essential to proving Ramsey-classification theorems for equivalence relations on fronts, generalizing the Pudlák-Rödl Theorem to this class of topological Ramsey spaces. To each topological Ramsey space in this framework corresponds an associated ultrafilter satisfying some weak partition property. By using the correct Fraïssé classes, we construct topological Ramsey spaces which are dense in the partial orders of Baumgartner and Taylor in \cite{Baumgartner/Taylor78} generating p-points which are $k$ -arrow but not $k+1$ -arrow, and in a partial order of Blass in \cite{Blass73} producing a diamond shape in the Rudin-Keisler structure of p-points. Any space in our framework in which blocks are products of $n$ many structures produces ultrafilters with initial Tukey structure exactly the Boolean algebra $\mathcal{P}(n)$ . If the number of Fraïssé classes on each block grows without bound, then the Tukey types of the p-points below the space's associated ultrafilter have the structure exactly $[ω]^{<ω}$ . In contrast, the set of isomorphism types of any product of finitely many Fraïssé classes of finite relational structures satisfying the Ramsey property and the OPFAP, partially ordered by embedding, is realized as the initial Rudin-Keisler structure of some p-point generated by a space constructed from our template.

preprint2014arXiv

High dimensional Ellentuck spaces and initial chains in the Tukey structure of non-p-points

The generic ultrafilter $\mathcal{G}_2$ forced by $\mathcal{P}(ω\timesω)/($ Fin $\otimes$ Fin) was recently proved to be neither maximum nor minimum in the Tukey order of ultrafilters (in a recent paper of Blass, Dobrinen, and Raghavan), but it was left open where exactly in the Tukey order it lies. We prove that $\mathcal{G}_2$ is in fact Tukey minimal over its projected Ramsey ultrafilter. Furthermore, we prove that for each $k\ge 2$ , the collection of all nonprincipal ultrafilters Tukey reducible to the generic ultrafilter $\mathcal{G}_k$ forced by $\mathcal{P}(ω^k)/$ Fin $^{\otimes k}$ forms a chain of length $k$ . Essential to the proof is the extraction of a dense subset $\mathcal{E}_k$ from (Fin $^{\otimes k})^+$ which we prove to be a topological Ramsey space. The spaces $\mathcal{E}_k$ , $k\ge 2$ , form a hiearchy of high dimensional Ellentuck spaces. New Ramsey-classification theorems for equivalence relations on fronts on $\mathcal{E}_k$ are proved, extending the Pudlak-Rodl Theorem for fronts on the Ellentuck space, which are applied to find the Tukey structure below $\mathcal{G}_k$ .

preprint2014arXiv

Rainbow Ramsey simple structures

A relational structure $\mathrm{R}$ is {\em rainbow Ramsey} if for every finite induced substructure $\mathrm{C}$ of $\mathrm{R}$ and every colouring of the copies of $\mathrm{C}$ with countably many colours, such that each colour is used at most $k$ times for a fixed $k$ , there exists a copy $\mathrm{R}^\ast$ of $\mathrm{R}$ so that the copies of $\mathrm{C}$ in $\mathrm{R^\ast}$ use each colour at most once. We show that certain ultrahomogenous binary relational structures, for example the Rado graph, are rainbow Ramsey. Via compactness this then implies that for all finite graphs $\mathrm{B}$ and $\mathrm{C}$ and $k \in ω$ , there exists a graph $\mathrm{A}$ so that for every colouring of the copies of $\mathrm{C}$ in $\mathrm{A}$ such that each colour is used at most $k$ times, there exists a copy $\mathrm{B}^\ast$ of $\mathrm{B}$ in $\mathrm{A}$ so that the copies of $\mathrm{C}$ in $\mathrm{B^\ast}$ use each colour at most once.

preprint2014arXiv

Survey on the Tukey theory of ultrafilters

This article surveys results regarding the Tukey theory of ultrafilters on countable base sets. The driving forces for this investigation are Isbell's Problem and the question of how closely related the Rudin-Keisler and Tukey reducibilities are. We review work on the possible structures of cofinal types and conditions which guarantee that an ultrafilter is below the Tukey maximum. The known canonical forms for cofinal maps on ultrafilters are reviewed, as well as their applications to finding which structures embed into the Tukey types of ultrafilters. With the addition of some Ramsey theory, fine analyses of the structures at the bottom of the Tukey hierarchy are made.

preprint2014arXiv

Topological Ramsey spaces and metrically Baire sets

We characterize a class of topological Ramsey spaces such that each element $\mathcal R$ of the class induces a collection $\{\mathcal R_k\}_{k<ω}$ of projected spaces which have the property that every Baire set is Ramsey. Every projected space $\mathcal R_k$ is a subspace of the corresponding space of length- $k$ approximation sequences with the Tychonoff, equivalently metric, topology. This answers a question of S. Todorcevic and generalizes the results of Carlson \cite{Carlson}, Carlson-Simpson \cite{CarSim2}, Prömel-Voigt \cite{PromVoi}, and Voigt \cite{Voigt}. We also present a new family of topological Ramsey spaces contained in the aforementioned class which generalize the spaces of ascending parameter words of Carlson-Simpson \cite{CarSim2} and Prömel-Voigt \cite{PromVoi} and the spaces $\FIN_m^{[\infty]}$, $0<m<ω$ , of block sequences defined by Todorcevic \cite{Todo}.

preprint2013arXiv

The next best thing to a P-point

We study ultrafilters on $ω^2$ produced by forcing with the quotient of $\scr P(ω^2)$ by the Fubini square of the Fréchet filter on $ω$ . We show that such an ultrafilter is a weak P-point but not a P-point and that the only non-principal ultrafilters strictly below it in the Rudin-Keisler order are a single isomorphism class of selective ultrafilters. We further show that it enjoys the strongest square-bracket partition relations that are possible for a non-P-point. We show that it is not basically generated but that it shares with basically generated ultrafilters the property of not being at the top of the Tukey ordering. In fact, it is not Tukey-above $[ω_1]^{<ω}$ , and it has only continuum many ultrafilters Tukey-below it. A tool in our proofs is the analysis of similar (but not the same) properties for ultrafilters obtained as the sum, over a selective ultrafilter, of non-isomorphic selective ultrafilters.

preprint2012arXiv

A new class of Ramsey-classification theorems and their applications in the Tukey theory of ultrafilters

Motivated by Tukey classification problems and building on work in \cite{Dobrinen/Todorcevic11}, we develop a new hierarchy of topological Ramsey spaces $\mathcal{R}_α$ , $α<ω_1$ . These spaces form a natural hierarchy of complexity, $\mathcal{R}_0$ being the Ellentuck space, and for each $α<ω_1$ , $\mathcal{R}_{α+1}$ coming immediately after $\mathcal{R}_α$ in complexity. Associated with each $\mathcal{R}_α$ is an ultrafilter $\mathcal{U}_α$ , which is Ramsey for $\mathcal{R}_α$ , and in particular, is a rapid p-point satisfying certain partition properties. We prove Ramsey-classification theorems for equivalence relations on fronts on $\mathcal{R}_α$ , $2\leα<ω_1$ . These are analogous to the Pudlak-\Rodl\ Theorem canonizing equivalence relations on barriers on the Ellentuck space. We then apply our Ramsey-classification theorems to completely classify all Rudin-Keisler equivalence classes of ultrafilters which are Tukey reducible to $\mathcal{U}_α$ , for each $2\leα<ω_1$ : Every ultrafilter which is Tukey reducible to $\mathcal{U}_α$ is isomorphic to a countable iteration of Fubini products of ultrafilters from among a fixed countable collection of rapid p-points. Moreover, we show that the Tukey types of nonprincipal ultrafilters Tukey reducible to $\mathcal{U}_α$ form a descending chain of order type $α+1$ .

preprint2012arXiv

A Ramsey-Classification Theorem and its Application in the Tukey Theory of Ultrafilters

Motivated by a Tukey classification problem we develop here a new topological Ramsey space $\mathcal{R}_1$ that in its complexity comes immediately after the classical is a natural Ellentuck space \cite{MR0349393}. Associated with $\mathcal{R}_1$ is an ultrafilter $\mathcal{U}_1$ which is weakly Ramsey but not Ramsey. We prove a canonization theorem for equivalence relations on fronts on $\mathcal{R}_1$ . This is analogous to the Pudlak-\Rodl\ Theorem canonizing equivalence relations on barriers on the Ellentuck space. We then apply our canonization theorem to completely classify all Rudin-Keisler equivalence classes of ultrafilters which are Tukey reducible to $\mathcal{U}_1$ : Every ultrafilter which is Tukey reducible to $\mathcal{U}_1$ is isomorphic to a countable iteration of Fubini products of ultrafilters from among a fixed countable collection of ultrafilters. Moreover, we show that there is exactly one Tukey type of nonprincipal ultrafilters strictly below that of $\mathcal{U}_1$ , namely the Tukey type a Ramsey ultrafilter.

preprint2011arXiv

Continuous cofinal maps on ultrafilters

An ultrafilter $\mathcal{U}$ on a countable base {\em has continuous Tukey reductions} if whenever an ultrafilter $\mathcal{V}$ is Tukey reducible to $\mathcal{U}$ , then every monotone cofinal map $f:\mathcal{U}\ra\mathcal{V}$ is continuous when restricted to some cofinal subset of $\mathcal{U}$ . In the first part of the paper, we give mild conditions under which the property of having continuous Tukey reductions is inherited under Tukey reducibility. In particular, if $\mathcal{U}$ is Tukey reducible to a p-point then $\mathcal{U}$ has continuous Tukey reductions. In the second part, we show that any countable iteration of Fubini products of p-points has Tukey reductions which are continuous with respect to its topological Ramsey space of $\vec{\mathcal{U}}$ -trees.

preprint2011arXiv

Tukey types of ultrafilters

We investigate the structure of the Tukey types of ultrafilters on countable sets partially ordered by reverse inclusion. A canonization of cofinal maps from a p-point into another ultrafilter is obtained. This is used in particular to study the Tukey types of p-points and selective ultrafilters. Results fall into three main categories: comparison to a basis element for selective ultrafilters, embeddings of chains and antichains into the Tukey types, and Tukey types generated by block-basic ultrafilters on FIN.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Natasha Dobrinen

Research overview

Is this your work?

23 publications

The Halpern--Läuchli Theorem at singular cardinals and failures of weak versions

Big Ramsey degrees in universal inverse limit structures

Fraisse Structures with SDAP+, Part I: Indivisibility

Fraisse structures with SDAP+, Part II: Simply characterized big Ramsey structures

The Ramsey Theory of Henson graphs

Perfect Tree Forcings for Singular Cardinals

Ramsey Theory on Infinite Structures and the Method of Strong Coding Trees

The Ramsey theory of the universal homogeneous triangle-free graph Part II: Exact big Ramsey degrees

Forcing in Ramsey theory

The Ramsey theory of the universal homogeneous triangle-free graph

Creature forcing and topological Ramsey spaces

Infinite dimensional Ellentuck spaces and Ramsey-classification theorems

Spectra of Tukey types of ultrafilters on Boolean algebras

Topological Ramsey spaces from Fraïssé classes, Ramsey-classification theorems, and initial structures in the Tukey types of p-points

High dimensional Ellentuck spaces and initial chains in the Tukey structure of non-p-points

Rainbow Ramsey simple structures

Survey on the Tukey theory of ultrafilters

Topological Ramsey spaces and metrically Baire sets

The next best thing to a P-point

A new class of Ramsey-classification theorems and their applications in the Tukey theory of ultrafilters

A Ramsey-Classification Theorem and its Application in the Tukey Theory of Ultrafilters

Continuous cofinal maps on ultrafilters

Tukey types of ultrafilters

See the researcher in context

Building this map preview