×

zbMATH — the first resource for mathematics

Some remarks on the theory of graphs. (English) Zbl 0032.19203
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 0012.27010], daß \(f(k,l) \leq {2k-2 \choose k-1}\), wird ergänzt durch \(f(k,l) > 2^{k/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.

MSC:
05C55 Generalized Ramsey theory
05C99 Graph theory
Keywords:
Topology
PDF BibTeX XML Cite
Full Text: DOI