Some applications of Ramsey's theorem to additive number theory (Q1143432): Difference between revisions

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.