Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 312.05123
Autor: Erdös, Paul; Hajnal, András; Pósa, L.
Title: Strong embeddings of graphs into colored graphs. (In English)
Source: Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 585-595 (1975).
Review: [For the entire collection see Zbl 293.00009.]
Die Verff. beschäftigen sich mit unendlichen Graphen G = < g,G >, wobei g die Knotenpunktmenge und G die Kantenmenge bezeichnen, und untersuchen deren Einbettungen in gefärbte Graphen. Unter eine Kantenfärbung von G mit \gamma Farben versteht man die Folge {G\nu: \nu < \gamma; \gamma > 0}, wobei die Kantenteilmenge G\nu zueinander disjunkt sind und ihre Vereinigung G ergibt. Ferner sei mit G(h) der durch die Knotenpunktmenge h \subset g aufgespannte Untergraph von G bezeichnet. Gegeben seien nun ein Graph H = < h,H > und eine eineindeutige Abbildung f von h in g mit folgenden Eigenschaften: a) Ist {x,y} in H eine Kante von H, dann folgt für die Bildkante: {f(x),f(y)} in G\nu von G\nu; b) sind dagegen x,y in h nicht durch eine Kante in H verbunden, so folgt: {f(x),f(y)} \not in G\nu. Mit anderen Worten: H sei isomorph zu einem aufgespannten Untergraphen G\nu(g') von G\nu. Dann sagt man: H kann in die \nu-te Farbe einer Kantenfärbung {G\nu: \nu < \gamma} von G eingebettet werden. Existiert darüber hinaus im Falle b) nicht nur in G\nu, sondern auch in G keine Kante {f(x),f(y)}, d.h. gilt G\nu(g') = G(g'), so spricht man von einer starken Einbettung. Mit der starken Einbettung beschäftigen sich die Verff. in vorliegender Arbeit und benutzen dazu die beiden folgenden Zerlegungsrelationen, die von P. Erdös und A. Hajnal [Acta Math. Acad. Sci. Hung. 18, 359-377 (1967; Zbl 169.26601)] und C. W. Henson [Can. J. Math. 25, 603-610 (1973; Zbl 274.05114)] eingeführt wurden: G,H\nu: \nu < \gamma seien Graphen. Dann sagt man, daß die Relationen G ––> (H\nu)\nu < \gamma, G\mapsto (H\nu)\nu < \gamma gelten, wenn es für jede Kantenfärbung {G\nu: \nu < \gamma } von G mit \gamma Farben ein \nu < \gamma derart gibt, daß H\nu in die \nu-te Farbe eingebettet bzw. stark eingebettet werden kann. Stimmen alle H\nu mit H überein, so schreibt man anstelle von (H\nu)\nu < \gamma auch (H)\gamma.
Zum Beweis der folgenden Resultate (3 Sätze) verwenden die Verff. Ergebnisse und Methoden der transfiniten Mengenlehre, und es macht sich dabei die Einführung weiterer Begriffe notwendig. Satz 1: Sei H = < h,H > der unendliche vollständige paare Graph, d.h. h = h0 \cup h1, h0 \cap h1 = Ø, |h0| = |h1| = \omega, H = [h0,h1]. Dann gilt G (not)––> (H)2 für alle abzählbaren Graphen G. Der Beweis erfolgt indirekt, und es ist notwendig, einen geeigneten Repräsentanten eines sog. \omega-guten Graphen (``\omega-good graph'') der infiniten Kardinalität \omega einzufhren.
Bezeichnet man einen Graphen G als lokal-endlich, wenn jeder Knotenpunkt von G eine endliche Valenz entweder in G oder im Komplement \barG von G besitzt, so lautet das zweite Ergebnis: Satz 2: Seien H lokal-endlich und H, K abzählbar. Dann existiert ein abzählbarer Graph G derart, daß G \mapsto (H,K) gilt. Der Beweis dieses Satzes vom Ramsey-Typ ist relativ lang und nicht ganz einfach. Von Bedeutung ist dabei die Zuordnung eines ``\kappa-vollständigen eigentlichen Ideals'' I_G = I (\kappa ist eine transfinite Kardinalzahl) zu einem Graphen G.
Im Bemühen, eine Verallgemeinerung für größere Graphen zu finden, beweisen die Verff. den Satz 3: Gegeben sei eine endliche Folge < Hi: i < k > von abzählbaren Graphen. Dann existiert ein Graph G mit |G| \leq 2\omega derart, daß G \mapsto (Hi)i < k gilt. Der Beweis wird mit ähnlichen Methoden wie der zu Satz 2 geführt, wobei wiederum das vollständige Ideal I verwendet wird. Erstaunlicherweise ist nicht bekannt, ob sich Satz 3 auf Graphen größerer Kardinalität ausdehnen läßt.
Die Verff. formulieren in diesem Zusammenhang das einfachste ungelöste Problem: Ist es wahr, daß es für alle Graphen H, K der Kardinalität \omega1 einen Graphen G (von angemessener Größe) derart gibt, daß G \mapsto (H,K) gilt?
Reviewer: H.-J.Presia
Classif.: * 05C99 Graph theory
05C15 Chromatic theory of graphs and maps
05C10 Topological graph theory
04A20 Combinatorial set theory
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag