Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 161.20603
Autor: Erdös, Pál
Title: On some applications of graph theory to geometry (In English)
Source: Can. J. Math. 19, 968-971 (1967).
Review: Es seien n verschiedene Punkte im Rk so verteilt, daß unter den {n \choose 2} Entfernungen möglichst viele gleich einer festen Zahl d sind. Diese Maximalzahl der Realisierungen von d heiße Dk(n). Es sei weiter G(n,b) ein Graph mit n Knotenpunkten und b Kanten. m(n; p) sei die größte Zahl derart, daß ein Graph G(n,m(n; p)) existiert, der keinen vollständigen Graphen mit p Knotenpunkten enthält. Es wird bewiesen, daß m(n; h)+n-h \leq D2h(n) \leq m(n; h)+n gilt für n > n0(h). Wenn n ein Vielfaches von 4h ist, gilt überdies das rechte Gleichheitszeichen. Ein expliziter Ausdruck für m(n; b) ist von P.Turán [Colloq. Math. 3, 19-30 (1954; Zbl 055.17004)] gefunden worden.
Reviewer: G.Ringel
Classif.: * 05C55 Generalized Ramsey theory
05C15 Chromatic theory of graphs and maps
60C05 Combinatorial probability
Index Words: topology
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag