×

Strong embeddings of graphs into colored graphs. (English) Zbl 0312.05123

Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 585-595 (1975).
[For the entire collection see Zbl 0293.00009.]
Die Verff. beschäftigen sich mit unendlichen Graphen \({\mathfrak G}= \langle g,G \rangle\), wobei \(g\) die Knotenpunktmenge und \(G\) die Kantenmenge bezeichnen, und untersuchen deren Einbettungen in gefärbte Graphen. Unter eine Kantenfärbung von \({\mathfrak 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 \({\mathfrak G}(h)\) der durch die Knotenpunktmenge \(h \subset g\) aufgespannte Untergraph von \({\mathfrak G}\) bezeichnet. Gegeben seien nun ein Graph \({\mathfrak H}= \langle h,H \rangle\) und eine eineindeutige Abbildung \(f\) von \(h\) in \(g\) mit folgenden Eigenschaften: a) Ist \(\{x,y\} \in H\) eine Kante von \({\mathfrak H}\), dann folgt für die Bildkante: \(\{f(x),f(y)\} \in G_\nu\) von \({\mathfrak G}_\nu\); b) sind dagegen \(x,y \in h\) nicht durch eine Kante in \({\mathfrak H}\) verbunden, so folgt: \(\{f(x),f(y)\} \not\in G_\nu\). Mit anderen Worten: \({\mathfrak H}\) sei isomorph zu einem aufgespannten Untergraphen \({\mathfrak G}_\nu(g')\) von \({\mathfrak G}_\nu\). Dann sagt man: \({\mathfrak 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 \({\mathfrak G}_\nu\), sondern auch in \({\mathfrak G}\) keine Kante \(\{f(x),f(y)\}\), d.h. gilt \({\mathfrak G}_\nu(g')={\mathfrak 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 0169.26601)] und C. W. Henson [Can. J. Math. 25, 603-610 (1973; Zbl 0274.05114)] eingeführt wurden: \({\mathfrak G},{\mathfrak H}_\nu: \nu < \gamma\) seien Graphen. Dann sagt man, daß die Relationen \({\mathfrak G} \to ({\mathfrak H}_\nu)_{\nu< \gamma}\), \({\mathfrak G}\mapsto ({\mathfrak H}_\nu)_{\nu < \gamma}\) gelten, wenn es für jede Kantenfärbung \(\{G_\nu: \nu < \gamma \}\) von \({\mathfrak G}\) mit \(\gamma\) Farben ein \(\nu < \gamma\) derart gibt, daß \({\mathfrak H}_\nu\) in die \(\nu\)-te Farbe eingebettet bzw. stark eingebettet werden kann. Stimmen alle \({\mathfrak H}_\nu\) mit \({\mathfrak H}\) überein, so schreibt man anstelle von \(({\mathfrak H}_\nu)_{\nu < \gamma}\) auch \(({\mathfrak 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 \({\mathfrak H} = \langle h,H \rangle\) der unendliche vollständige paare Graph, d.h. \(h = h_0 \cup h_1\), \(h_0 \cap h_1 = \emptyset\), \(|h_0| = |h_1| = \omega\), \(H=[h_0,h_1]\). Dann gilt \({\mathfrak G} \nrightarrow ({\mathfrak H})_2\) für alle abzählbaren Graphen \({\mathfrak 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\) einzufḧren.
Bezeichnet man einen Graphen \({\mathfrak G}\) als lokal-endlich, wenn jeder Knotenpunkt von \({\mathfrak G}\) eine endliche Valenz entweder in \({\mathfrak G}\) oder im Komplement \(\bar{\mathfrak G}\) von \({\mathfrak G}\) besitzt, so lautet das zweite Ergebnis: Satz 2: Seien \({\mathfrak H}\) lokal-endlich und \({\mathfrak H}\), \({\mathfrak K}\) abzählbar. Dann existiert ein abzählbarer Graph \({\mathfrak G}\) derart, daß \({\mathfrak G} \mapsto ({\mathfrak H},{\mathfrak 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_{\mathfrak G}=I\) (\(\kappa\) ist eine transfinite Kardinalzahl) zu einem Graphen \({\mathfrak G}\).
Im Bemühen, eine Verallgemeinerung für größere Graphen zu finden, beweisen die Verff. den Satz 3: Gegeben sei eine endliche Folge \(\langle {\mathfrak H}_i: i<k \rangle\) von abzählbaren Graphen. Dann existiert ein Graph \({\mathfrak G}\) mit \(|{\mathfrak G}| \leq 2^\omega\) derart, daß \({\mathfrak G} \mapsto ({\mathfrak H}_i)_{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 \({\mathfrak H}\), \({\mathfrak K}\) der Kardinalität \(\omega_1\) einen Graphen \({\mathfrak G}\) (von angemessener Größe) derart gibt, daß \({\mathfrak G} \mapsto ({\mathfrak H},{\mathfrak K})\) gilt?
Reviewer: H.-J.Presia

MSC:

05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
03E05 Other combinatorial set theory