An official website of the United States government
Milliken’s tree theorem is a deep result in combinatorics that generalizes a vast number of other results in the subject, most notably Ramsey’s theorem and its many variants and consequences. In this sense, Milliken’s tree theorem is paradigmatic of structural Ramsey theory, which seeks to identify the common combinatorial and logical features of partition results in general. Its investigation in this area has consequently been extensive. Motivated by a question of Dobrinen, we initiate the study of Milliken’s tree theorem from the point of view of computability theory. The goal is to understand how close it is to being algorithmically solvable, and how computationally complex are the constructions needed to prove it. This kind of examination enjoys a long and rich history, and continues to be a highly active endeavor. Applied to combinatorial principles, particularly Ramsey’s theorem, it constitutes one of the most fruitful research programs in computability theory as a whole. The challenge to studying Milliken’s tree theorem using this framework is its unusually intricate proof, and more specifically, the proof of the Halpern-Laüchli theorem, which is a key ingredient. Our advance here stems from a careful analysis of the Halpern-Laüchli theorem which shows that it can be carried out effectively (i.e., that it is computably true). We use this as the basis of a new inductive proof of Milliken’s tree theorem that permits us to gauge its effectivity in turn. The key combinatorial tool we develop for the inductive step is a fast-growing computable function that can be used to obtain a finitary, or localized, version of Milliken’s tree theorem. This enables us to build solutions to the full Milliken’s tree theorem using effective forcing. The principal result of this is a full classification of the computable content of Milliken’s tree theorem in terms of the jump hierarchy, stratified by the size of instance. As usual, this also translates into the parlance of reverse mathematics, yielding a complete understanding of the fragment of second-order arithmetic required to prove Milliken’s tree theorem. We apply our analysis also to several well-known applications of Milliken’s tree theorem, namely Devlin’s theorem, a partition theorem for Rado graphs, and a generalized version of the so-called tree theorem of Chubb, Hirst, and McNicholl. These are all certain kinds of extensions of Ramsey’s theorem for different structures, namely the rational numbers, the Rado graph, and perfect binary trees, respectively. We obtain a number of new results about how these principles relate to Milliken’s tree theorem and to each other, in terms of both their computability-theoretic and combinatorial aspects. In particular, we establish new structural Ramsey-theoretic properties of the Rado graph theorem and the generalized Chubb-Hirst-McNicholl tree theorem using Zucker’s notion of big Ramsey structure.
more »
« less
Richter’s local limit theorem, its refinement, and related results*
We give a detailed exposition of the proof of Richter’s local limit theorem in a refined form and establish the stability of the remainder term in this theorem under small perturbations of the underlying distribution (including smoothing).We also discuss related quantitative bounds for characteristic functions and Laplace transforms.
more »
« less
- Award ID(s):
- 2154001
- PAR ID:
- 10495215
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Lithuanian Mathematical Journal
- Volume:
- 63
- Issue:
- 2
- ISSN:
- 0363-1672
- Page Range / eLocation ID:
- 138 to 160
- Subject(s) / Keyword(s):
- MSC: 60E, 60F Keywords: central limit theorem, local limit theorem, characteristic functions
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In this paper, we generalize the original idea of Thurston for the so-called Mather-Thurston’s theorem for foliated bundles to prove new variants of this theorem for PL homeomorphisms and contactormorphisms. These versions answer questions posed by Gelfand-Fuks ([GF73, Section 5]) and Greenberg ([Gre92]) on PL foliations and Rybicki ([Ryb10, Section 11]) on contactomorphisms. The interesting point about the original Thurston’s technique compared to the better-known Segal-McDuff’s proof of the Mather-Thurston theorem is that it gives acompactly supportedc-principle theorem without knowing the relevant local statement on open balls. In the appendix, we show that Thurston’s fragmentation implies the non-abelian Poincare duality theorem and its generalization using blob complexes ([MW12, Theorem 7.3.1]). To the memory of John Mather.more » « less
-
Abstract We introduce a notion of curvature on finite, combinatorial graphs. It can be easily computed by solving a linear system of equations. We show that graphs with curvature bounded below by have diameter bounded by (a Bonnet–Myers theorem), that implies that has constant curvature (a Cheng theorem) and that there is a spectral gap (a Lichnerowicz theorem). It is computed for several families of graphs and often coincides with Ollivier curvature or Lin–Lu–Yau curvature. The von Neumann Minimax theorem features prominently in the proofs.more » « less
-
In Kenneth Arrow's last week of life at age 95, he reported that I began my research career with an impossibility theorem. If I had time now, my last theorem would be an impossibility theorem about social choice for environmental policy. This paper completes the formalization, proof, and discussion of the theorem that Arrow then described.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s10986-023-09598-9
