Lu Liu (Central South University)

June 16, 2020 @ 3:00 pm – 4:00 pm

Title: The coding power of products of partitions
by Lu Liu (Central South University) as part of Computability theory and applications

Given two combinatorial notions P0 and P1, can we encode P0 via P1. In this talk we address the question where P0 is a 3-partition of integers and P1 is a product of finitely many 2-partitions of integers.
We firstly reduce the question to a lemma which asserts that certain Pi01 class of partitions admit two members violating a particular combinatorial constraint. Then we took a digression to see how complex does the class has to be so as to maintain the cross constraint.
On the other hand, reducing the complexity of the two members in the lemma in certain ways will answer an open question concerning a sort of Weihrauch degree of stable Ramsey’s theorem for pairs. It turns out the resulted strengthen of the lemma is a basis theorem for Pi01 class with additional constraint. We look at several such variants of basis theorem, among them some are unknown.
We end up by introducing some results and questions concerning product of infinitely many partitions.