Rado Partition Theorem for Random Subsets of Integers

For an l × k matrix A = ( a ij ) of integers, denote by L ( A ) the system of homogenous linear equations a i 1 x 1 + … + a ik x k = 0, 1 ⩽ i ⩽ l . We say that A is density regular if every subset of N with positive density, contains a solution to L ( A ). For a density regular l × k matrix A , an integer r and a set of integers F , we write F → ( A ) rif for any partition F = F 1 ∪ … ∪ F r there exists i ∈ {1, 2, …, r } and a column vector x such that A x = 0 and all entries of 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 α = α( A ) such that lim n → ∞ P ([ n ] N → ( A ) r )=0 if N = O( n α ) and 1 if N = Ω( n α ). 1991 Mathematics Subject Classification : 05D10, 11B25, 60C05