×

Embedding theorems for graphs establishing negative partition relations. (English) Zbl 0381.04004

The graph \(G_1\) is said to embed into the graph \(G_1\) if \(G_0\) is isomorphic to a spanned subgraph of \(G_1\). Given cardinal numbers \(\varkappa\) and \(\lambda\), the symbol \([\varkappa]\) denotes the complete graph on \(\varkappa\) vertices, \([\varkappa\lambda]\) the complete \((\varkappa\lambda)\)-bipartite graph and , \([\varkappa/\varkappa]\) the half \((\varkappa/\varkappa)\)-bipartite graph (where the set of vertices is a disjoint union \(G_0\cup G_1\) with \(|G_0| = |G_1| = \varkappa\) and there are one-to-one enumerations \(G_0 = \{x_{\alpha};\alpha< \varkappa\}\), \(G_1=\{y_{\beta};\beta< \varkappa\}\) such that for each \(x_{\alpha}\), the set of vertices adjacent to \(x_{\alpha}\) is \(\{y_{\beta};\alpha< \beta< \varkappa\}\)). Let \(\triangle_0\), \(\triangle_1\) be symbols of these types: The graph \(G\) is said to establish the negative partition relation \(\varkappa\nrightarrow(\triangle_0,\triangle_1)^2\) if \(G\) is a graph on \(\varkappa\) vertices such that \(G\) contains no subgraph of type \(\triangle_0\) and the complement of \(G\) contains no subgraph of type \(\triangle_1\). The main aim of this paper is to characterize the class of all countable graphs which embed into all graphs \(G\) establishing \(\aleph_1\nrightarrow(\triangle_0,\triangle_1)^2\) when \(\triangle_0\), \(\triangle_1\) are any of \([\aleph_1]\), \([\aleph_1,\aleph_1]\), \([\aleph_1/\aleph_1]\), \([\aleph_0,\aleph_1]\), The authors prove their theorems in ZFC, and then try to show that they are ”best possible” assuming the continuum hypothesis or the existence of a Souslin tree. Occasionally Souslin’s axiom is invoked instead.
Reviewer: N.H.Williams

MSC:

03E05 Other combinatorial set theory
03E30 Axiomatics of classical set theory and its fragments
05C99 Graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. J. Devlin andH. Johnsbråten,The Souslin problem, Springer Verlag, 1974, Berlin-Heidelberg-New York.MR 52 # 5416
[2] P. Erdos, F. Galvin andA. Hajnal, On set-systems having large chromatic number and not containing prescribed subsystems,Colloquia Math. Soc. János Bolyai, 10. Infinite and finite sets (Keszthely Hungary, 1973), North-Holland, 1975, Amsterdam, 425–513.MR 53#2727
[3] P. Erdos andA. Hajnal, Unsolved problems in set theory,Proc. Sympos. Pure Math., 13,part 1, Amer. Math. Soc., Providence, R. I., 1971, 17–48.MR 43#6101
[4] P. Erdos andA. Hajnal, Unsolved and solved problems in set theory,Proceedings of the Tarski Symposium (Berkeley, Calif., 1971), Amer. Math. Soc., Providence, R. I., 1974, 269–287.MR 50#9590
[5] P. Erdos, A. Hajnal, A. Máté andR. Rado,Partition relations for cardinals. (To be published by the Hungarian Academy of Sciences)
[6] P. Erdos, A. Hajnal andR. Rado, Partition relations for cardinal numbers,Acta Math. Acad. Sci. Hungar. 16 (1965), 93–196.MR 34#2475. · Zbl 0158.26603
[7] W. P. Hanf, Incompactness in languages with infinitely long expressions,Fund. Math. 53 (1963–64), 309–324.MR 28#3943 · Zbl 0207.30201
[8] S. Shelah, Coloring without triangles and partition relations,Israel J. Math. 20 (1975), 1–12.Zbl. 311#05112 · Zbl 0311.05112
[9] R. M. Solovay andS. Tennenbaum, Iterated Cohen extensions and Souslin’s problem,Ann. of Math. 94 (1971), 201–245.MR 45#3212 · Zbl 0244.02023
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.