Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 032.19203
Autor: Erdös, Pál
Title: Some remarks on the theory of graphs. (In English)
Source: Bull. Am. Math. Soc. 53, 292-294 (1947).
Review: Zwei Graphen G und G' sind komplementär, wenn sie alle Eckpunkte, aber keine Kante gemeinsam haben und je zwei Eckpunkte entweder in G oder in G' durch eine Kante verbunden sind. Es werden im Anschluß an Bemerkungen zu einem Satz von Ramsey Fragen folgender Art behandelt: Welches ist die Mindestzahl f(k,l) der Ecken eines Graphen G, damit entweder G einen vollständigen Teilgraphen k-ter Ordnung oder G' einen vollständigen Teilgraphen l-ter Ordnung enthalten muß? Ein früheres Ergebnis des Verf. und Szekeres [Compositio Math., Groningen 2, 463-470 (1935; Zbl 012.27010], daß f(k,l) \leq {2k-2 \choose k-1}, wird ergänzt durch f(k,l) > 2k/2. Daraus folgt: Wenn bei gegebener Eckenzahl n A(n) die größte Zahl der Eigenschaft ist, daß G oder G' einen vollständigen Teilgraphen A(n)-ter Ordnung enthalten muß, so gilt: {log n \over 2 log 2} < A(n) < {2 log n \over log 2}. Wenn G orientiert ist und n \geq (k-1)(l-1)+1, dann enthält G' einen vollständigen Teilgraph k-ter Ordnung oder G eine l Eckpunkte verbindende Bahn; auf Zahlensysteme angewendet: Ein System von (k-1)(l-1)+1 verschiedenen ganzen Zahlen enthält entweder ein Teilsystem von k Zahlen, von denen keine ein Vielfaches der anderen ist, oder eine Folgen von l Zahlen, in der jede ein Vielfaches der vorangehenden ist.
Reviewer: Künneth (Erlangen)
Classif.: * 05C55 Generalized Ramsey theory
05C99 Graph theory
Index Words: Topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag