Logic Colloquium 2024


Gabriela Laboska

University of Chicago

Talks at this conference:

  Friday, 16:55, J336

Some computability-theoretic aspects of partition regularity over rings

A system of linear equations over a ring \(R\) is partition regular if for any finite coloring of \(R\), the system has a monochromatic solution. In 1933, Rado [3] showed that an inhomogeneous system is partition regular over \(\mathbb{Z}\) if and only if it has a constant solution. Following a similar approach, Byszewski and Krawczyk [1] showed that the result holds over any integral domain. In 2018, following a different approach, Leader and Russell [2] generalized this over any commutative ring \(R\). We analyze some of these combinatorial results from a computability-theoretic point of view, starting with a theorem by Straus [4] used in the work of [1] and [2] that generalizes an earlier result by Rado.


  1. Byszewski, B., Krawczyk, E.,Rado’s theorem for rings and modules,Journal of Combinatorial Theory Series A,vol. 180 (2021), no. 105402, pp. 28.
  2. Leader, I., Russell, P. A.,Inhomogeneous partition regularity,Electronic Journal of Combinatorics,vol. 27 (2020), no. 2, pp. 4.
  3. Rado, R.,Studien zur kombinatorik,Mathematische Zeitschrift,vol. 36 (1933), no. 1, pp. 424–470.
  4. Straus, E. G.,A combinatorial theorem in group theory,Mathematics of Computation,vol. 29 (1975), pp. 303-309.