ترغب بنشر مسار تعليمي؟ اضغط هنا

An inside/outside Ramsey theorem and recursion theory

108   0   0.0 ( 0 )
 نشر من قبل Paul Shafer
 تاريخ النشر 2020
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

Inspired by Ramseys theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph $G$ contains an infinite subset $H$ such that every vertex of $G$ is adjacent to precisely none, one, or infinitely many vertices of $H$. We analyze the Rival-Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival-Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramseys theorem for pairs. We also identify a weak form of the Rival-Sands theorem that is equivalent to Ramseys theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival-Sands theorems computational strength. We find that the Rival-Sands theorem is Weihrauch equivalent to the double jump of weak K{o}nigs lemma. We believe that the Rival-Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival-Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramseys theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival-Sands theorem is weaker than that of Ramseys theorem for pairs by showing that a number of well-known consequences of Ramseys theorem for pairs do not Weihrauch reduce to the weak Rival-Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle.



قيم البحث

اقرأ أيضاً

We define a collection of topological Ramsey spaces consisting of equivalence relations on $omega$ with the property that the minimal representatives of the equivalence classes alternate according to a fixed partition of $omega$. To prove the associa ted pigeonhole principles, we make use of the left-variable Hales-Jewett theorem and its extension to an infinite alphabet. We also show how to transfer the corresponding infinite-dimensional Ramsey results to equivalence relations on countable limit ordinals (up to a necessary restriction on the set of minimal representatives of the equivalence classes) in order to obtain a dual Ramsey theorem for such ordinals.
We investigate interactions between Ramsey theory, topological dynamics, and model theory. We introduce various Ramsey-like properties for first order theories and characterize them in terms of the appropriate dynamical properties of the theories in question (such as [extreme] amenability of a theory or some properties of the associated Ellis semigroups). Then we relate them to profiniteness and triviality of the Ellis groups of first order theories. In particular, we find various criteria for [pro]finiteness and for triviality of the Ellis group of a given theory from which we obtain wide classes of examples of theories with [pro]finite or trivial Ellis groups. As an initial motivation, we note that profiniteness of the Ellis group of a theory implies that the Kim-Pillay Galois group of this theory is also profinite, which in turn is equivalent to the equality of the Shelah and Kim-Pillay strong types. We also find several concrete examples illustrating the lack of implications between some fundamental properties. In the appendix, we give a full computation of the Ellis group of the theory of the random hypergraph with one binary and one 4-ary relation. This example shows that the assumption of NIP in the version of Newelskis conjecture for amenable theories (proved in [16]) cannot be dropped.
We prove an infinite Ramsey theorem for noncommutative graphs realized as unital self-adjoint subspaces of linear operators acting on an infinite dimensional Hilbert space. Specifically, we prove that if V is such a subspace, then provided there is n o obvious obstruction, there is an infinite rank projection P with the property that the compression PVP is either maximal or minimal in a certain natural sense.
356 - Nadav Samet , Boaz Tsaban 2011
Superfilters are generalized ultrafilters, which capture the underlying concept in Ramsey theoretic theorems such as van der Waerdens Theorem. We establish several properties of superfilters, which generalize both Ramseys Theorem and its variant for ultrafilters on the natural numbers. We use them to confirm a conjecture of Kov{c}inac and Di Maio, which is a generalization of a Ramsey theoretic result of Scheepers, concerning selections from open covers. Following Bergelson and Hindmans 1989 Theorem, we present a new simultaneous generalization of the theorems of Ramsey, van der Waerden, Schur, Folkman-Rado-Sanders, Rado, and others, where the colored sets can be much smaller than the full set of natural numbers.
250 - L. Nguyen Van The 2009
In 2003, Kechris, Pestov and Todorcevic showed that the structure of certain separable metric spaces - called ultrahomogeneous - is closely related to the combinatorial behavior of the class of their finite metric spaces. The purpose of the present p aper is to explore the different aspects of this connection.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا