Some applications of Ramsey's theorem to additive number theory
type: Item
instance of: scholarly article
title: Some applications of Ramsey's theorem to additive number theory
zbMATH Open document ID: 0442.10037
DOI: 10.1016/S0195-6698(80)80020-5
published in: European Journal of Combinatorics
publication date: 1980-01-01T00:00:00Z
review text: Eine (endliche oder unendliche) Folge \(A\) von natürlichen Zahlen \(a_1< a_2< \dots\) heißt \(B_r^{(k)}\)-Folge, wenn \(k\) die kleinste Zahl ist, für die sich jede Zahl \(n\) auf höchstens \(k\) verschiedene Arten als Summe von maximal \(r\) Elementen von \(A\) darstellen läßt. (\(B_2^{(1)}\)-Folgen sind die bekannten \(B_2\)-Folgen.) Verf. weist auf einige, mit \(B_r^{(k)}\)-Folgen zusammenhängende, Vermutungen hin und beweist: (1) Es gibt eine \(B_2^{(3)}\)-Folge, so daß in jeder ihrer Zerlegungen in endlich viele Teilfolgen mindestens eine \(B_2^{(3)}\)-Folge vorkommt. (2) Eine zu (1) analoge Aussage gilt, statt für \(k=3\), auch für alle \(k=2^s\) und alle \(k=\frac{1}{2}\binom{2s}{s}(s\in\mathbb N)\). (Vermutet wird die Gültigkeit für alle \(k\in\mathbb N\). Nach einem Korrekturzusatz soll diese Vermutung inzwischen von \textit{I.Nesetřil} und \textit{V.Rödl} bewiesen sein.) (3) \(H_n^{(k)}\) sei die größte unter allen Zahlen \(\ell\), für die es immer möglich ist, aus einer \(B_2^{(k)}\)-Folge mit \(n\) Elementen eine \(B_2\)-Folge mit \(\ell\) Elementen auszuwählen. Dann gilt \(H_n^{(2)}< c n^{\frac{3}{4}}\), \(H_n^{(4)}< c n^{\frac{2}{3}}\). In den Beweisen benutzt der Verf. den Satz von Ramsey, wonach in jeder Zerlegung eines vollständigen Graphen \(G\) mit \(m\) Ecken in \(\ell\) kantendisjunkte Graphen ein vollständiger Graph mit \(n\) Ecken vorkommt, falls die Zahl der Ecken von \(G\) hinreichend groß (\(m> \ell^{l(n-2)-1}\)) ist.
Mathematics Subject Classification ID: 11B83
Mathematics Subject Classification ID: 11B13
zbMATH DE Number: 3689500
zbMATH Keywords: applications of Ramsey's theorem
zbMATH Keywords: B2 sequence
reviewed by: Arnulf Mrose
MaRDI profile type: Publication
cites work: Q5520566
cites work: On extremal problems of graphs and generalized graphs
cites work: Q5850594
cites work: Linear problems in combinatorial number theory
full work available at URL: s0195-6698(80)80020-5
OpenAlex ID: W1991334388
author: P. Erdős
description: scientific article; zbMATH DE number 3689500