3
$\begingroup$

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$.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

This doesn't have anything to do with partition regularity: There is such a constant $C(A)<1$ provided only that there exists at least one solution to $Ax=0$ in positive integers.

Indeed suppose $x = (x_1,\dots,x_m)$ is a solution. Then $jx = (jx_1,\dots,jx_m)$ is a solution for each $j\geq 1$. Now take a large integer $n$ much larger than $m$ and $\max x_i$ and allow $j$ to range between $1$ and $J = \lfloor n/\max x_i\rfloor $. Every element of $\{1,\dots,n\}$ appears in at most $m$ of the solutions $x,2x,\dots,Jx$, so if none of $x,2x,\dots,Jx$ is wholly contained in our set $X$ then $X$ is missing at least $J/m$ elements, so $$|X| \leq \left(1-\frac{1}{m \max x_i}\right) n + 1.$$

Improve this answer
$\endgroup$
5
  • $\begingroup$ Sean, does this argument come up often in additive combinatorics? I've used it before (to dodge sparse colour classes when proving Ramsey results) but haven't until now seen it elsewhere. $\endgroup$
    – Ben Barber
    Commented Dec 2, 2015 at 14:36
  • 1
    $\begingroup$ Probably. I think I remembered it from the proof that a set without, say, $10$-term geometric progressions must have density strictly less than $1$. $\endgroup$
    – Sean Eberhard
    Commented Dec 2, 2015 at 14:42
  • 1
    $\begingroup$ Maybe I'd say it comes up more often in measure-theoretic arguments, since outer regularity implies that an arbitrary set of positive measure has arbitrarily large density in some interval. Therefore for example every set of positive measure contains an affine translate of every finite set. $\endgroup$
    – Sean Eberhard
    Commented Dec 2, 2015 at 14:46
  • $\begingroup$ Thanks for the answer! I was wondering if this result can be strengthened to obtain a robust version of the existence of solutions, as it happens with Varnavides theorem when dealing with arithmetic progressions. $\endgroup$
    – Johnny Cage
    Commented Dec 14, 2015 at 10:17
  • $\begingroup$ Maybe a good way of formulating such a result is like this: Suppose there are $d$ linearly independent positive solutions. Then there is some $\epsilon>0$ depending on $A$ and $d$ such that as $n$ becomes large compared to everything else then whenever $X\subset\{1,\dots,n\}$ has density at least $1-\epsilon$ then there are at least $\epsilon n^d$ solutions in $X$. My guess is this is true by the same proof. $\endgroup$
    – Sean Eberhard
    Commented Dec 15, 2015 at 6:23
1
$\begingroup$

Yes, this statement is true. If you read Rado's proof (or any of the standard proofs) you can modify it to obtain a 'Ramsey multiplicity' type statement, which says that there is not just one monochromatic solution to any PR system in an $r$-colouring of $[n]$, but actually there is $\delta>0$ (depending on the system!) such that a $\delta$-fraction of all the solutions in $[n]$ are monochromatic. (Note: this is a fair bit of work.)

Now, since no integer in $[n]$ is in much more than the average number of solutions (easy to check, constant again depending on the PR system), however you remove $\ll\delta n$ integers there will remain solutions.

The constant you get from this argument is surely very far from the truth - it would be an interesting problem to try to find the optimal constant for general PR systems, but I would guess this is hard.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .