×

Universal graphs without large bipartite subgraphs. (English) Zbl 0551.05057

Let \(1\leq \alpha \leq \beta \leq \gamma\) be cardinals, and let \({\mathcal G}_{\gamma}(K_{\alpha,\beta})\) denote the class of all graphs on \(\gamma\) vertices having no subgraphs isomorphic to \(K_{\alpha,\beta}\). A graph \(G_ 0\in {\mathcal G}_{\gamma}(K_{\alpha,\beta})\) is called universal if every \(G\in {\mathcal G}_{\gamma}(K_{\alpha,\beta})\) can be embedded into \(G_ 0\) as a subgraph. We prove that, if \(\alpha <\omega \leq \gamma\) and the general continuum hypothesis is assumed, then \({\mathcal G}_{\gamma}(K_{\alpha,\beta})\) has a universal element if and only if (i) \(\gamma >\omega\) or (ii) \(\gamma =\omega\), \(\alpha =1\) and \(\beta\leq 3\). Using the axiom of constructibility, we also show that there does not exist a universal graph in \({\mathcal G}_{\omega_ 1}(K_{\omega,\omega_ 1})\).

MSC:

05C75 Structural characterization of families of graphs
03E05 Other combinatorial set theory
Full Text: DOI

References:

[1] Erdos, Probabilistic methods in combinatorics (1974)
[2] Devlin, The axiom ofconstructibility, A guide for the mathematician, Lecture Notes in Mathematics (1977) · Zbl 0369.02043 · doi:10.1007/BFb0070208
[3] Chang, Model theory (1973)
[4] Mat. Lapok 29 pp 349– (1977)
[5] Hajnal, Studies in Logic and the Foundations of Mathematics pp 347– (1975)
[6] Rado, In A Seminar in Graph Theory (1967)
[7] Rado, Ada Arith. 9 pp 331– (1964)
[8] Hajnal, Coll. Math. Soc. J. Bolyai 37 pp 359– (1981)
[9] DOI: 10.1007/BF02764885 · Zbl 0269.04004 · doi:10.1007/BF02764885
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.