Skip to main content
1 of 2
Johnny Cage
  • 1.6k
  • 2
  • 12
  • 18

Partition regular systems: do they have solution in (very dense) set of integers?

A partition regular system is a linear system of equations of the form $A\cdot x=0$, which satisfies a Ramsey-type result (namely, that for each $r>0$ whenever we colour the integers in $r$ classes, there is a class which contains a monochromatic solution). The well-known Rado's theorem gives a characterization of such matrices, but we are not interested on this here.

An strong condition of this notion is density regular: a matrix $A$ is density regular if for every $\varepsilon>0$ and $Y\subset \{1,\dots,n\}$ with $|Y| \geq \varepsilon n$, then $Y$ contains a solution to the equation $A\cdot x=0$. This is the strong counterpart of Rado's theorem, and it was proven by Frankl, Rödl and Graham that $A$ is density regular iff the vector $x=(1,\dots, 1)$ is a solution of the system (namely, the columns vectors of $A$ sum 0). For instance, the matrix equation associated to $k$-APs satisfies this condition, so Szemerédi's theorem is covered by this result.

After this, it comes my question. Take the Schur equation (x+y=z), which is partition regular but NOT density regular. Easily, there are sets of linear size (for instance, take the odd numbers) which are solution-free. However, it is very easy to show that if $X\in \{1,\dots,n\}$ satisfies $|X|\geq \left({\frac{1}{2}+\varepsilon}\right) n$, then $X$ contains a Schur triple.

My question is the following: is a similar result true for general partition regular systems? In other words, is it true the following statement?: let $A$ be a partition regular system. Then there exists $C:=C(A)<1$ such that for $n$ large enough every subset $X\subset \{1,\dots, n\}$ with $|X|> C n$ contains a solution to the equation $A \cdot x=0$.

Johnny Cage
  • 1.6k
  • 2
  • 12
  • 18