Rado partition theorem for random subsets ofintegers

Abstract

For an $l\times k$ matrix $A=(a_{ij})$ of integers, denote by $\mathcal L(A)$ the system of homogenous linear equations $a_{i1}x_1+\ldots+a_{ik}x_k=0$, $1\le i\le l$. We say that $A$ is {\it density regular} if every subset of $\bold N$ with positive density, contains a solution to $\mathcal L(A)$. For a density regular $l\times k$ matrix $A$, an integer $r$ and a set of integers $F$, we write $$F\to(A)_r$$ if for any partition $F=F_1\cup....\cup F_r$ there exists $i\in\{1,2,...,r\}$ and a column vector $\bold x$ such that $A\bold x=\bold 0$ and all entries of $\bold x$ belong to $F_i$. Let $[n]_N$ be a random $N$-element subset of $\{1,2,...,n\}$ chosen uniformly from among all such subsets. In this paper we determine for every density regular matrix $A$ a parameter $\alpha=\alpha(A)$ such that $\lim_{n\to\infty}\bold P([n]_N\to(A)_r)=0$ if $N=O(n^{\alpha})$ and 1 if $N=\Omega(n^{\alpha})$.

1991 Mathematics Subject Classification: 05D10, 11B25, 60C05