Journal of Combinatorics

Volume 5 (2014)

Number 2

Degree of regularity of linear homogeneous equations and inequalities

Pages: 235 – 243

DOI: https://dx.doi.org/10.4310/JOC.2014.v5.n2.a5

Authors

Kavish Gandhi (MIT-PRIMES, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Noah Golowich (MIT-PRIMES, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

László Miklós Lovász (MIT-PRIMES, Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Mass., U.S.A.)

Abstract

We define a linear homogeneous equation to be strongly $\mathrm{r}$-regular if, when a finite number of inequalities is added to the equation, the system of the equation and inequalities is still $r$-regular. In this paper, we show that if a linear homogeneous equation is $r$-regular, then it is strongly $r$-regular. In 2009, Alexeev and Tsimerman introduced a family of equations, each of which is $(n - 1)$-regular but not $n$-regular, verifying a conjecture of Rado from 1933. These equations are actually strongly $(n - 1)$-regular as an immediate corollary of our results.

Keywords

colorings, partition regularity, Ramsey theory

2010 Mathematics Subject Classification

05D10

Published 20 August 2014