On Schur Properties of Random Subsets of Integers
1996; Elsevier BV; Volume: 61; Issue: 2 Linguagem: Inglês
10.1006/jnth.1996.0155
ISSN1096-1658
AutoresRonald Graham, Vojtěch Rödl, Andrzej Ruciński,
Tópico(s)Advanced Graph Theory Research
ResumoA classic result of I. Schur [9] asserts that for everyr⩾2 and fornsufficiently large, if the set [n]={1, 2, …, n} is partitioned intorclasses, then at least one of the classes contains a solution to the equationx+y=z. Any such solution withx≠ywill be called aSchur triple. Let us say thatA⊆[n] has theSchur propertyif for every partition (or 2-coloring) ofA=R∪B(forredandblue), there must always be formed somemonochromaticSchur triple, i.e., belonging entirely to eitherRorB. Our goal here is to show thatn1/2is a threshold for the Schur property in the following sense: for anyω=ω(n)→∞, almost all setsA⊆[n] with |A| ωn1/2do.
Referência(s)