Title: The computable strength of Milliken’s Tree Theorem and applications

by Paul-Elliot Angles d’Auriac (University of Lyon) as part of Computability theory and applications

Abstract

Devlin’s theorem and the Rado graph theorem are both variants of Ramsey’s theorem, where a structure is added but more colors are allowed: Devlin’s theorem (respectively the Rado graph theorem) states if S is ℚ (respectively G, the Rado graph), then for any size of tuple n, there exists a number of colors l such that for any coloring of [S]^n into finitely many colors, there exists a subcopy of S on which the coloring takes at most l colors. Moreover, given n, the optimal l is specified.

The key combinatorial theorem used in both the proof of Devlin’s theorem and the Rado graph theorem is Milliken’s tree theorem. Milliken’s tree theorem is also a variant of Ramsey’s theorem, but this time for trees and strong subtrees: it states that given a coloring of the strong subtrees of height n of a tree T, there exists a strong subtree of height ω of T on which the coloring is constant.

In this talk, we review the links between those theorems, and present the recent results on the computable strength of Milliken’s tree theorem and its applications Devlin and the Rado graph theorem, obtained with Cholak, Dzhafarov, Monin and Patey.

Title: Towards a unifying approach to algebraic and coarse entropy

by Nicolò Zava (University of Udine) as part of Topological Groups

Lecture held in Elysium.

Abstract

In each situation, entropy associates to a self-morphism a value that estimates the chaos created by the map application. In particular, the algebraic entropy $h_{alg}$ can be computed for (continuous) endomorphisms of (topological) groups, while the coarse entropy $h_c$ is associated to bornologous self-maps of locally finite coarse spaces. Those two entropy notions can be compared because of the following observation. If $f$ is a (continuous) homomorphism of a (topological) group $G$, then $f$ becomes automatically bornologous provided that $G$ is equipped with the compact-group coarse structure. For an endomorphism $f$ of a discrete group, $h_{alg}(f)=h_c(f)$ if $f$ is surjective, while, in general, $h_{alg}(f)

eq h_c(f)$. That difference occurs because in many cases, if $f$ is not surjective, then $h_c(f)=0$.

In the first part of the talk, after briefly recalling the large-scale geometry of topological groups, we define the coarse entropy and discuss its relationship with the algebraic entropy. The second part is dedicated to the introduction of the algebraic entropy of endomorphisms of $G$-sets (i.e., sets endowed with group actions). We show that it extends the usual algebraic entropy of group endomorphisms and we provide evidence that it can represent a useful modification and generalisation of the coarse entropy that overcome the non-surjectivity issue.

Title: Topological Groups Seminar Two-Week Hiatus

by Break (University of Hawaiʻi) as part of Topological Groups

Lecture held in Elysium.

Abstract: TBA

Title: Reverse mathematics of combinatorial principles over a weak base theory

by Leszek Kołodziejczyk (University of Warsaw) as part of Computability theory and applications

Abstract

Reverse mathematics studies the strength of axioms needed to prove various

mathematical theorems. Often, the theorems have the form $forall X exists

Y psi(X,Y)$ with $X, Y$ denoting subsets of $mathbb{N}$ and $psi$

arithmetical, and the logical strength required to prove them is closely

related to the difficulty of computing $Y$ given $X$. In the early decades

of reverse mathematics, most of the theorems studied turned out to be

equivalent, over a relatively weak base theory, to one of just a few typical

axioms, which are themselves linearly ordered in terms of strength. More

recently, however, many statements from combinatorics, especially Ramsey

theory, have been shown to be pairwise inequivalent or even logically

incomparable.

The usual base theory used in reverse mathematics is $mathrm{RCA}_0$, which

is intended to correspond roughly to the idea of “computable mathematics”.

The main two axioms of $mathrm{RCA}_0$ are: comprehension for computable

properties of natural numbers and mathematical induction for c.e.

properties. A weaker theory in which induction for c.e. properties is

replaced by induction for computable properties has also been introduced,

but it has received much less attention. In the reverse mathematics

literature, this weaker theory is known as $mathrm{RCA}^*_0$.

In this talk, I will discuss some results concerning the reverse mathematics

of combinatorial principles over $mathrm{RCA}^*_0$. We will focus mostly on

Ramsey’s theorem and some of its well-known special cases: the

chain-antichain principle CAC, the ascending-descending chain principle ADS,

and the cohesiveness principle COH.

The results I will talk about are part of a larger project joint with Marta

Fiori Carones, Katarzyna Kowalik, Tin Lok Wong, and Keita Yokoyama.

Title: Non-arithmetic algebraic constructions

by Chris Conidis (CUNY-College of Staten Island) as part of Computability theory and applications

Abstract

We examine two radical constructions, one from ring theory and another from module theory, and produce a computable ring for each construction where the corresponding radical is $Pi^1_1$-complete.

Join the Hawai‘i Data Science Institute for another Data Science Friday seminar titled “Bayesian Topological Learning for Complex Data Analysis” presented by Assistant Professor of Mathematics Dr. Farzana Nasir on October 16, 2020 at 2 pm on Zoom.

Please find more information below and on the attached flyer.

**Zoom registration:** http://go.hawaii.edu/39f

**Abstract:** Persistent homology is a tool in topological data analysis for learning about the geometrical/topological structures in data by detecting different dimensional holes and summarizing their appearance disappearance scales in persistence diagrams. However, quantifying the uncertainty present in these summaries is challenging. In this talk, I will present a Bayesian framework for persistent homology by relying on the theory of point

processes. This Bayesian model provides an effective, flexible, and noise-resilient scheme to analyze and classify complex datasets. A closed form of the posterior distribution of persistence diagrams based on a family of conjugate priors will be provided. The goal is to introduce a

supervised machine learning algorithm using Bayes factors on the space of persistence diagrams. This framework is applicable to a wide variety of datasets. I will present an application to filament networks data classification of plant cells.**Bio:** Farzana Nasrin graduated from Texas Tech University with a Ph.D. in Applied Mathematics in August 2018. Her research interests span algebraic topology, differential geometry, statistics, and machine learning. Currently, she is holding an assistant professor position at UH Manoa in the Department of Mathematics. Before coming to UHM, she was working as a postdoctoral research associate funded by the ARO in mathematical data science at UTK. She has been working on building novel learning tools that rely on the shape peculiarities of data with application to biology, materials science, neuroscience, and ophthalmology. Her dissertation involves the development of analytical tools for smooth shape reconstruction from noisy data and visualization tools for utilizing information from advanced imaging devices.

Title: Effective embeddings and interpretations

by Alexandra Soskova (Sofia University) as part of Computability theory and applications

Abstract

Friedman and Stanley introduced Borel embeddings as a way of comparing classification problems for different classes of structures. Many Borel embeddings are actually Turing computable. The effective decoding is given by a uniform effective interpretation. Part of the effective interpretation is actually Medvedev reduction.

The class of undirected graphs and the class of linear orderings both lie on top under Turing computable embeddings. We give examples of graphs that are not Medvedev reducible to any linear ordering, or to the jump of any linear ordering. For any graph, there is a linear ordering, that the graph is Medvedev reducible to the second jump of the linear ordering. Friedman and Stanley gave a Turing computable embedding $L$ of directed graphs in linear orderings. We show that there do not exist $L_{omega_1omega}$-formulas that uniformly interpret the input graph $G$ in the output linear ordering $L(G)$. This is joint work with Knight, and Vatev.

We have also one positive result — we prove that the class of fields is uniformly effectively interpreted without parameters in the class of Heisenberg groups.

The second part is joint work with Alvir, Calvert, Goodman, Harizanov, Knight, Miller, Morozov, and Weisshaar.

Title: Topological Groups Seminar Two-Week Hiatus

by Break (University of Hawaiʻi) as part of Topological Groups

Lecture held in Elysium.

Abstract: TBA