Cross-constraint basis theorems and products of partitions
Abstract
We survey and extend a new technique from Lu Liu to prove separation theorems between products of Ramsey-type theorems over computable reducibility. We use this technique to show that Ramsey’s theorem for n -tuples and three colors is not computably reducible to finite products of Ramsey’s theorem for n -tuples and two colors, and prove multiple basis and anti-basis theorems for the so-called cross-constraint problem.
Fields of Study & Subjects
Constraint Satisfaction and Optimization
Digital Image Processing Techniques
Mathematics and Applications
Publication details
- Journal / source
- Computability
- Publisher
- SAGE Publications
- Volume
- 15
- Issue
- 1-2
- Pages
- 60–84
- Publication date
- 1 May 2026
- Language
- EN