Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-05T12:54:03.949Z Has data issue: false hasContentIssue false

Rado partition theorem for random subsets ofintegers

Published online by Cambridge University Press:  01 May 1997

F Rödl
Affiliation:
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA. Email: [email protected]
A Ruciński
Affiliation:
Department of Discrete Mathematics, Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Matejki 48/49, 60-769 Poznań, Poland. Email: [email protected]
Get access

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

Type
Research Article
Copyright
© London Mathematical Society 1997

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)