Premium
Rado Partition Theorem for Random Subsets of Integers
Author(s) -
Rödl F,
Ruciński A
Publication year - 1997
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/s0024611597000178
Subject(s) - mathematics , combinatorics , partition (number theory) , integer (computer science) , discrete mathematics , matrix (chemical analysis) , mathematics subject classification , materials science , computer science , composite material , programming language
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