# Sh:492

- Komjáth, P., & Shelah, S. (1995).
*Universal graphs without large cliques*. J. Combin. Theory Ser. B,**63**(1), 125–135. arXiv: math/9308221 DOI: 10.1006/jctb.1995.1008 MR: 1309360 -
Abstract:

We give some existence/nonexistence statements on universal graphs, which under GCH give a necessary and sufficient condition for the existence of a universal graph of size \lambda with no K(\kappa), namely, if either \kappa is finite or cf(\kappa)>cf(\lambda). (Here K(\kappa) denotes the complete graph on \kappa vertices.) The special case when \lambda^{<\kappa}=\lambda was first proved by F. Galvin. Next, we investigate the question that if there is no universal K(\kappa)-free graph of size \lambda then how many of these graphs embed all the other. It was known, that if \lambda^{<\lambda}= \lambda (e.g., if \lambda is regular and the GCH holds below \lambda), and \kappa=\omega, then this number is \lambda^+. We show that this holds for every \kappa\leq\lambda of countable cofinality. On the other hand, even for \kappa=\omega_1, and any regular \lambda\geq\omega_1 it is consistent that the GCH holds below \lambda, 2^{\lambda} is as large as we wish, and the above number is either \lambda^+ or 2^{\lambda}, so both extremes can actually occur. - published version (11p)

Bib entry

@article{Sh:492, author = {Komj{\'a}th, P{\'e}ter and Shelah, Saharon}, title = {{Universal graphs without large cliques}}, journal = {J. Combin. Theory Ser. B}, fjournal = {Journal of Combinatorial Theory. Series B}, volume = {63}, number = {1}, year = {1995}, pages = {125--135}, issn = {0095-8956}, mrnumber = {1309360}, mrclass = {05C10}, doi = {10.1006/jctb.1995.1008}, note = {\href{https://arxiv.org/abs/math/9308221}{arXiv: math/9308221}}, arxiv_number = {math/9308221} }