University of Connecticut

Events Calendar

Connecticut Logic Seminar
Encodable by thin sets
Peter Cholak (Notre Dame)

Thursday, April 11, 2019
4:30pm – 5:45pm

Storrs Campus
Exley Science Center 121, Wesleyan University

Let $$c$$ be a coloring of $$n$$-tuples (of $$\omega$$) by finitely many colors. For $$l$$ less than the number of colors, a set $$T$$ is $$l$$-thin iff $$c$$ uses at most $$l$$ colors to color all the $$n$$-tuples from $$T$$. We say a set $$S$$ is $$RT^n_{< \infty,l}$$-encodable iff there is a coloring $$c$$ as above such that every $$l$$-thin set computes $$S$$. Wang and others showed that when $$l$$ is "big'' only the computable sets are $$RT^n_{< \infty,l}$$-encodable. Dorais, Dzhafarov, Hirst, Mileti, and Shafer showed that the hyperarithmetic sets are $$RT^n_{< \infty,l}$$-encodable for $$l<2^{n-1}$$. Cholak and Patey showed that the arithmetic sets are $$RT^n_{< \infty,l}$$-encodable for "medium'' $$l$$. In the talk we will provide exact definitions of "medium'' and "big''. What is also of interest is the role that cone avoidance plays in determining "medium'' and "big''. This is joint work with Ludovic Patey.


Reed Solomon,

Connecticut Logic Seminar (primary), UConn Master Calendar

Control Panel